Chapter 4 · Proof Toolkit
Contraction, Induction and Lifting
Shrink the graph, solve the smaller one, un-shrink — with the two rules that decide whether the move is legal.
Contracting an edge uv (write G/uv) replaces u,v by a single vertex and deletes loops and parallel copies. It is the standard way to do induction on n while keeping connectivity-type properties intact — and the standard way to build a data structure (DSU, Disjoint Set Union (Union–Find)).
- Preservation: the property you induct on must survive contraction, or you must contract something chosen to make it survive (e.g. contract an edge of a maximum matching to preserve "has a perfect matching" for the smaller graph).
- Lifting: after you have the object in G/uv you must be able to un-shrink it into G and pay at most a constant. If the answer for G is "answer for G/uv plus maybe one", you have a theorem; if un-shrinking can destroy the whole construction, you have a hole.
Induct on m. Take a cycle C (exists: δ ≥ 2 after removing nothing… precisely: bridgeless ⇒ each edge lies on a cycle). Orient C cyclically and contract it: G/V(C) is still bridgeless (contracting cannot create a bridge out of non-bridges), has fewer edges, so by induction it has an orientation with all degrees even; combining with the cycle orientation, every vertex of G has deg^+ = deg^- (the vertices of C gained one in and one out). ∎ Note where rule 2 lives: the merged vertex's evenness follows because the cycle contributed exactly one in and one out to each of its vertices — this is the step that fails for a path instead of a cycle.
To prove χ(G) ≤ Δ + 1 by induction on n+m, pick non-adjacent x,y with a common neighbour of minimum degree (exists when G is not complete, else Brooks handles it). Form G' = G + xy — it has the same maximum degree and χ(G) ≤ χ(G') — colour G' by induction, then delete xy. The colouring lifts unchanged, because deleting an edge never invalidates a proper colouring. That asymmetry (add edges when colouring, delete edges when studying connectivity) is the reason the same proof technique proves completely different theorems.
#Contraction in algorithms
Four places the same move appears as code
- Kruskal: each accepted edge contracts two super-vertices;
find()answers "which class is this vertex in now". The algorithm literally walks a sequence of contractions (Minimum Spanning Tree). - Karger's min-cut: contract random edges until two vertices remain; the remaining cut is uniform among the cuts of the original graph. O(n2 log n) repetitions → constant success probability (Cuts and Flows).
- Biconnected/block decomposition: contract each 2-edge-connected component; what remains is a tree (the bridge tree), and answers to "how many edges on the path" become tree-distance queries (Connectivity, Bridges, Articulation Points).
- Treewidth / elimination: contract (or eliminate) a low-degree vertex, recurse, then lift the solution — the reason degeneracy-ordered DP works on sparse graphs.
#Induction that goes the other way: lifting
"Lift" here means: build the object for G from the object for G - v, for a vertex v you chose. Choosing which v to remove is the entire skill:
- need a leaf? a tree always has one (Trees: Six Definitions of One Object) — remove it, induct, re-attach;
- need degree ≤ bar d? average-degree gives one (Double Counting and Averaging) — this is why greedy colouring and α ≥ n/(bar d+1) work;
- need "small remaining graph"? contract a cycle, or a maximal path;
- need both endpoints of the diameter? root at one and remove the other.
Counting problems. "How many spanning trees does G have?" splits as τ(G) = τ(G-e) + τ(G/e) — a genuine recurrence, but it is exponential unless you turn it into a determinant (The Matrix–Tree Theorem). Similarly, counting matchings or independent sets does not survive contraction without carrying a polynomial in a variable; when you see that, stop and look for the structural condition (bipartite? bounded treewidth? small n?) instead.