From a Tournament List to a Hamiltonian Path
A Hamiltonian path is a directed path that visits every vertex exactly once. In a tournament, every pair of distinct vertices is joined by exactly one directed arc, so when a new vertex is considered, it either points to an existing path vertex or is pointed to by that vertex. This complete orientation makes a direct insertion procedure possible: scan the current path from left to right and insert the new vertex at the first place where its arc points forward to a vertex already on the path.
All digraphs here are finite. An arc is an ordered pair of distinct vertices, written \(u\to v\). A directed path is a sequence of distinct vertices \(v_1,\ldots,v_k\) such that \(v_i\to v_{i+1}\) is an arc for every \(1\le i<k\). It is Hamiltonian if this sequence contains every vertex of the digraph.
When the input is given as lists, verify the tournament conditions before running the construction. The vertex list must contain no repeated vertices. Each listed arc must have both endpoints in that vertex list, must have distinct endpoints, and must occur only once in the arc list. Finally, for every unordered pair of distinct vertices, exactly one of its two possible directions must occur. These checks rule out missing arcs as well as loops, duplicate arcs and pairs listed in both directions.
The Insertion Procedure
Fix an order \(x_1,\ldots,x_n\) in which to process the vertices. Start with the one-vertex path \(P=(x_1)\). When processing a new vertex \(x\), scan the current path \(P=(v_1,\ldots,v_k)\) from left to right and find the first index \(i\) for which \(x\to v_i\). If there is such an index, insert \(x\) immediately before \(v_i\). If there is no such index, append \(x\) to the end.
Test the arcs \(x\to v_1,x\to v_2,\ldots\) in order, stopping at the first one that is present.
If the first such vertex is \(v_i\), place \(x\) immediately before \(v_i\). If no path vertex is beaten by \(x\), append \(x\).
Continue until all vertices are included, then check every consecutive arc in the resulting sequence.
Proof. We prove that after processing the first \(j\) vertices, the current sequence is a directed path containing exactly those \(j\) vertices, each once. For \(j=0\), the sequence is empty and the claim holds under the stated convention. For \(j=1\), the sequence consists of \(x_1\), so it is a path containing exactly the processed vertex.
Now suppose \(j\ge1\) and the claim holds for the current path \(P=(v_1,\ldots,v_k)\), where the vertices in \(P\) are exactly those already processed. Let \(x\) be the next, not-yet-processed vertex. If there is a first index \(i\) with \(x\to v_i\), then for each \(h<i\), the arc \(x\to v_h\) is absent. Since the graph is a tournament and \(x\ne v_h\), this means \(v_h\to x\). In particular, if \(i>1\), then \(v_{i-1}\to x\), and by the choice of \(i\), \(x\to v_i\). The new consecutive arcs at the insertion are therefore correctly directed; all other consecutive arcs are unchanged. If \(i=1\), the new sequence starts with \(x\to v_1\), and all old consecutive arcs remain unchanged. In either case the result is a directed path.
If no index \(i\) exists, then \(x\to v_h\) is absent for every \(h\). The tournament condition gives \(v_h\to x\) for every \(h\), in particular \(v_k\to x\), so appending \(x\) also gives a directed path. Since \(x\) was not previously in the path, the new sequence contains each processed vertex exactly once. Induction proves the claim after all vertices have been processed, at which point the path is Hamiltonian. \(\square\)
The proof also gives a useful invariant: every insertion preserves the directed path already constructed. A tournament need not be transitive; the algorithm does not try to put every arc in one consistent left-to-right order. It only ensures that each pair of consecutive vertices in the final sequence has the required arc.
Worked Constructions
Worked Example: A Five-Vertex Tournament
Let \(V=\{1,2,3,4,5\}\), with arc list \(E=\{1\to2,3\to1,1\to4,5\to1,2\to3,2\to4,5\to2,3\to4,3\to5,4\to5\}\). The list has ten arcs, one for each of the ten unordered pairs of vertices; no arc is a loop or repeated. Thus it specifies a tournament. Process the vertices in the order \(1,2,3,4,5\).
| Vertex inserted | Scan and insertion | Path after insertion |
|---|---|---|
| 1 | Start with the first vertex. | \((1)\) |
| 2 | \(1\to2\), so \(2\) beats no current path vertex; append. | \((1,2)\) |
| 3 | \(3\to1\) is present, so insert before \(1\). | \((3,1,2)\) |
| 4 | \(4\to3\), \(4\to1\), and \(4\to2\) are all absent; append. | \((3,1,2,4)\) |
| 5 | \(5\to3\) is absent, but \(5\to1\) is present; insert before \(1\). | \((3,5,1,2,4)\) |
The output is \((3,5,1,2,4)\). Check its consecutive arcs against the list: \(3\to5\) is present, \(5\to1\) is present, \(1\to2\) is present, and \(2\to4\) is present. Thus the output is a directed path. Its sequence contains all five vertices exactly once, so it is Hamiltonian.
Worked Example: An Interior Insertion
Let \(V=\{a,b,c,d\}\), with \(E=\{a\to b,c\to a,b\to c,d\to a,b\to d,c\to d\}\). There are six unordered pairs and six listed arcs; each pair occurs once, with one direction, and there are no loops or repeated arcs. This is a tournament. Process the vertices in the order \(a,b,c,d\).
Start with \((a)\). Since \(a\to b\), vertex \(b\) does not beat \(a\), so append \(b\) to obtain \((a,b)\). Next, \(c\to a\) is present, so insert \(c\) before \(a\), giving \((c,a,b)\). For \(d\), scan this path: \(d\to c\) is absent because \(c\to d\) is listed; \(d\to a\) is present. The first vertex beaten by \(d\) is therefore \(a\), so insert \(d\) between \(c\) and \(a\). The result is \((c,d,a,b)\).
Check the consecutive arcs individually: \(c\to d\) is listed, \(d\to a\) is listed, and \(a\to b\) is listed. The sequence contains \(c,d,a,b\), which are the four distinct vertices of \(V\), so it is a Hamiltonian path. The insertion step is valid because the vertex immediately before the insertion point, \(c\), points to \(d\), while \(d\) points to the vertex immediately after it, \(a\).
Worked Example: Changing the Processing Order
Let \(V=\{p,q,r,s,t\}\), with \(E=\{p\to q,r\to p,s\to p,p\to t,q\to r,q\to s,t\to q,r\to s,r\to t,t\to s\}\). There are ten listed arcs, one for each of the ten unordered pairs; no arc is repeated or a loop, so this is a tournament. Process the vertices in the order \(p,q,r,s,t\).
Start with \((p)\). Since \(p\to q\), append \(q\), obtaining \((p,q)\). For \(r\), \(r\to p\) is present, so insert \(r\) before \(p\), obtaining \((r,p,q)\). For \(s\), \(s\to r\) is absent because \(r\to s\) is listed, while \(s\to p\) is present. Insert \(s\) before \(p\), obtaining \((r,s,p,q)\). For \(t\), \(t\to r\) is absent because \(r\to t\) is listed, and \(t\to s\) is present. Insert \(t\) before \(s\), giving \((r,t,s,p,q)\).
Check every consecutive arc in the output: \(r\to t\), \(t\to s\), \(s\to p\), and \(p\to q\) all occur in the stated arc list. The output lists all five distinct vertices once, and hence is Hamiltonian. This example also shows that the construction depends on the chosen processing order, even though the theorem guarantees a Hamiltonian path for every order.
Input Checks, Efficiency and Pitfalls
For an input with \(n\) vertices, there are \(n(n-1)/2\) unordered pairs of distinct vertices. A valid tournament arc list must contain exactly one arc for each such pair, so it has exactly \(n(n-1)/2\) arcs. This count is a useful preliminary check, but it does not replace checking the pairs: the wrong list could have the right total number of entries. In particular, check explicitly that no directed arc appears twice and that no pair occurs in both directions.
With an adjacency table that records whether \(u\to v\) is present, validation can check each pair in constant time, for a total of order \(n^2\) pair checks. The insertion algorithm examines at most \(j\) path vertices when inserting the \((j+1)\)-st vertex. Thus it makes at most \(1+2+\cdots+(n-1)=n(n-1)/2\) arc tests, also of order \(n^2\) when table lookup takes constant time. If the input is stored only as an unsorted list and each test scans that whole list, the running time is larger; the order-\(n^2\) bound assumes constant-time access to arc directions.
For \(n=1\), the procedure returns the single vertex, which is a Hamiltonian path. For \(n=0\), it returns the empty sequence under the convention stated above. These cases need no arc tests. For larger inputs, do not skip the tournament validation: the insertion proof depends on the fact that when \(x\to v\) is absent, \(v\to x\) must be present.
Common pitfall: accepting a duplicated arc. Suppose an input lists the vertices \(\{1,2,3\}\) and the arcs \(1\to2,1\to2,2\to3\). There are three listed arcs, the same number as the three unordered pairs, but this is not a tournament: \(1\to2\) is duplicated, and neither direction between \(1\) and \(3\) is listed. Counting entries alone would incorrectly accept it. The correction is to reject duplicate arcs first, then check each unordered pair and require exactly one direction. Only after those checks does the insertion argument apply.
A separate construction error is to insert \(x\) before a vertex it beats without checking the preceding vertex. The procedure avoids this error by choosing the first path vertex beaten by \(x\): every earlier vertex points to \(x\), so the new adjacent arcs on both sides are justified. If no path vertex is beaten by \(x\), the correct action is to append \(x\), since every current path vertex then points to it.
Check Your Understanding
For each question, justify the answer using the insertion rule or its proof.
- In a tournament with \(n\) vertices, how many arcs must a valid arc list contain, and why does that count not by itself validate the list?
- Suppose the current path is \((u,v,w)\), with \(u\to x\), \(x\to v\), and \(w\to x\). Where does the algorithm insert \(x\), and which two arcs verify the new consecutive positions?
- Explain why the algorithm appends \(x\) when no arc \(x\to v_i\) occurs for a current path vertex \(v_i\).
- Give the checks needed to reject an arc list containing a duplicate directed arc.
- Why does the proof require the tournament condition, rather than merely assuming there is at least one directed arc between each pair?