Mọi giải đấu đều có đường đi Hamilton (định lý Rédei)

Bước 1 (lựa chọn cực hạn). Trong tất cả các đường đi có hướng của giải đấu, chọn một đường, $P: v_1 \to v_2 \to \cdots \to v_k$, có số đỉnh $k$ lớn nhất có thể; giá trị lớn nhất này tồn tại vì chỉ có hữu hạn đỉnh. Giả sử, để phản chứng, rằng $k < n$, và gọi $u$ là một đỉnh không thuộc $P$.

Bước 2 (chia trường hợp ở hai đầu). Vì giải đấu có đúng một trong hai cung $u \to v_1$ hoặc $v_1 \to u$: nếu $u \to v_1$ đúng, thì việc thêm $u$ vào đầu sẽ cho đường đi dài hơn $u \to v_1 \to \cdots \to v_k$, mâu thuẫn với tính lớn nhất của $k$; do đó $v_1 \to u$ đúng. Tương tự, đúng một trong hai cung $v_k \to u$ hoặc $u \to v_k$ tồn tại: nếu $v_k \to u$ đúng, thì việc thêm $u$ vào cuối sẽ cho một đường đi dài hơn, mâu thuẫn với tính lớn nhất; do đó $u \to v_k$ đúng.

Bước 3 (xác định vị trí chèn). Bây giờ ta biết $v_1 \to u$ và $u \to v_k$. Gọi $j$ là chỉ số lớn nhất trong $\{1, \dots, k-1\}$ sao cho $v_j \to u$ đúng; tập chỉ số này không rỗng vì $j = 1$ thỏa mãn, nên theo nguyên lý cực hạn $j$ tồn tại. Do tính lớn nhất của $j$, cung $v_{j+1} \to u$ không tồn tại, nên tính chất giải đấu buộc $u \to v_{j+1}$ phải đúng.

Bước 4 (mâu thuẫn nhờ phép chèn). Kết hợp $v_j \to u$ với $u \to v_{j+1}$, ta chèn $u$ vào giữa $v_j$ và $v_{j+1}$ để tạo thành đường đi $v_1 \to \cdots \to v_j \to u \to v_{j+1} \to \cdots \to v_k$, có $k + 1$ đỉnh, mâu thuẫn với tính lớn nhất của $k$.

Bước 5 (kết luận). Không thể tồn tại đỉnh $u$ như vậy, nên $k = n$ và $P$ là một đường đi Hamilton.