每个锦标赛都存在哈密顿路径(雷代定理)

第一步(极端选择)。 在锦标赛的所有有向路径中,选出顶点数 $k$ 最大的一条 $P: v_1 \to v_2 \to \cdots \to v_k$;由于顶点只有有限多个,这个最大值必定存在。为得出矛盾,假设 $k < n$,并设 $u$ 为不在 $P$ 上的一个顶点。

第二步(在两端分类讨论)。 由于锦标赛中 $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$ 成立。

第三步(确定插入位置)。 现在已知 $v_1 \to u$ 与 $u \to v_k$。设 $j$ 为 $\{1, \dots, k-1\}$ 中使 $v_j \to u$ 成立的最大下标;由于 $j = 1$ 满足条件,该下标集合非空,故由极端原理 $j$ 存在。由 $j$ 的最大性,弧 $v_{j+1} \to u$ 不成立,于是锦标赛的性质迫使 $u \to v_{j+1}$ 成立。

第四步(通过插入得到矛盾)。 结合 $v_j \to u$ 与 $u \to v_{j+1}$,把 $u$ 插入 $v_j$ 与 $v_{j+1}$ 之间,得到路径 $v_1 \to \cdots \to v_j \to u \to v_{j+1} \to \cdots \to v_k$,它有 $k + 1$ 个顶点,与 $k$ 的最大性矛盾。

第五步(结论)。 这样的顶点 $u$ 不可能存在,故 $k = n$,$P$ 即为一条哈密顿路径。