Directed Reachability in Tournaments

Reachability in a Tournament

A tournament assigns a direction to every pair of distinct vertices. This guarantees that each pair is directly connected in one direction, but it does not guarantee that every vertex can reach every other vertex by following the directions. The distinction between a direct arc and a directed path is essential: a path can sometimes travel against a direct arc by taking a longer route, but in other tournaments it cannot.

All digraphs here are finite and have no loops or multiple arcs. A directed path from \(u\) to \(v\) is a sequence \(u=v_0,v_1,\ldots,v_\ell=v\) of distinct vertices such that \(v_{i-1}\to v_i\) is an arc for each \(i\). A path of length zero is allowed from a vertex to itself. We say \(v\) is reachable from \(u\) if there is a directed path from \(u\) to \(v\). A digraph is strongly connected if each vertex can reach every vertex, and its strong components are its maximal strongly connected subdigraphs.

Reachability is reflexive because length-zero paths are allowed, and it is transitive because directed paths can be concatenated. If a concatenation repeats a vertex, deleting the portion between two occurrences gives a shorter directed walk with the same endpoints; repeating this deletion produces a directed path. Consequently, the relation “\(u\) reaches \(v\) and \(v\) reaches \(u\)” is an equivalence relation. Its equivalence classes are exactly the strong components.

How Strong Components Are Ordered

Proof. First consider distinct strong components \(A\) and \(B\). Suppose there are arcs in both directions between them: \(a\to b\) with \(a\in A,b\in B\), and \(b'\to a'\) with \(b'\in B,a'\in A\). Since \(A\) is strongly connected, there is a directed path from \(a'\) to \(a\); since \(B\) is strongly connected, there is a directed path from \(b\) to \(b'\). Thus there is a directed route from \(A\) to \(B\) and one from \(B\) to \(A\). Every vertex in either component can reach the relevant route within its component, so vertices of \(A\) and \(B\) are mutually reachable. They would belong to the same strong component, a contradiction. Therefore all arcs between \(A\) and \(B\) point one way.

Now form a digraph whose vertices are the strong components, putting an arc \(A\to B\) when the arcs between the original components point from \(A\) to \(B\). Between every pair of these vertices there is exactly one arc, by the first part. This component digraph has no directed cycle: a cycle of components would give directed routes around the cycle, making its components mutually reachable and contradicting their distinctness.

A finite acyclic digraph has a topological ordering. For completeness, it has a vertex with no incoming arc: otherwise, repeatedly following an incoming arc would eventually repeat a vertex, producing a directed cycle. Remove such a vertex, repeat on the remaining acyclic digraph, and list the removed vertices in order. In the component digraph, every pair has an arc, and a topological ordering must place the tail of each arc before its head. Hence every arc points forward in that ordering. Translating back to the tournament gives the asserted ordering \(C_1,\ldots,C_k\). If the tournament has no vertices, there are no components and the ordering is empty; a one-vertex tournament has one component. \(\square\)

Proof. If \(u\to v\), the single arc is a directed path, so \(u\) reaches \(v\). If \(u\) and \(v\) are in the same strong component, strong connectivity gives a directed path from \(u\) to \(v\). For the converse, suppose \(u\) reaches \(v\) but \(u\not\to v\). The tournament condition gives \(v\to u\). The path from \(u\) to \(v\), together with this return arc, shows that \(v\) reaches \(u\). Thus \(u\) and \(v\) are mutually reachable, so they belong to the same strong component. \(\square\)

The corollary gives a useful decision rule. If \(u\to v\), reachability is immediate. If \(v\to u\), then \(u\) reaches \(v\) precisely when they lie in the same strong component. Equivalently, once the components are known, reachability between distinct components is exactly the forward order: vertices in \(C_i\) reach vertices in \(C_j\) when \(i<j\), and do not reach them when \(i>j\).

Worked Examples

Component Sizes and a Common Pitfall

A strong component of a tournament can have one vertex, or at least three vertices; it cannot have exactly two. Indeed, on two vertices there is only one arc, say \(u\to v\). There is no directed path from \(v\) back to \(u\), since the only other vertex is \(u\) and there is no arc \(v\to u\). Thus the two vertices cannot be mutually reachable. This observation is often a useful consistency check when identifying components.

Common mistake: “Every pair of vertices is joined by an arc, so every tournament is strongly connected.” For a concrete counterexample, take \(V=\{1,2,3\}\) and \(E=\{1\to2,1\to3,2\to3\}\). The pair count is \(3\cdot2/2=3\), and all three pairs occur, so this is a tournament. But every arc points from a smaller label to a larger one. A directed path cannot decrease its label, so \(3\) reaches neither \(1\) nor \(2\). The correction is to test directed paths, not just adjacency: a tournament can have several strong components, and the theorem says those components are linearly ordered with all arcs pointing forward.

For a finite tournament, a reliable analysis is therefore to determine which vertices are mutually reachable, group them into strong components, and then order the groups by their arc directions. Within a component, every vertex reaches every other; between distinct components, the direction of the ordered pair decides reachability completely. The component order also explains why a path cannot travel backward through the components: every arc, and hence every directed path, moves forward or stays within one component.