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 だから、少なくとも三本 AB,AC,ADAB,AC,AD の直径が一点 AA に接続する。ACAC を ABAB と ADAD の間の光線に選ぶ。