Hamiltonian Paths in Tournaments

Paths That Visit Every Vertex

A directed path can travel through a tournament without visiting most of its vertices. A directed Hamiltonian path has a more demanding requirement: it follows the direction of every step and visits every vertex exactly once. The distinction matters because a list containing all the vertices is not necessarily a directed path in the order listed. To check an ordering, each consecutive pair must have its arc pointing forward.

A directed walk is a sequence \(v_0,v_1,\ldots,v_\ell\) such that \(\overrightarrow{v_{i-1}v_i}\in E\) for every \(i\) from \(1\) to \(\ell\). A directed path is a directed walk with no repeated vertices. Its length is the number \(\ell\) of arcs it uses. In particular, a one-vertex sequence is a path of length zero.

The tournament condition guarantees that every pair of distinct vertices is joined by an arc, but it does not prescribe which way that arc points. Consequently, the order of the vertices is essential: an ordering is a directed path only when every consecutive arc points from the earlier vertex to the next one. To be Hamiltonian, it must also include every vertex exactly once.

Checking an Ordering

Proof. Assume first that the ordering is a directed Hamiltonian path. By the definition of a directed path, each consecutive pair is joined by an arc in the direction of the sequence, so \(\overrightarrow{v_iv_{i+1}}\in E\) for every \(i\). Conversely, suppose the ordering lists every vertex exactly once and all those forward arcs belong to \(E\). The sequence then follows a directed arc at each step, so it is a directed walk. Its vertices are distinct, making it a directed path; because the sequence lists all vertices, it is Hamiltonian. \(\square\)

For a tournament, exactly one of the two possible arcs between consecutive vertices points forward. So checking an ordering requires checking \(n-1\) arcs, not every arc of the tournament. The remaining arcs may point in either direction without changing whether the proposed ordering is a Hamiltonian path.

Reachability Along a Hamiltonian Path

Hamiltonian paths also give a direct reachability statement. In a directed graph, a vertex \(y\) is reachable from \(x\) if there is a directed path from \(x\) to \(y\). A Hamiltonian path provides such a path from each earlier vertex in its ordering to each later one, though it need not provide a route in the reverse direction.

Proof. Suppose \(i<j\). The segment \(v_i,v_{i+1},\ldots,v_j\) consists of consecutive vertices from the Hamiltonian path. Each arc \(\overrightarrow{v_kv_{k+1}}\), for \(k=i,\ldots,j-1\), belongs to \(E\), because the full sequence is a directed path. The segment therefore gives a directed path from \(v_i\) to \(v_j\), proving reachability. This argument does not establish reachability from \(v_j\) to \(v_i\): it follows only the forward arcs in the given sequence. \(\square\)

In particular, the first vertex of a Hamiltonian path can reach every vertex along its successive segments, and every vertex can reach the last vertex. This does not imply that the tournament is strongly connected. Strong connectivity requires that every vertex be reachable from every other vertex, including in both directions for each pair.

Transitive Tournaments

A useful special case is a transitive tournament: one whose vertices can be placed in a linear order so that every arc points from an earlier vertex to a later one. This means that the chosen order itself gives a Hamiltonian path. In fact, it is the only possible Hamiltonian path in that order direction.

Proof. Let the vertices be \(u_1,\ldots,u_n\) in a transitive order, so \(\overrightarrow{u_iu_j}\in E\) whenever \(i<j\). The sequence \(u_1,\ldots,u_n\) lists every vertex once, and each consecutive arc points forward, so it is a Hamiltonian path. Now consider any directed Hamiltonian path in this tournament. For each consecutive pair in that path, the arc must point from the earlier vertex in the transitive order to the later one. Therefore the positions in the transitive order strictly increase at every step. The path lists all \(n\) vertices, so its positions are a strictly increasing ordering of the integers \(1,\ldots,n\). The only such ordering is \(1,\ldots,n\). Hence the path must be \(u_1,\ldots,u_n\), proving uniqueness. \(\square\)

Common Pitfall: Counting Vertices Is Not Enough

A common mistake is to treat any ordering containing every vertex exactly once as a Hamiltonian path. That checks only the spanning condition; it ignores the direction of the arcs. Both conditions are required: the vertices must all appear exactly once, and every consecutive arc must point in the direction of travel.

For a concrete failure, use the tournament in the previous example and try the ordering \(a,c,b,d\). It lists all four vertices exactly once, but its second step would require \(\overrightarrow{cb}\). The edge set contains \(\overrightarrow{bc}\), not \(\overrightarrow{cb}\). The ordering is therefore not a directed path, let alone a Hamiltonian path. The correction is to test its consecutive pairs: \(a\) to \(c\) is allowed, \(c\) to \(b\) is not, and \(b\) to \(d\) is allowed. One backward step is enough to invalidate the entire ordering.

Also keep a path distinct from a cycle. A directed Hamiltonian cycle must visit every vertex exactly once before returning to its start, so it needs an additional closing arc from its last vertex to its first. A Hamiltonian path does not require that arc. The previous example with \(1,2,3,4\) shows why the distinction matters: the path exists, but the required return arc does not.