Chapter 13 · Matching
Matching: Definitions and Duality
Matchings, covers, and independent sets on one page — plus the two theorems that turn searching into proving.
A matching M ⊆ E is a set of edges no two of which share an endpoint. Its size is |M|; it is perfect if every vertex is matched, maximal if no edge can be added, maximum if no larger matching exists. A vertex cover is a set C of vertices touching every edge. An independent set is a set of vertices with no edge inside it.
Three trivialities you will use constantly
- maximal ≠ maximum: a greedy maximal matching is a 2-approximation of the maximum (every edge of a maximum matching touches a distinct chosen edge), and that factor is tight for the greedy;
- in any graph, the complement of a vertex cover is an independent set, so α(G) + τ(G) = n;
- every matching edge needs its own cover vertex: |M| ≤ |C| for every matching M and every cover C. In particular a perfect matching certifies τ ≥ n/2.
In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. (Proof, and the algorithm: Kőnig's Theorem and Minimum Covers.)
For a triangle K3: max matching =1, min cover =2. The odd cycle is exactly the obstruction, and the general-graph answer is Berge's: the defect is measured by Tutte's condition (General Matching and Blossoms). Duality with no gap is a bipartite phenomenon — the same reason LP duality is clean for network matrices.
M is a maximum matching iff there is no M-augmenting path: a path whose endpoints are unmatched and whose edges alternate ∉ M, ∈ M, ∉ M, …
If an augmenting path exists, symmetric-differencing M with it (flip matched/unmatched along the path) gives a matching of size |M|+1. Conversely, if a larger matching M' exists, look at the subgraph M △ M': every vertex has degree ≤ 2 and components alternate edges of M and M', so the components are even cycles and paths. Since |M'| > |M|, some path component has one more M'-edge than M-edge — its endpoints are unmatched in M (an endpoint matched in M would need its M-edge present, giving the component an extra M edge or degree 3). That path is an augmenting path. ∎
Greedy vs. augmenting: find an augmenting path on the left picture and watch the matching grow by one; the right picture is what a maximal-but-not-maximum matching looks like.
The map of the chapter
- Bipartite Matching (Kuhn's Algorithm) — DFS augmenting paths (Kuhn's algorithm), O(VE), 10 lines,
- Hopcroft–Karp — BFS-layered multi-augmentation, O(E√V),
- Kőnig's Theorem and Minimum Covers — minimum cover, maximum independent set, and minimum path cover from the same run,
- The Hungarian Algorithm — weighted assignment, O(n3),
- Matching Applications — tilings, domino problems, posets, "place rooks", grid-cut problems,
- General Matching and Blossoms — blossoms: why odd cycles need a contraction, and the O(V3) implementation.