すべてのトーナメントにハミルトン路が存在する(レーデイの定理)

ステップ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$ はハミルトン路である。