Xét trường hợp, cực hạn

Trong hữu hạn các cặp (điểm, đường thẳng qua hai điểm) mà điểm không nằm trên đường thẳng, chọn cặp đạt khoảng cách nhỏ nhất ngặt; nếu đường thẳng gần nhất đó có điểm thứ ba nằm trên, hình học sẽ tạo ra một cặp còn gần hơn nữa, điều này là không thể do tính nhỏ nhất.

Bước 1 (thiết lập lựa chọn cực hạn). Cho $P$ là tập hữu hạn đã cho gồm $n \ge 3$ điểm, không thẳng hàng tất cả. Xét tập hữu hạn các cặp $(Q, \ell)$ trong đó $\ell$ là đường thẳng đi qua ít nhất $2$ điểm của $P$ và $Q \in P$ là một điểm không nằm trên $\ell$. Tập này không rỗng (vì $P$ không thẳng hàng tất cả) và hữu hạn, nên theo nguyên lý cực hạn ta có thể chọn một cặp $(Q_0, \ell_0)$ làm khoảng cách $d(Q_0, \ell_0)$ từ điểm đến đường thẳng đạt giá trị nhỏ nhất.

Bước 2 (giả sử phản chứng). Giả sử, để phản chứng, rằng $\ell_0$ chứa ít nhất $3$ điểm của $P$. Gọi $F$ là chân đường vuông góc hạ từ $Q_0$ xuống $\ell_0$. Vì có $\ge 3$ điểm của $P$ nằm trên $\ell_0$ và chúng chỉ có thể nằm trên nhiều nhất $2$ tia xuất phát từ $F$ dọc theo $\ell_0$, nguyên lý Dirichlet cho ta hai điểm trong số đó, $B$ và $C$, nằm trên cùng một tia, với $B$ nằm giữa $F$ và $C$ (cho phép $B = F$).

Bước 3 (dựng một cặp gần hơn nhờ tam giác đồng dạng). Hạ đường vuông góc từ $B$ xuống đường thẳng $Q_0C$, chân là $G$. Hai tam giác vuông $\triangle BGC$ và $\triangle Q_0FC$ có chung góc tại $C$, nên chúng đồng dạng, cho ta $\dfrac{BG}{Q_0F} = \dfrac{BC}{Q_0C}$. Vì $B$ nằm giữa $F$ và $C$ nên $BC \le FC$, và vì $\triangle Q_0FC$ vuông tại $F$ nên cạnh huyền thỏa $FC < Q_0C$; kết hợp lại, $BC < Q_0C$, do đó $BG < Q_0F = d(Q_0, \ell_0)$.

Bước 4 (mâu thuẫn). Đường thẳng $Q_0C$ đi qua $2$ điểm của $P$ (cụ thể là $Q_0$ và $C$), và $B$ là một điểm của $P$ không nằm trên đó, nên $(B, Q_0C)$ là một cặp hợp lệ trong tập hữu hạn của ta với $d(B, Q_0C) = BG < d(Q_0, \ell_0)$, mâu thuẫn với tính nhỏ nhất của $(Q_0, \ell_0)$.

Bước 5 (kết luận). Mâu thuẫn này cho thấy $\ell_0$ không thể chứa $3$ điểm trở lên của $P$; vì nó được chọn chứa ít nhất $2$ điểm, nên nó chứa đúng $2$ điểm, vậy $\ell_0$ chính là đường thẳng thường cần tìm.

Lấy một đường đi có hướng dài nhất; nếu có một đỉnh nào đó bị bỏ sót, tính chất của giải đấu (mọi cặp đều có một cạnh có hướng) sẽ cho phép ta kéo dài đường đi ở một đầu hoặc chèn đỉnh bị thiếu vào giữa, mâu thuẫn với tính lớn nhất.

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.