A Bit of History
British mathematician Philip Hall proved the theorem now bearing his name in 1935, phrased in terms of a whimsical "marriage problem": given a group of people, each willing to marry only certain acceptable partners, when can everyone be matched simultaneously? A parallel line of work came from Hungary — Dénes Kőnig proved his own foundational matching-cover duality theorem in 1931, building on earlier joint work with Jenő Egerváry — independent enough of Hall's marriage framing that both results are now taught side by side as two views of the same underlying structure. Two decades later, in 1957, Claude Berge supplied the algorithmic key that made matching theory computationally tractable: a clean characterization of when a matching is already maximum, based entirely on the existence (or absence) of a specific kind of path.
Matching Fundamentals
A matching \(M \subseteq E\) is a set of edges, no two of which share a vertex. A maximum matching has the largest possible number of edges; a perfect matching covers every vertex (only possible when \(|V|\) is even). In graph-theoretic terms first used in Part 12, a perfect matching is exactly a 1-factor — a spanning subgraph that is 1-regular (every vertex has degree exactly 1).
Hall's Marriage Theorem
For a bipartite graph with parts \(X\) and \(Y\), a matching saturating every vertex of \(X\) exists if and only if Hall's condition holds: for every subset \(S \subseteq X\), the neighborhood \(N(S)\) (every vertex in \(Y\) adjacent to some vertex in \(S\)) satisfies \(|N(S)| \geq |S|\).
Analogy: No Group Can Be "Collectively Stuck"
Translating back to the marriage framing: if any group of \(k\) people, considered together, is only acceptable to fewer than \(k\) total potential partners across the whole group, that group can never all be matched — someone in it is guaranteed to be left out no matter how cleverly you arrange things. Hall's theorem says this "collectively stuck" obstruction is the only possible obstruction — if no such group exists, a full matching is always achievable.
König's Theorem
In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover (Part 15's vocabulary — the smallest set of vertices touching every edge). This is a genuinely deep duality: every bipartite graph's hardest-to-match structure is exactly captured by its smallest possible "vertex blocker" set, with no gap between the two numbers — a direct bipartite special case of the max-flow min-cut theorem from Part 15 (matching = flow, vertex cover = cut).
Berge's Augmenting Path Theorem
An alternating path alternates between edges not in \(M\) and edges in \(M\); an augmenting path is an alternating path whose both endpoints are unmatched. Berge's theorem (1957): a matching \(M\) is maximum if and only if no augmenting path exists relative to \(M\). This single fact is the engine behind every matching algorithm in this deep-dive batch: repeatedly find an augmenting path, flip which edges are "in" versus "out" of the matching along it (this always increases the matching size by exactly one), and stop only when no augmenting path remains — at which point Berge's theorem guarantees the matching found is provably maximum.
Matching via Max-Flow
Part 15 previewed this reduction; here it is fully spelled out. Add a super-source \(s\) connected to every vertex in \(X\) with capacity 1, direct every original edge from \(X\) to \(Y\) with capacity 1, and connect every vertex in \(Y\) to a super-sink \(t\) with capacity 1. The maximum flow from \(s\) to \(t\) in this network exactly equals the size of a maximum bipartite matching — and since all capacities are integers, the max-flow theorem (specifically, the integrality of optimal flows on integer-capacity networks) guarantees the optimal flow itself corresponds directly to a valid matching, not just a matching-sized number.
Faster Than Generic Max-Flow
Because every capacity in this construction is exactly 1, generic max-flow algorithms (Ford-Fulkerson, Edmonds-Karp — upcoming deep dives) can be specialized into much faster matching-specific algorithms. The Hopcroft-Karp algorithm (1973, an upcoming deep dive) exploits this structure to solve bipartite matching in \(O(E\sqrt{V})\) — asymptotically faster than running Edmonds-Karp's generic \(O(VE^2)\) unmodified.
Real-World Applications
Medical Residency Matching (The National Resident Matching Program)
Every year, tens of thousands of new doctors in the United States are matched to residency programs using an algorithm rooted directly in matching theory — the deferred-acceptance algorithm (a close relative of Hall's-condition-satisfying matchings, extended to handle preference rankings on both sides rather than simple yes/no compatibility). The same family of techniques underlies kidney-exchange matching programs (pairing incompatible donor-patient pairs into compatible chains) and any large-scale "assign people to slots respecting mutual preferences" system.
Exercises
- Construct a small bipartite graph violating Hall's condition (some subset \(S\) with \(|N(S)| < |S|\)), and confirm no matching saturating \(X\) exists.
- Verify König's theorem by hand on \(K_{3,3}\) minus one edge: find a maximum matching and a minimum vertex cover, and confirm their sizes match.
- Given a bipartite matching, trace an augmenting path by hand and flip the matching/non-matching edges along it, verifying the matching size increases by exactly one.
- Challenge: Implement bipartite matching via the max-flow reduction (reusing any max-flow implementation you build in the Ford-Fulkerson deep dive) and verify it matches a matching found by direct augmenting-path search on the same graph.
Conclusion & Next Steps
Hall's condition, König's duality, and Berge's augmenting-path characterization together give a complete theory of bipartite matching — existence, an exact duality with vertex covers, and a concrete algorithmic engine. With flows and matchings both established, the series now turns to a different kind of structure entirely: graphs that can be drawn on paper without any edges crossing.
Next in the Series
In Part 17: Planar Graphs & Topological Graph Theory, the series turns from flows and matchings to a different kind of structure entirely: graphs that can be drawn on paper without any edges crossing.