大家好
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
(附上原始題目)
請問看看有沒有大神可以證的出來或是提供點線索給小弟我
謝謝!

幫推 作業好難都想不到QQ目前這題只想到 如果把距離為1的邊都加上去行成一個新圖可以證明它是planar graphhttps://goo.gl/9ZxT1U可是就只能證到有3n-6條edge(pair)而已不知道3n-3是怎麼來的還是這樣就算證明結束了??

這題跟 台大電機104的蠻像的，我看別人的解釋是用畫圓但是這一題多減去3...

https://i.imgur.com/W6BKutK.jpg我用數學歸納證，有錯請指教

原來這裡都是修電機離散的XDP大，我也是用數學歸納法去想

其實我是同時有修課也有要考試啦p大的歸納法看起來怪怪的 n=k使用的假設和n=k+1證出來的好像不一樣

有人可以說明一下作業第一題的3嗎QQ

把g1用矩陣表示 可以得到每個點的deg=4所以去除4條邊後 c=1 or 2 就能帶公式了