Proving Redei's Theorem

Question

Can someone prove Redei's theorem that every tournament has a directed Hamiltonan path in simple english?

The articles I found on it are very abstract and the only video on the topic is in Hindi.

Answer 1

A very relevant idea is the median order of a directed graph. It is a vertex ordering $v_1, v_2, \dots, v_n$ that maximizes the number of "forward edges": edges $(v_i, v_j)$ for which $i < j$. Since we are optimizing over $n!$ possible orderings, which is a finite set, a maximum must exist, though it is not always unique.

This is NP-hard to compute for general directed graphs. But it is a useful idea for proofs, where we don't have to worry about computing it! In particular, it immediately gives us the result you want here:

Theorem. $v_1, v_2, \dots, v_n$ is a median order of a tournament, then $(v_1, v_2, \dots, v_n)$ is a Hamiltonian path.

Proof. Suppose not: suppose there is an edge between $v_i$ and $v_{i+1}$ oriented $(v_{i+1}, v_i)$ rather than $(v_i, v_{i+1})$. Then swapping the two vertices $v_i$ and $v_{i+1}$ increases the number of forward edges by $1$: the edge between these two vertices is now a forward edge, and no other edges are affected. This contradicts the maximality of the median order we started with. $\square$