Chapter 14
Special Topics
A toolbox of one-off ideas that keep showing up in finals: Euler's formula, greedy colouring bounds, the implication graph, hitting times, and Ramsey's unavoidable order.
7 pages8,037 words12 problems0 interactive
1Planarity and Euler's Formulam <= 3n - 6 and what it buys you, the Kuratowski obstruction, the linear-time tests you can actually run, and why planarity keeps appearing in olympiad graph problems.2Degree Sequences and Graphical SequencesThe handshaking lemma's consequences, Erdős–Gallai and Havel–Hakimi — which one to use when you must build the graph.3Graph ColouringGreedy bounds, Brooks' and Reed's theorems, chromatic number versus clique number, and the three colouring problems that are actually solvable.42-SATThe implication graph, the "x and not x in one SCC" criterion, and the assignment read off the condensation order — with the linear-time proof.5Random Walks and Cover TimesHitting times as linear equations, commute-time bounds via effective resistance, and the walk-based algorithms that actually get used.6Ramsey Theory on GraphsR(3,3)=6 and R(4,4)=18 with complete elementary proofs, the recursion behind every bound, and the counting argument that explains why the numbers explode.7Independent Sets, Cliques, and TreewidthWhy maximum independent set is hopeless in general, what makes it easy on trees, chordal graphs and bounded-treewidth graphs, and the two approximations that are worth coding.