1

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.

6ix9ine
  • 13
  • 1
    Are you asking about the theorem itself, or about a proof of it? The proof in this PDF is very simple. The theorem just says that if you have a directed graph that has a directed edge between every pair of distinct vertices, there is a path using those edges that goes through every vertex. – Brian M. Scott Mar 08 '21 at 23:16
  • I meant proving the theorem. Thank you I will check out the pdf. – 6ix9ine Mar 08 '21 at 23:38
  • If I remember right, Redei proved a stronger result, that every tournament has an odd number of {directed} Hamiltonian paths. Did you want a proof of that stronger result, or just the fact that every tournament has at least one Hamiltonian path? – bof Mar 08 '21 at 23:47
  • @bof Just the fact that every tournament has at least one Hamiltonian path. – 6ix9ine Mar 09 '21 at 00:07

1 Answers1

-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$

Misha Lavrov
  • 142,276