MathLabs

第6题

在平面上给定 nn 个点，nge3n\\ge3，并连接每一对点。设最长线段的长度为 dd。长度为 dd 的连接线段称为直径。证明直径的条数至多为 nn。
第 2/4 步：用计数导出矛盾
上一步下一步
E>nLongrightarrow2En>2Longrightarrowsome vertex is incident with at least three diameters.E>n\\Longrightarrow\frac{2E}{n}>2\\Longrightarrow\text{some vertex is incident with at least three diameters}.
详细分析

假设有 E>nE>n 条直径，把它们看作给定点上的图的边。平均直径度数为 2E/n>22E/n>2，故某点 AA 至少连接三条直径 AB,AC,ADAB,AC,AD。取射线 ACAC 位于 ABAB 与 ADAD 之间。