Chapter 4 · Proof Toolkit
The Extremal Principle
Assume a counterexample is smallest/largest/closest and let it contradict itself — the single most useful proof move in graph olympiads.
To prove something holds for every object, pick an object where the relevant quantity is extreme (longest path, maximal matching, vertex closest to all others, the component with most edges, the smallest counterexample) and show that the extremality forces the extra structure you want — because if it were missing, you could extend, improve, or shrink, contradicting the choice.
Four worked shapes, all of them used elsewhere in this book:
In a graph with minimum degree δ, a longest path P = v0 v1 … v_ℓ has every neighbour of v0 on P. Hence G contains a cycle of length ≥ δ + 1: take the far neighbour vi of v0, the cycle v0 v1 … vi v0 has length i+1 ≥ δ + 1. Where extremality was used: "every neighbour is on P", otherwise P extends.
A maximal matching (cannot add an edge) has size ≥ (1)/(2)|maximum|: every edge of the maximum matching touches an edge of the maximal one, and one edge of the maximal one covers at most two of them. So the greedy "take any edge, delete its endpoints" is a 2-approximation — and, more usefully in contests, a maximal matching of size k bounds everything: 2k is a vertex cover, and if k < n/2 some vertex is unmatched.
Claim: every connected graph on n vertices has at least n-1 edges. Suppose a counterexample exists and choose G with m minimal among all counterexamples. No edge of G is a bridge: deleting one keeps connectivity, so G - e is a connected graph with m-1 < n-1 edges — a smaller counterexample, contradiction. Hence every edge lies on a cycle; but a graph in which every edge lies on a cycle cannot be minimal under edge deletion, and a direct check gives the same: pick a BFS tree, it already has n-1 edges, so m ≥ n-1. Minimality did the bookkeeping; the tree argument finished it.
"Show a graph with diameter d has at most ⌊ d/2 ⌋ … " — always start by taking a,b with dist(a,b) = d (the diameter pair) and root everything at a. Layers from a then contain b in the last one, and any edge can only join adjacent layers, which is exactly the structure you needed. This is the same trick as BFS-level arguments (Breadth-First Search), so extremal + BFS is a compound move worth memorising.
#Extremal algorithm design
The principle is not only for existence proofs; it generates algorithms:
- Tree diameter: farthest-from-anything is an endpoint — extremality, twice (Tree Diameter in Two Passes).
- Greedy MST: choose the lightest safe edge; correctness is an exchange argument over an extremal (lightest) spanning tree (Minimum Spanning Tree).
- Centroid: pick the vertex minimising the largest remaining component — extremality gives the ≤ n/2 bound that makes centroid decomposition O(nlog n) (Centroid Decomposition).
- Sweep-line / sorting: Kruskal, Prim, "process edges by weight" are extremal choices in a loop.
Maximal = cannot be extended. Maximum = largest possible. Almost every "greedy is a 2-approximation" argument gives maximal, and every NP-hard optimisation problem asks for maximum. Confusing the two produces a wrong proof that looks right, which is the worst kind of bug in a written solution.
- Prove every graph with average degree bar d has a subgraph of minimum degree > bar d/2. (Delete vertices of small degree; what does the last surviving graph look like?)
- Prove that in any tournament, a vertex of maximum out-degree is a "2-king" (Tournaments).
- Prove: if ∑v C(deg(v), 2) > C(n, 2) then G contains a 4-cycle. (Count length-2 paths between pairs — extremal in the sense of "too many of something".)