場合分けと極値原理

点が直線上にない(点、2点を通る直線)という有限個の組の中から、厳密に最小の距離を達成する組を選ぶ。もしその最も近い直線上に3つ目の点があれば、幾何学的にさらに近い組が作られてしまい、最小性に矛盾する。

ステップ1(極値による選択の設定)。 $P$ を、すべてが同一直線上にはない $n \ge 3$ 個の点からなる与えられた有限集合とする。$\ell$ が $P$ の少なくとも $2$ 個の点を通る直線であり、$Q \in P$ が $\ell$ 上にない点であるような組 $(Q, \ell)$ からなる有限集合を考える。この集合は($P$ がすべて同一直線上にはないため)空でなく、有限であるから、極値原理により、点から直線までの距離 $d(Q_0, \ell_0)$ を最小にする組 $(Q_0, \ell_0)$ を選ぶことができる。

ステップ2(矛盾の仮定)。 矛盾を導くために、$\ell_0$ が $P$ の点を $3$ 個以上含むと仮定する。$F$ を $Q_0$ から $\ell_0$ への垂線の足とする。$\ell_0$ 上には $P$ の点が $\ge 3$ 個あり、それらは $F$ から $\ell_0$ に沿って伸びる高々 $2$ 本の半直線上にあるので、鳩の巣原理により、そのうち2点 $B$ と $C$ が同じ半直線上にあり、$B$ が $F$ と $C$ の間にある($B = F$ の場合も含む)ようにできる。

ステップ3(相似三角形によるより近い組の構成)。 $B$ から直線 $Q_0C$ へ垂線を下ろし、その足を $G$ とする。直角三角形 $\triangle BGC$ と $\triangle Q_0FC$ は $C$ における角を共有するので相似であり、$\dfrac{BG}{Q_0F} = \dfrac{BC}{Q_0C}$ が成り立つ。$B$ が $F$ と $C$ の間にあるので $BC \le FC$ であり、$\triangle Q_0FC$ は $F$ で直角なので斜辺について $FC < Q_0C$ が成り立つ。これらを合わせると $BC < Q_0C$ となり、したがって $BG < Q_0F = d(Q_0, \ell_0)$ を得る。

ステップ4(矛盾)。 直線 $Q_0C$ は $P$ の $2$ 個の点(すなわち $Q_0$ と $C$)を通り、$B$ はその上にない $P$ の点であるから、$(B, Q_0C)$ は有限集合の中の有効な組であり、$d(B, Q_0C) = BG < d(Q_0, \ell_0)$ を満たす。これは $(Q_0, \ell_0)$ の最小性に矛盾する。

ステップ5(結論)。 この矛盾により $\ell_0$ は $P$ の点を $3$ 個以上含むことはできない。少なくとも $2$ 個を含むように選ばれていたので、ちょうど $2$ 個を含み、$\ell_0$ が求める通常直線である。

有向路の中で長さが最大のものを取る。もし取り残された頂点があれば、トーナメントの性質(すべての対に有向辺が存在する)により、路の端を延長するか、途中に欠けた頂点を挿入することができ、最大性に矛盾する。

ステップ1(極値による選択)。 トーナメント内のすべての有向路の中から、頂点数 $k$ が最大となるもの $P: v_1 \to v_2 \to \cdots \to v_k$ を選ぶ。頂点は有限個しかないため、この最大値は存在する。矛盾を導くために $k < n$ と仮定し、$u$ を $P$ に含まれない頂点とする。

ステップ2(両端での場合分け)。 トーナメントでは $u \to v_1$ または $v_1 \to u$ のちょうど一方が成り立つ。もし $u \to v_1$ が成り立てば、先頭に $u$ を加えることでより長い路 $u \to v_1 \to \cdots \to v_k$ が得られ、$k$ の最大性に矛盾する。したがって $v_1 \to u$ が成り立つ。同様に、$v_k \to u$ または $u \to v_k$ のちょうど一方が成り立つ。もし $v_k \to u$ が成り立てば、末尾に $u$ を加えることでより長い路が得られ、最大性に矛盾する。したがって $u \to v_k$ が成り立つ。

ステップ3(挿入位置の特定)。 ここまでで $v_1 \to u$ と $u \to v_k$ が分かった。$v_j \to u$ が成り立つような $\{1, \dots, k-1\}$ 内の最大の添字を $j$ とする。$j = 1$ が条件を満たすためこの添字集合は空でなく、極値原理により $j$ が存在する。$j$ の最大性より弧 $v_{j+1} \to u$ は成り立たないので、トーナメントの性質により $u \to v_{j+1}$ が成り立つ。

ステップ4(挿入による矛盾)。 $v_j \to u$ と $u \to v_{j+1}$ を組み合わせて、$v_j$ と $v_{j+1}$ の間に $u$ を挿入すると、路 $v_1 \to \cdots \to v_j \to u \to v_{j+1} \to \cdots \to v_k$ が得られ、これは $k + 1$ 個の頂点を持ち、$k$ の最大性に矛盾する。

ステップ5(結論)。 そのような頂点 $u$ は存在し得ないので $k = n$ となり、$P$ はハミルトン路である。