Cycles · Hamiltonian Graphs

Lesson 8

Nikolai Chukhin · Alexander S. Kulikov

We now turn to the consideration of directed graphs. A tournament is a directed graph in which there is an edge in one of two directions between any two vertices. The tournament is named as such because it is convenient for representing the results of games between all pairs of teams.

Theorem. Every tournament has a Hamiltonian path.

Proof. We prove by induction on \(n\). The case \(n=1\) is clear. For the transition \(n-1\to n\), remove vertex \(n\) from the graph and construct a Hamiltonian path in the remaining graph. Let \(1 \to 2 \to \dotsb \to n-1\) be this Hamiltonian path. If there is an edge \((n,1)\) or an edge \((n-1,n)\), then everything is ready. Now suppose instead of these edges there are edges \((1,n)\) and \((n,n-1)\).

Thus, as \(i\) increases from \(1\) to \(n-1\), the direction of an edge will at some point "switch": there will be edges \((i,n)\) and \((n,i+1)\). This gives the Hamiltonian path: \[1\to2\to \dotsb \to i \to n \to i+1 \to i+2\to \dotsb \to n-1 \ .\]

◼