Tournaments and Forward Orders
A tournament records a direction for every pairwise contest: for any two distinct vertices, exactly one defeats the other. The direction of each pair imposes an ordering constraint. If the constraints are consistent, the vertices can be listed so that every arc points from an earlier vertex to a later one. This tutorial proves that consistency is equivalent to having no directed cycle, and explains why such a tournament is called transitive.
All digraphs considered here are finite. An arc \(u\to v\) is a directed edge from \(u\) to \(v\). A directed walk is a sequence \(v_0,v_1,\ldots,v_\ell\) such that \(v_{i-1}\to v_i\) is an arc for each \(1\le i\le\ell\). A directed cycle is a directed closed walk of length at least \(3\) whose vertices \(v_0,\ldots,v_{\ell-1}\) are distinct. A digraph is acyclic if it contains no directed cycle.
In a tournament, the orientation between each pair is fixed, so a forward order, if it exists, has to respect every one of those pairwise directions. The empty tournament has the empty forward order and is acyclic; a one-vertex tournament has its one possible order and is also acyclic. These cases will be included in the characterization.
The Acyclicity Characterization
Proof. First suppose the tournament has a forward order \(v_1,\ldots,v_n\). If it contained a directed cycle, every arc on that cycle would go from a smaller index to a larger index. Following the cycle would then require the indices to increase at each step and return to their starting index, which is impossible. Thus the tournament is acyclic.
For the converse, we first establish that every nonempty acyclic tournament has a vertex with no incoming arc, called a source. Suppose instead that every vertex has at least one incoming arc. Starting at any vertex \(x_0\), choose a vertex \(x_1\) with \(x_1\to x_0\), then a vertex \(x_2\) with \(x_2\to x_1\), and continue. Since the tournament has finitely many vertices, some vertex repeats. The portion of this sequence between two occurrences, read in the direction of its arcs, is a directed closed walk. Choose a repeated segment with no internal repeated vertex, by shortening the segment whenever an internal vertex repeats. Its length cannot be \(1\), because there are no loops. Its length cannot be \(2\), because that would require both \(u\to v\) and \(v\to u\), which a tournament forbids. So its length is at least \(3\), and it is a directed cycle. This contradicts acyclicity. Therefore a source exists.
Now use induction on the number \(n\) of vertices. For \(n=0\), the empty order works. For \(n=1\), the only vertex is a forward order. Suppose \(n\ge2\) and the claim holds for tournaments with fewer than \(n\) vertices. Choose a source \(s\), and remove it. The remaining digraph is still a tournament: every pair of remaining vertices still has exactly one of its two possible arcs. It is acyclic because any directed cycle in it would also be a directed cycle in the original tournament. The induction hypothesis gives a forward order of the remaining vertices. Prepend \(s\) to that order. Every arc from \(s\) points outward, since \(s\) has no incoming arc; all arcs among the other vertices point forward by their order. Hence the resulting order is forward, completing the induction. \(\square\)
The proof gives a procedure: repeatedly find and remove a source, then list the vertices in the order they were removed. The theorem shows why it works for tournaments. If the procedure reaches a nonempty remainder with no source, the source-existence argument shows that remainder contains a directed cycle, so it cannot be acyclic.
Proof. If a tournament has a forward order and \(u\to v\) and \(v\to w\), then \(u\) must appear before \(v\), and \(v\) before \(w\). Thus \(u\) appears before \(w\). Since each pair has exactly one arc, its direction is \(u\to w\); the tournament is transitive. Conversely, suppose the tournament is transitive. A directed cycle would give \(v_1\to v_2\) and \(v_2\to v_3\), hence \(v_1\to v_3\). Continuing around a cycle would force, in particular, both \(v_1\to v_2\) and \(v_2\to v_1\), which is impossible. Thus the tournament is acyclic, so the theorem supplies a forward order. Finally, if two forward orders differed, there would be a pair \(u,v\) appearing in opposite relative orders: one order would require \(u\to v\), the other \(v\to u\). A tournament cannot have both arcs. Therefore the forward order is unique. \(\square\)
Worked Examples
Worked Example: Constructing the Order by Source Removal
Let \(V=\{a,b,c,d\}\) and let the arcs be \(a\to b,\ a\to c,\ a\to d,\ b\to c,\ b\to d,\ c\to d\). This is a tournament because each of the \(\binom{4}{2}=6\) vertex pairs occurs exactly once. Apply source removal.
| Remaining vertices | Incoming-arc counts in the remainder | Source removed |
|---|---|---|
| \(\{a,b,c,d\}\) | \(a:0,\ b:1,\ c:2,\ d:3\) | \(a\) |
| \(\{b,c,d\}\) | \(b:0,\ c:1,\ d:2\) | \(b\) |
| \(\{c,d\}\) | \(c:0,\ d:1\) | \(c\) |
| \(\{d\}\) | \(d:0\) | \(d\) |
For instance, initially \(a\) has no incoming arcs, \(b\) has the one incoming arc \(a\to b\), \(c\) has \(a\to c\) and \(b\to c\), and \(d\) has \(a\to d,\ b\to d,\ c\to d\). After removing \(a\), the remaining arcs are \(b\to c,\ b\to d,\ c\to d\); their incoming counts are \(0,1,2\). The next two rows follow from the remaining arcs \(c\to d\), then no arcs.
The output is \(a,b,c,d\). Checking the original list, the arcs point forward in this order: \(a\to b,\ a\to c,\ a\to d,\ b\to c,\ b\to d,\ c\to d\). There are six arcs, as required because each of four vertices forms a pair with each of the other three, counted once: \(4\cdot3/2=6\). Thus the list checks all pairs and the tournament is transitive and acyclic.
Worked Example: A Tournament with No Forward Order
Let \(V=\{a,b,c\}\) and \(E=\{a\to b,\ b\to c,\ c\to a\}\). There are three vertex pairs and the three listed arcs orient each pair exactly once, so this is a tournament.
The incoming-arc counts are \(\deg^-(a)=1\), from \(c\to a\); \(\deg^-(b)=1\), from \(a\to b\); and \(\deg^-(c)=1\), from \(b\to c\). Thus no vertex is a source. More directly, the arcs form the directed cycle \(a\to b\to c\to a\), so the tournament is not acyclic and, by the theorem, has no forward order.
Check: If a forward order existed, \(a\to b\) would require \(a\) before \(b\), \(b\to c\) would require \(b\) before \(c\), and \(c\to a\) would require \(c\) before \(a\). Together these give \(a\) before \(b\) before \(c\) before \(a\), an impossibility. The direct order test agrees with the cycle test.
Worked Example: A Four-Vertex Tournament with a Directed Triangle
Let \(V=\{a,b,c,d\}\) and let \(E=\{a\to b,\ b\to c,\ c\to a,\ a\to d,\ d\to b,\ c\to d\}\). The pairs \(ab,bc,ac,ad,bd,cd\) each occur once, so this is a tournament with \(4\cdot3/2=6\) arcs.
The vertices \(a,b,c\) form the directed triangle \(a\to b\to c\to a\). Hence the tournament is not acyclic and has no forward order. The incoming-arc counts confirm that source removal cannot begin: \(a\) has one incoming arc, \(c\to a\); \(b\) has two, \(a\to b\) and \(d\to b\); \(c\) has one, \(b\to c\); and \(d\) has two, \(a\to d\) and \(c\to d\). The total is \(1+2+1+2=6\), which agrees with the six listed arcs, each counted once at its head.
Check: The failure is not caused by an omitted pair or an incorrect arc count: all six pairs have exactly one orientation. It is the directed triangle that prevents the pairwise directions from being arranged consistently in a forward order.
Directed Triangles and a Common Pitfall
Proof. If a tournament is acyclic, it has no directed triangle because a directed triangle is itself a directed cycle. For the converse, suppose the tournament contains a directed cycle, and choose one of minimum length \(k\). If \(k=3\), there is a directed triangle. Suppose \(k\ge4\), and write the cycle as \(v_1\to v_2\to\cdots\to v_k\to v_1\). The pair \(v_1,v_3\) has exactly one orientation. If \(v_3\to v_1\), then \(v_1\to v_2\to v_3\to v_1\) is a directed triangle. If \(v_1\to v_3\), then \(v_1\to v_3\to v_4\to\cdots\to v_k\to v_1\) is a directed cycle of length \(k-1\), contradicting the minimality of \(k\). Thus any directed cycle in a tournament implies a directed triangle. Therefore a tournament with no directed triangle is acyclic. \(\square\)
A common mistake is to use the source argument for an arbitrary digraph, without checking the tournament hypothesis. For example, take two vertices \(u,v\) and the arcs \(u\to v,\ v\to u\). Under the definition here, this digraph has no directed cycle: its closed walk has length \(2\), below the required length \(3\). Yet both vertices have an incoming arc, so there is no source. The argument in the characterization works for tournaments because they cannot have a directed closed walk of length \(2\): opposite arcs are forbidden. When applying source removal, check that the digraph is a tournament; do not silently transfer the claim to all digraphs.
The characterization is useful because it turns a global ordering question into a structural test. A forward order certifies acyclicity by showing every arc moves one way through the list. Conversely, source removal constructs that certificate when the tournament is acyclic. And to show a tournament is not transitive, one directed triangle is enough. These tests concern consistency of orientations; they do not require searching through every possible ordering.
Check Your Understanding
Use the definitions and results above to answer the following questions.
- Give a forward order for the tournament on \(\{1,2,3\}\) with arcs \(1\to2,\ 1\to3,\ 2\to3\), and verify it by checking every arc.
- For the tournament with arcs \(1\to2,\ 2\to3,\ 3\to4,\ 4\to1,\ 1\to3,\ 2\to4\), find a directed triangle or give a forward order.
- Why must a nonempty acyclic tournament have a source? Identify the role of the tournament hypothesis in the proof.
- Prove that if a tournament has a forward order, then no pair of distinct forward orders can exist.
- Explain why the two-vertex digraph with arcs in both directions does not contradict the source result for acyclic tournaments.