Every Tournament Has a Hamiltonian Path

A chess club with no draws#

Six people in a chess club each play every other member once. Every game has a winner. Can you always line up all six so that each person beat the next person in the line?

The surprising answer is yes, always, no matter who beat whom. This page proves it.

The vocabulary, one clause each. A tournament is exactly this setup: every pair plays once and one of the two wins. In graph language, players are vertices and each game is an edge with an arrow pointing from winner to loser. A directed path follows the arrows. A Hamiltonian path is a directed path that visits every vertex exactly once.

Theorem. Every tournament has a Hamiltonian path.

Why you cannot just check them all#

With 6 players, each plays 5 games, which counts 6 · 5 = 30, but every game is counted twice, once by each player. So there are 15 games.

Each game can go 2 ways, so there are 2¹⁵ = 32,768 different tournaments on 6 labelled players. With 10 players there are 45 games and 2⁴⁵ tournaments, more than 35 trillion. Checking them one by one is not a proof and not practical. Induction handles every size at once.

The proof by induction on the number of players#

We induct on n, the number of vertices.

Basis step, n = 2. There is one game. Start at the winner and go to the loser. That path visits both players. Done.

Induction hypothesis. Assume every tournament with n players (for some n ≥ 2) has a Hamiltonian path.

Inductive step. Take any tournament with n + 1 players. Set one player aside; call them v. The other n players, with the games among them, form a tournament on n players. By the induction hypothesis it has a Hamiltonian path. Number the players along that path:

1 → 2 → 3 → … → n   (each beat the next).

Now fit v back in. v played every one of them, so every pair (v, i) has an arrow one way or the other.

• If v beat player 1, put v at the front: v → 1 → 2 → … → n.
• Otherwise player 1 beat v. Walk along the path and stop at the first player i that v beat. The player just before, i − 1, did not lose to v, so i − 1 beat v. Slot v in between: … → i − 1 → v → i → …
• If v beat nobody, then in particular n beat v. Put v at the end: 1 → … → n → v.

In every case we have a path through all n + 1 players, each beating the next.

Conclusion. By the principle of mathematical induction, every tournament with n ≥ 2 players has a Hamiltonian path.

The proof is also an algorithm#

Your professor stressed that a good induction proof can be turned into a program. This one can. Start with one player. Add the others one at a time, each time inserting the new player just before the first person in the current line whom they beat (or at the end). When everyone is in, you have the path.

That procedure was run on 5,000 random tournaments of 2 to 10 players while this guide was written. It produced a valid Hamiltonian path every time.

Where this goes wrong#

• Always putting the new player at the end. That only works when player n beat v.
• Stopping at any player v beat, not the first one. The argument needs the player just before to have beaten v, and that is only guaranteed for the first such player.
• Starting at n = 1. With one player there are no games, so “tournament” says nothing useful. The lecture’s basis step is n = 2 (a one-vertex path is trivially fine too, but say which you use).
• Forgetting to use the hypothesis. The whole step rests on the path through the other n players. Say out loud where it came from.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.