---
title: "Contraction, Induction and Lifting"
summary: Shrink the graph, solve the smaller one, un-shrink — with the two rules that decide whether the move is legal.
difficulty: hard
tags: [proofs, structural, induction]
see: [foundations/subgraph, structures/dsu, advanced-tree/mst]
---

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, @structures/dsu).

:::idea title="The two legality rules"
1. **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).
2. **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.
:::

:::example title="Every bridgeless graph has an even-degree orientation"
Induct on $m$. Take a cycle $C$ (exists: $\delta \ge 2$ after removing nothing… precisely: bridgeless $\implies$ 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.
:::

:::example title="Colouring: add an edge, colour, delete it"
To prove $\chi(G) \le \Delta + 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 $\chi(G) \le \chi(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
:::props title="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 (@advanced-tree/mst).
- **Karger's min-cut**: contract random edges until two vertices remain; the remaining cut is uniform among the cuts of the original graph. $O(n^2 \log n)$ repetitions $\to$ constant success probability (@flow/cuts).
- **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 (@foundations/connectivity).
- **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:

:::check title="Pick the vertex that makes the smaller instance easy"
- need a leaf? a tree always has one (@trees/properties) — remove it, induct, re-attach;
- need degree $\le \bar d$? average-degree gives one (@proofs/double-count) — this is why greedy colouring and $\alpha \ge 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.
:::

:::warning title="When contraction is a trap"
Counting problems. "How many spanning trees does $G$ have?" splits as $\tau(G) = \tau(G-e) + \tau(G/e)$ — a genuine recurrence, but it is exponential unless you turn it into a determinant (@matrices/matrix-tree). 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.
:::

:::problems
- [[CSES 2101]] New Roads Queries | https://cses.fi/problemset/task/2101 | hard | offline contraction + MST
- [[CF 160D]] Edges in MST | https://codeforces.com/problemset/problem/160/D | core | classify by contraction order
:::