The Insertion Idea
A tournament assigns a direction to every pair of distinct vertices. This complete set of pairwise choices makes it possible to place a new vertex into a path: it can go at one end, or there can be a consecutive pair of path vertices that point into and out of it in the right order. Repeating this step gives a constructive proof that every tournament has a directed Hamiltonian path.
The direction matters: a sequence of all the vertices is not a directed Hamiltonian path unless every consecutive arc points forward along the sequence. A one-vertex sequence is a directed path, since it has no consecutive pair whose orientation needs checking.
The Vertex-Insertion Lemma
Proof. If \(k=0\), the sequence consisting only of \(x\) is the required path. Suppose \(k\ge1\). If \(x\to x_1\), prepend \(x\) to the path. The new first arc points from \(x\) to \(x_1\), and all the old consecutive arcs are unchanged.
Now suppose \(x\to x_1\) does not hold. Since \(T\) is a tournament, \(x_1\to x\). If \(x_k\to x\), append \(x\) to the path; the new final arc has the required direction.
It remains to consider the case \(x_1\to x\) and \(x\to x_k\). Let \(j\) be the smallest index such that \(x\to x_j\). Such an index exists because \(x\to x_k\), and \(j\ge2\) because \(x_1\to x\). By the minimality of \(j\), \(x\to x_{j-1}\) does not hold. Exactly one arc joins \(x\) and \(x_{j-1}\), so \(x_{j-1}\to x\). Therefore the sequence \(x_1,\dots,x_{j-1},x,x_j,\dots,x_k\) is a directed path: the two new consecutive arcs are \(x_{j-1}\to x\) and \(x\to x_j\), while every other consecutive arc belongs to the original path. In each case the new sequence contains the old vertices in their original order and includes \(x\). \(\square\)
The lemma uses the tournament condition precisely where it must: whenever one direction between two vertices is ruled out, the opposite direction is guaranteed. For a general directed graph, neither direction might be present, and this insertion argument would not necessarily work.
Worked Example: Inserting a Vertex Between Two Path Vertices
Let \(T\) have vertex set \(\{1,2,3,4\}\) and arc set \(\{2\to1,1\to3,2\to3,2\to4,4\to1,4\to3\}\). Each of the six unordered pairs of vertices has exactly one listed direction, so this is a tournament.
On the vertices \(\{1,2,3\}\), the sequence \(2,1,3\) is a directed path: its consecutive arcs are \(2\to1\) and \(1\to3\). To insert vertex \(4\), check the path from left to right. The arc \(4\to2\) is absent, so the tournament has \(2\to4\). The next arc is \(4\to1\). Thus the transition from \(2\to4\) to \(4\to1\) allows \(4\) to be placed between \(2\) and \(1\).
| Path position checked | Arc involving \(4\) | Insertion information |
|---|---|---|
| First vertex \(2\) | \(2\to4\) | The path points into \(4\). |
| Next vertex \(1\) | \(4\to1\) | The path can continue out of \(4\). |
| Next vertex \(3\) | \(4\to3\) | The remaining path arc \(1\to3\) is retained. |
The resulting sequence is \(2,4,1,3\). Its consecutive arcs are \(2\to4\), \(4\to1\), and \(1\to3\), all of which are in the specified arc set. The sequence contains all four vertices exactly once, so it is a directed Hamiltonian path.
Check: The original path used \(2\to1\to3\). In the new sequence, that direct step is replaced by \(2\to4\to1\), and the final arc \(1\to3\) is unchanged. This verifies both the insertion and preservation of the original path order.
Rédei’s Theorem
Proof. We use induction on the number \(n\) of vertices. If \(n=1\), the sequence consisting of the unique vertex is a directed Hamiltonian path.
Now let \(n\ge2\), and assume the theorem holds for every tournament on \(n-1\) vertices. Choose a vertex \(x\) of the \(n\)-vertex tournament \(T\), and remove it. The induced tournament on the remaining \(n-1\) vertices is still a tournament: for each pair of remaining distinct vertices, the original tournament had exactly one direction between them, and removing \(x\) does not change that arc. By the induction hypothesis, these \(n-1\) vertices have a directed Hamiltonian path \(x_1,\dots,x_{n-1}\) in the smaller tournament. Apply the vertex-insertion lemma to this path and the removed vertex \(x\). It gives a directed path containing \(x\) and all \(n-1\) vertices of the smaller tournament. These are exactly the vertices of \(T\), each appearing once, so the path is Hamiltonian in \(T\). This proves the result for \(n\), and hence for every \(n\ge1\). \(\square\)
The induction is constructive: at each stage, remove one vertex, find a path on the smaller tournament, and then insert the removed vertex. The lemma proves that an insertion position always exists, even though that position can depend on the directions of several arcs.
Worked Example: Finding an Interior Insertion Position
Let \(T\) have vertex set \(\{a,b,c,d,e\}\) and arc set \(\{a\to b,a\to c,a\to d,a\to e,b\to c,b\to d,b\to e,c\to d,e\to c,e\to d\}\). There are ten unordered pairs of vertices, and the list gives one direction for each, so it specifies a tournament.
Start with the directed path \(a,b,c,d\), whose consecutive arcs \(a\to b\), \(b\to c\), and \(c\to d\) are all listed. Insert \(e\), scanning the old path in order:
| Old path vertex | Arc direction | What it tells us |
|---|---|---|
| \(a\) | \(a\to e\) | The first vertex points into \(e\). |
| \(b\) | \(b\to e\) | The next vertex also points into \(e\). |
| \(c\) | \(e\to c\) | The direction changes; insert \(e\) between \(b\) and \(c\). |
The result is \(a,b,e,c,d\). Its consecutive arcs are \(a\to b\), \(b\to e\), \(e\to c\), and \(c\to d\), each present in the arc set. The five entries are precisely the five distinct vertices of \(T\), so the result is Hamiltonian.
Check: The only new consecutive arcs are \(b\to e\) and \(e\to c\), both listed in the tournament. The old consecutive arc \(b\to c\) is no longer needed; all other old consecutive arcs remain.
Worked Example: Inserting at the End
Let \(T\) have vertex set \(\{a,b,c,d\}\) and arc set \(\{a\to b,a\to c,a\to d,b\to c,b\to d,c\to d\}\). These are the six pairs of distinct vertices, each with exactly one direction. The sequence \(a,b,c\) is a directed path in the tournament induced by \(\{a,b,c\}\).
The arcs involving \(d\) are \(a\to d\), \(b\to d\), and \(c\to d\). In particular, the last old path vertex points to \(d\), so append \(d\). The resulting path is \(a,b,c,d\), with consecutive arcs \(a\to b\), \(b\to c\), and \(c\to d\), all listed in the arc set. It includes all four distinct vertices exactly once.
Check: Appending does not alter either old arc \(a\to b\) or \(b\to c\); it adds only the verified arc \(c\to d\). Thus the path is directed and Hamiltonian.
Common Pitfall: The Arc Must Point the Right Way
A proposed insertion can use the right vertices and still fail if an arc points backwards. For example, let the tournament on \(\{a,b,c,x\}\) have arc set \(\{a\to b,b\to c,a\to c,x\to a,b\to x,c\to x\}\). The path \(a,b,c\) is directed. A tempting but incorrect insertion is \(a,x,b,c\), on the grounds that \(x\) is being placed between \(a\) and \(b\). But this sequence would require \(a\to x\), whereas the tournament has \(x\to a\). The proposed sequence is not a directed path.
The correct insertion is at the beginning: \(x,a,b,c\). Its consecutive arcs are \(x\to a\), \(a\to b\), and \(b\to c\), all present in the specified arc set. The direction of the new arc is not a detail that can be inferred from where a vertex is placed; it must be checked against the sequence order.
Rédei’s theorem guarantees a directed Hamiltonian path, not that every ordering of the vertices works, or that the path closes into a directed cycle. Its force comes from the tournament condition and the insertion lemma: at every induction step, the orientations ensure that the new vertex can be attached without losing the directed path property.
Check Your Understanding
Use the insertion cases and the induction proof to answer the following questions.
- In the insertion lemma, why does \(x_1\to x\) follow when \(x\to x_1\) does not hold?
- Suppose a directed path is \(p,q,r,s\), with \(p\to x\), \(q\to x\), \(x\to r\), and \(x\to s\). Where can \(x\) be inserted to preserve a directed path?
- In the induction proof, why is the tournament obtained by removing one vertex still a tournament?
- Give a tournament on three vertices and trace an insertion starting from a directed path on two of its vertices.
- Explain why the sequence \(a,x,b,c\) in the pitfall example is not a directed path, and verify the corrected sequence.