[理工] 離散數學的證明題

[triumphant10 (yu12510 )]

大家好

Let S be a set of n points in the plane such that the distance between any two
is at least one .
Prove that there are at most 3n-3 pairs of points with distance exactly one.

https://imgur.com/a/Z4WyGPV
(附上原始題目)

請問看看有沒有大神可以證的出來或是提供點線索給小弟我

謝謝!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.7.151
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545496138.A.44C.html
推 Leaving: 幫推 作業好難都想不到QQ
→ Leaving: 目前這題只想到 如果把距離為1的邊都加上去行成一個新圖
→ Leaving: 可以證明它是planar graph
→ Leaving: https://goo.gl/9ZxT1U
→ Leaving: 可是就只能證到有3n-6條edge(pair)而已
→ Leaving: 不知道3n-3是怎麼來的
→ Leaving: 還是這樣就算證明結束了??
推 eggy1018: 這題跟 台大電機104的蠻像的，我看別人的解釋是用畫圓
→ eggy1018: 但是這一題多減去3...
推 ponponjerry: https://i.imgur.com/W6BKutK.jpg
→ ponponjerry: 我用數學歸納證，有錯請指教
→ triumphant10: 原來這裡都是修電機離散的XD
→ triumphant10: P大，我也是用數學歸納法去想
推 Leaving: 其實我是同時有修課也有要考試啦
→ Leaving: p大的歸納法看起來怪怪的 n=k使用的假設和n=k+1證出來的
→ Leaving: 好像不一樣
推 zqAI3yGOAT: 有人可以說明一下作業第一題的3嗎QQ
→ Leaving: 把g1用矩陣表示 可以得到每個點的deg=4
→ Leaving: 所以去除4條邊後 c=1 or 2 就能帶公式了