Pairwise comparisons and a directed graph
Suppose every two players meet exactly once and there are no ties. Draw an arrow from the winner to the loser. This model remembers every result, but it need not produce a single ranking: may beat , beat , and beat . The same directed graph can describe any complete collection of asymmetric pairwise comparisons; the players need not have numerical scores.
Definition 5.2.1
(Tournaments, directed paths and cycles)
A tournament is a finite directed graph with no loops and exactly one of and for every pair of distinct vertices . A directed path is a sequence of distinct vertices with every consecutive arrow pointing forward. A Hamiltonian path visits every vertex exactly once. A directed cycle also follows the arrow directions and has distinct vertices apart from its repeated start/end. The outdegree counts vertices to which sends an arrow. We permit the empty tournament; its empty ordering is a Hamiltonian ordering by convention. For reachability, a vertex reaches itself by a path of length zero.
Every tournament has a Hamiltonian path
The statement is surprising because no individual vertex need beat all the others. Its proof inserts one vertex into an already ordered path, rather than trying to rank everyone by outdegree.
Theorem 5.2.2
(Directed Hamiltonian path in a tournament)
Every finite tournament admits an ordering with for every .
Proof
(Insert the next vertex)
Use induction on the number of vertices. The empty or one-vertex tournament is immediate. Delete a vertex and, by induction, arrange the remaining vertices in a directed path . If , put first. Otherwise, find the largest index for which . If , append . If , maximality says does not point to ; the tournament rule therefore gives . Insert between and . Only the old adjacency is replaced, by , so the new ordering is a directed path through every vertex.
Proof X-ray
Why the last in-neighbor marks a usable gap
The induction hypothesis is applied to the tournament with deleted, which is again a tournament: the class is closed under deleting vertices, and the proof depends on that. What the insertion needs is a switch along the path, a position where and , or one of the two ends. The case split guarantees one. If , the switch is before the start. Otherwise , so the set of indices with is nonempty and has a largest element . Either and goes at the end, or does not point to .
That last step is the only use of the tournament axiom: a pair that is not must be . In a general directed graph the pair might be nonadjacent and the gap would not close. Maximality is a convenient way to find a switch; it is not the only one, and in the five-vertex example the first in-neighbor also works, because . The step closes because only one consecutive pair changes and both new arrows have been checked.
This constructive proof checks at most the current path length when inserting each vertex. With constant-time access to each pair's direction, it needs direction checks. Nor does a Hamiltonian path assert that every earlier vertex beats every later one; only consecutive arrows are required.
Common mistake
(Ordering by outdegree instead of inserting)
Listing the vertices in non-increasing order of outdegree need not give a directed path when ties are broken arbitrarily. In the tournament on with , , , , , , the outdegrees are , and the order is non-increasing; but the arrow between and is , so the first step already points backwards. The insertion proof never consults outdegrees.
Common mistake
(Upgrading the path to a Hamiltonian cycle)
The theorem proves existence of a path, not a cycle. In the transitive tournament , , , the ordering is a Hamiltonian path, but has outdegree zero and cannot be left, so no directed cycle passes through it. A transitive tournament has no directed cycle at all.
Worked example 5.2.3
(Insertion can expose a cycle)
Let , , and . Start with the path . Because , append to get . This is Hamiltonian, although the arrow goes backwards relative to the ordering. It also closes a directed triangle; a path ordering need not be a consistent ranking of every comparison.
Worked example 5.2.4
(Inserting inside a path)
Take five vertices . Among , let the arrows be , , , , , and . Thus is a directed path. Let the four comparisons involving be , , , and . These ten arrows specify every pair.
Scan the existing path and note the vertices that point to : they are and . The last is , in position three; its successor is . Since , insert in that gap. The resulting path has consecutive arrows , , , and . In particular, does not invalidate the construction: arrows between nonconsecutive vertices need not point forward. The rule examines all relevant positions because the directions toward need not occur in a single uninterrupted block.
When is the comparison a consistent ranking?
Definition 5.2.5
(Transitive tournament and directed triangle)
A tournament is transitive if and always imply for distinct . A directed triangle is a directed cycle of three distinct vertices.
The theorem below shows that, equivalently, the vertices of a transitive tournament can be ordered so every arrow points from an earlier vertex to a later vertex.
Theorem 5.2.6
(Three ways to recognize transitivity)
For a finite tournament, the following are equivalent: (1) it is transitive; (2) it has no directed triangle; (3) it has an ordering in which every arrow points forward.
Proof
(From local triples to a global order)
If transitivity holds, a directed triangle is impossible, since the first two arrows would require . Now assume there is no directed triangle. Choose a Hamiltonian path . We show every arrow points forward for by induction on . The adjacent case is the path property. For a larger gap, induction gives and the path gives . The reverse arrow would form a directed triangle, so . Finally, an all-forward ordering is transitive: two consecutive comparisons and force before before , hence .
The forward ordering is unique when the tournament is transitive: for any two vertices their arrow forces which must occur first. For vertices its outdegrees are in that order. More generally, in every tournament the sum of outdegrees is , because each pair contributes exactly one outgoing arrow. The sum alone does not characterize transitivity: every tournament on the same number of vertices has that sum.
Counterexample mode
A path is not a global ranking
In the three-vertex directed cycle, is a Hamiltonian path, but . All three outdegrees equal one. Thus sorting by outdegree cannot by itself turn arbitrary results into an order with every arrow forward, and existence of a Hamiltonian path does not imply acyclicity.
Shortening a directed cycle
The absence of a directed triangle also rules out every longer directed cycle. Here is a constructive way to see why the special tournament hypothesis matters: any two nonconsecutive vertices on a cycle have an arrow between them, so we can use that arrow as a shortcut.
Lemma 5.2.7
(A directed cycle contains a directed triangle on its vertices)
In a tournament, every directed cycle with contains three of its vertices that form a directed triangle.
Proof
(Shortcut across the cycle)
Suppose is a directed cycle, with . If , it is already a triangle. For , inspect the arrow between and . If it is , the first three vertices form the directed triangle . Otherwise it is , so we can omit and obtain the shorter directed cycle . Its vertices are still distinct. Repeat until a triangle appears; the cycle length decreases at every shortcut, so the process terminates.
This proves more than the existence of some triangle elsewhere in the tournament: its vertices can be chosen from the original cycle. It does not say that every triple on that cycle is a directed triangle. In an arbitrary directed graph the shortcut may be absent, so the same argument need not apply.
A short route from a high-outdegree vertex
Definition 5.2.8
(King)
A vertex is a king if every vertex is reachable from by a directed path of length at most two. This includes itself via the length-zero path. It does not require to beat everyone directly.
Theorem 5.2.9
(A maximum-outdegree vertex is a king)
In every nonempty finite tournament, any vertex of maximum outdegree reaches each other vertex in at most two directed edges.
Proof
(Compare outgoing neighbors)
Choose a maximum-outdegree vertex . If , there is nothing to prove. Otherwise . Suppose no vertex satisfies . Every outgoing neighbor of is distinct from and must therefore satisfy . In addition, . Hence has at least outgoing neighbors, contradicting maximality. Some such exists and is the required path.
Counterexample mode
Maximum outdegree is not enough outside tournaments
One might expect a vertex of maximum outdegree to reach every vertex within two steps in any directed graph. Take vertices with only the arrows , and . Then is maximum, yet no arrow enters , so cannot reach at all. The proof breaks at “otherwise ”: here neither arrow between and exists. The theorem needs the tournament axiom that every pair is joined in exactly one direction.
Worked example 5.2.10
(A king need not win every comparison)
In the directed triangle , all outdegrees are one and each vertex is a king. For instance, reaches via , even though beats directly. A king is a statement about reachability, not an undefeated player.
Worked example 5.2.11
(A king with smaller outdegree)
On , take , , , , , and . The outdegrees of are respectively . Nevertheless is a king: it reaches directly and reaches and along and . Thus the theorem gives a reliable way to find a king, but its converse is false: being a king need not imply maximum outdegree.
Practice
Quick check
(The arrows on are , , , , and . Find a Hamiltonian path, a directed triangle and a king.)
Start the path at the vertex that beats .
Solution · Answer
is a Hamiltonian path. The arrows form a directed triangle. Vertex is a king: it reaches directly and reaches through (or ).
Quick check
(A tournament has four vertices and outdegrees . Must it be transitive? Explain.)
Remove the vertex of outdegree three first.
Solution · Answer
Yes. The vertex of outdegree three beats all others; remove it. In the remaining three vertices the original outdegrees are unchanged because their edge to the removed vertex was incoming. The vertex of outdegree two beats the remaining two, and the last edge orders those two. Thus all arrows point forward in the order of degrees .
Quick check
(Give a tournament on three vertices with a Hamiltonian path but no vertex of outdegree two. Does it have a king?)
The outdegrees must sum to three.
Solution · Answer
Orient the edges as . The path is Hamiltonian; every vertex has outdegree one. Every vertex is a king, since it reaches the vertex that beats it through the remaining vertex.
Quick check
(A tournament has a directed cycle of some length. Must it have a directed triangle whose vertices belong to that cycle? Give a proof using a shortcut, without assuming that the given cycle itself has length three.)
Look at the arrow between the first and third vertices of the cycle.
Solution · Answer
Yes. If the cycle has length at least four, the arrow between its first and third vertices either completes a triangle with the first two edges or lets us omit the second vertex and obtain a shorter directed cycle. Repeating this step eventually gives a triangle, using only vertices of the original cycle.
Quick check
(Suppose a vertex of a nonempty tournament beats every other vertex. Show that it is the unique king.)
Ask whether any other vertex can reach it at all.
Solution · Answer
Let beat every other vertex. It reaches all vertices in at most one edge, so it is a king. No other vertex can reach by a directed path: the last edge of such a path would have to point into , but all edges incident with point out. Hence is the only king.