Chapter 4
Proof Toolkit
Olympiad graph theory is barely about algorithms; it is about three proof moves used relentlessly. Name them and you can attack a problem with no idea where to start.
3 pages2,045 words4 problems0 interactive
1The Extremal PrincipleAssume a counterexample is smallest/largest/closest and let it contradict itself — the single most useful proof move in graph olympiads.2Double Counting and AveragingCount one set two ways, then compare — the source of the handshaking lemma, Turán-type bounds, and most "prove that m ≤ …" problems.3Contraction, Induction and LiftingShrink the graph, solve the smaller one, un-shrink — with the two rules that decide whether the move is legal.