---
title: "Matching: Definitions and Duality"
summary: Matchings, covers, and independent sets on one page — plus the two theorems that turn searching into proving.
difficulty: core
tags: [matching, duality]
prereq: [foundations/bipartite, flow/cuts]
see: [matching/bipartite, flow/mincut-models]
demo: matching
---

:::definition label="The vocabulary"
A **matching** $M \subseteq 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.
:::

:::props title="Three trivialities you will use constantly"
- maximal $\ne$ 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 $\alpha(G) + \tau(G) = n$;
- every matching edge needs its own cover vertex: $|M| \le |C|$ for every matching $M$ and every cover $C$. In particular a **perfect matching certifies $\tau \ge n/2$**.
:::

:::theorem title="Kőnig's theorem (bipartite)"
In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. (Proof, and the algorithm: @matching/konig.)
:::

:::note title="Why the bipartite restriction is doing the work"
For a triangle $K_3$: 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 (@matching/general-matching). Duality with no gap is a bipartite phenomenon — the same reason LP duality is clean for network matrices.
:::

:::theorem title="Berge's characterisation (every graph)"
$M$ is a maximum matching iff there is no **$M$-augmenting path**: a path whose endpoints are unmatched and whose edges alternate $\notin M, \in M, \notin M, \dots$
:::

:::proof
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 \mathrel{\triangle} M'$: every vertex has degree $\le 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. ∎
:::

:::demo id="matching" caption="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."
:::

:::props title="The map of the chapter"
- @matching/bipartite — DFS augmenting paths (Kuhn's algorithm), $O(VE)$, 10 lines,
- @matching/hopcroft-karp — BFS-layered multi-augmentation, $O(E\sqrt V)$,
- @matching/konig — minimum cover, maximum independent set, and minimum path cover from the same run,
- @matching/hungarian — weighted assignment, $O(n^3)$,
- @matching/applications — tilings, domino problems, posets, "place rooks", grid-cut problems,
- @matching/general-matching — blossoms: why odd cycles need a contraction, and the $O(V^3)$ implementation.
:::

:::problems
- [[CSES 1696]] School Dance | https://cses.fi/problemset/task/1696 | core | the bipartite matching statement with output pairs
- [[CSES 1130]] Tree Matching | https://cses.fi/problemset/task/1130 | easy | maximum matching on a tree is DP, not flow — know both
:::