GTOIgraph theory, redesigned

Chapter 3 · Directed Graphs

Tournaments

Every pair plays once: scores, the king chicken theorem, and the Hamiltonian path you get for free.

  • hard
  • directed
  • existence
  • olympiad
Read first

A tournament on n vertices orients each of the C(n, 2) pairs exactly one way — a "round robin" where every pair plays and there are no draws.

Instant facts

  • m = C(n, 2), and ∑v deg+(v) = C(n, 2).
  • deg+(v) + deg-(v) = n-1 for every v: out-degree determines in-degree.
  • The score sequence is the multiset of out-degrees; Landau's theorem says s1 ≤ … ≤ sn is a score sequence ⇔ ∑i ≤ k si ≥ C(k, 2) for all k, with equality at k = n.
  • A tournament is transitive (a → b → c ⇒ a → c) ⇔ it has no directed 3-cycle ⇔ its score sequence is 0,1,…,n-1.
TheoremEvery tournament has a Hamiltonian path

There is an ordering v1, …, vn with vi → vi+1 for all i.

Proof

Induction. Insert a new vertex x into an existing Hamilton path v1 → … → vn. If v1 arrow x, prepend; if vn → x, append. Otherwise there is an index with vi → x → vi+1: such an i exists because the predicate "vj → x" is true at j=1 and false at j=n, so it flips somewhere. Splice x in at that i. ∎

The proof also gives the algorithm: binary search for the flip point, insert. O(n log n) per vertex on an adjacency matrix, or O(n) total with the "score insertion sort" — and note the path is not necessarily unique.

TheoremKing chicken (every vertex of max out-degree is a 2-king)

In any tournament, a vertex c with maximum out-degree reaches every other vertex by a path of length at most 2.

Proof

Suppose some u has u → c and no edge c → u with a 2-hop, i.e. c → u is false and for all w with c → w we have u → w. Then every out-neighbour of c is also an out-neighbour of u, plus u → c itself, so deg+(u) ≥ deg+(c) + 1 — contradicting maximality of c. ∎

ExampleContest-shaped use

"Given results of a round robin, find a vertex that beat-or-was-beaten-by-everyone within two steps" — one pass for max out-degree, no search. And "can the n players be ranked so each beat the next?" — always yes, by the Hamiltonian path, which makes it a proof problem, not a search problem.

#Strong tournaments

TheoremRédei / Camion

A tournament has a Hamiltonian cycle ⇔ it is strongly connected.

Proof

⇒ clear. ⇐ Take a longest cycle C. If C misses some vertex x: since the tournament is strong, there are u, v ∈ C with u → x → v (otherwise the sets {y ∈ C : y → x} and {x → y} would separate x from C). Because C is a directed cycle, walking around it must cross from the second set to the first; the crossing pair gives u → x → v with v immediately before u on C — insert x, contradicting maximality. ∎

G A A D D A->D C C D->C B B B->A B->D C->B E E C->E E->B F F F->D F->C
Figure 1A small oriented graph: not every digraph is a tournament (some pairs play both ways here), but the same 'walk around the cycle' argument drives the strong case.
ExerciseProve it yourself
  1. Show that a tournament is transitive ⇔ it has no directed 3-cycle. (Hint: induction on n using the vertex of out-degree 0.)
  2. Prove that in a regular tournament (n odd, all out-degrees (n-1)/2) every vertex lies on a Hamiltonian cycle.
  3. Landau's inequality: prove the "only if" direction by noting that the k smallest scores must beat each other somewhere.