---
title: "Tournaments"
summary: Every pair plays once: scores, the king chicken theorem, and the Hamiltonian path you get for free.
difficulty: hard
tags: [directed, existence, olympiad]
see: [proofs/extremal, euler/hamilton-theorems]
---

A **tournament** on $n$ vertices orients each of the $\binom{n}{2}$ pairs exactly one way — a "round robin" where every pair plays and there are no draws.

:::props title="Instant facts"
- $m = \binom{n}{2}$, and $\sum_v \deg^{+}(v) = \binom{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 $s_1 \le \dots \le s_n$ is a score sequence $\iff$ $\sum_{i \le k} s_i \ge \binom{k}{2}$ for all $k$, with equality at $k = n$.
- A tournament is **transitive** ($a \to b \to c \Rightarrow a \to c$) $\iff$ it has no directed 3-cycle $\iff$ its score sequence is $0,1,\dots,n-1$.
:::

:::theorem title="Every tournament has a Hamiltonian path"
There is an ordering $v_1, \dots, v_n$ with $v_i \to v_{i+1}$ for all $i$.
:::

:::proof
Induction. Insert a new vertex $x$ into an existing Hamilton path $v_1 \to \dots \to v_n$. If $v_1 \leftarrow x$, prepend; if $v_n \to x$, append. Otherwise there is an index with $v_i \to x \to v_{i+1}$: such an $i$ exists because the predicate "$v_j \to 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.

:::theorem title="King 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 \to c$ and no edge $c \to u$ with a 2-hop, i.e. $c \to u$ is false and for all $w$ with $c \to w$ we have $u \to w$. Then every out-neighbour of $c$ is also an out-neighbour of $u$, *plus* $u \to c$ itself, so $\deg^{+}(u) \ge \deg^{+}(c) + 1$ — contradicting maximality of $c$. ∎
:::

:::example title="Contest-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
:::theorem title="Rédei / Camion"
A tournament has a Hamiltonian **cycle** $\iff$ it is strongly connected.
:::

:::proof
$\Rightarrow$ clear. $\Leftarrow$ Take a longest cycle $C$. If $C$ misses some vertex $x$: since the tournament is strong, there are $u, v \in C$ with $u \to x \to v$ (otherwise the sets $\{y \in C : y \to x\}$ and $\{x \to 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 \to x \to v$ with $v$ immediately before $u$ on $C$ — insert $x$, contradicting maximality. ∎
:::

:::figure src="Simple_Directed_Graph.svg" caption="A 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."
:::

:::exercise title="Prove it yourself"
1. Show that a tournament is transitive $\iff$ 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.
:::