Question

其中任意两点之间的距离至少为1

求教一道图论题!
设平面上有n个点v1,v2,……,vn,其中任意两点间的距离至少是1,证明至多有3n对点,每对点的距离恰好是1.

Answer 1

这个大致属于组合几何的范畴,不属于图论问题.
很简单：
第一步：证任何一个点vi至多和6个不同的点有距离1.
用反证法,若存在一个点vi和7个（或以上的点）距离为1,则这7个点落在以vi为圆心的单位圆上,必存在两点距离小于1,与题设矛盾.
第二步：由第一步得,至多有n×6÷2=3n对点的距离为1.
证毕!