大家好
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 就能带公式了