---
title: "The Extremal Principle"
summary: "Assume a counterexample is smallest/largest/closest and let it contradict itself — the single most useful proof move in graph olympiads."
difficulty: hard
tags: [proofs, olympiad]
see: [foundations/walks, euler/hamilton-theorems]
---

:::idea title="The move, stated once"
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:

:::example title="1. Longest path ends where the degrees are"
In a graph with minimum degree $\delta$, a longest path $P = v_0 v_1 \dots v_\ell$ has every neighbour of $v_0$ on $P$. Hence $G$ contains a cycle of length $\ge \delta + 1$: take the far neighbour $v_i$ of $v_0$, the cycle $v_0 v_1 \dots v_i v_0$ has length $i+1 \ge \delta + 1$.
*Where extremality was used:* "every neighbour is on $P$", otherwise $P$ extends.
:::

:::example title="2. Maximal matching is a 2-approximation for maximum matching"
A **maximal** matching (cannot add an edge) has size $\ge \frac{1}{2}|\text{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.
:::

:::example title="3. Minimal counterexample buys you structure"
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 \ge n-1$. Minimality did the bookkeeping; the tree argument finished it.
:::

:::example title="4. Extremal vertex in a proof by contradiction about distances"
"Show a graph with diameter $d$ has at most $\lfloor d/2 \rfloor$ … " — always start by taking $a,b$ with $\operatorname{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 (@trees/bfs), 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 (@trees/diameter).
- **Greedy MST**: choose the lightest safe edge; correctness is an exchange argument over an extremal (lightest) spanning tree (@advanced-tree/mst).
- **Centroid**: pick the vertex minimising the largest remaining component — extremality gives the $\le n/2$ bound that makes centroid decomposition $O(n\log n)$ (@advanced-tree/centroid).
- **Sweep-line / sorting**: Kruskal, Prim, "process edges by weight" are extremal choices in a loop.

:::warning title="Maximal vs maximum"
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.
:::

:::exercise title="Practise the move"
1. 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?)
2. Prove that in any tournament, a vertex of maximum out-degree is a "2-king" (@directed/tournament).
3. Prove: if $\sum_v \binom{\deg(v)}{2} > \binom{n}{2}$ then $G$ contains a 4-cycle. (Count length-2 paths between pairs — extremal in the sense of "too many of something".)
:::