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. The clean mental model is one edge = one pair: once a vertex is used by one matched edge, it cannot participate in another. A vertex incident to an edge of \(M\) is matched (or saturated); otherwise it is unmatched (or free).
Matching means choosing edges that never compete for a vertex
A matching is not trying to connect the whole graph. It is selecting compatible pairs. The only local rule is that a vertex can appear in at most one selected edge.
Memory hook: a matching is a set of non-overlapping handshakes. A perfect matching leaves nobody without a partner.
A maximum matching has the largest possible number of edges; a perfect matching covers every vertex (so \(|V|\) must be 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.
Maximum vs. Maximal: A Crucial Distinction
Maximum means globally largest. Maximal only means you cannot add another edge without breaking the matching rule. A maximal matching can therefore be locally stuck while still being smaller than the true optimum.
A locally finished matching need not be the largest one
This distinction is exactly why matching algorithms search for augmenting paths: they reveal how to rearrange a locally stuck matching into a larger one.
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)\) must contain at least as many vertices as \(S\).
Analogy: No Group Can Be “Collectively Stuck”
Hall's condition is a group bottleneck test, not an individual one. Every single vertex may have several choices and the matching can still fail if some group of \(k\) vertices collectively has fewer than \(k\) available neighbors. Hall's theorem says this is not merely one possible failure mode — it is the only obstruction.
Look for a crowded subset, not just a lonely vertex
In the left graph, all three vertices in \(S\) compete for only two neighbors. In the right graph, the candidate set has enough distinct neighbors to support a one-to-one assignment.
Hall's Theorem Is Structural — Algorithms Need Not Check Every Subset
The theorem quantifies over all \(2^{|X|}\) subsets, but matching algorithms do not enumerate them. Augmenting-path and flow algorithms search for a larger matching directly; if no augmentation exists, the search structure can be turned into a certificate explaining the bottleneck.
König's Theorem
A vertex cover is a set of vertices touching every edge. In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. If \(\nu(G)\) denotes maximum-matching size and \(\tau(G)\) minimum-vertex-cover size, then:
The easy inequality is \(\nu(G)\le \tau(G)\): every edge in a matching is disjoint from every other matching edge, so a vertex cover needs at least one different endpoint to hit each of them. König's theorem says bipartite graphs are special because this obvious lower bound is always tight.
Three disjoint pairs force at least three blockers — and three blockers suffice
This is the matching analogue of max-flow/min-cut: a construction (matching) and an apparently different obstruction/certificate (cover) meet at exactly the same optimum value.
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 two endpoints are unmatched. Berge's theorem (1957) says a matching \(M\) is maximum if and only if no augmenting path exists relative to \(M\).
Why Flipping an Augmenting Path Adds Exactly One Pair
An augmenting path begins and ends with unmatched edges, so it contains one more unmatched edge than matched edge. Flipping the status of every edge on the path therefore replaces \(k\) old matched edges with \(k+1\) new matched edges. Internal vertices stay matched exactly once; the two formerly free endpoints become matched.
Unmatched → matched → unmatched becomes matched → unmatched → matched
This is the matching version of residual-flow correction: a good algorithm is allowed to revise earlier choices rather than committing greedily forever.
Berge Gives Both an Algorithm and a Certificate
While an augmenting path exists, the matching is definitely not maximum. When no augmenting path exists, Berge's theorem certifies that no larger matching is possible. This “improve until no improving structure remains” pattern is one of the most reusable ideas in combinatorial optimization.
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.
One unit of flow = one matched pair
The unit capacities do all the bookkeeping. Capacity 1 out of \(s\) means each \(x\in X\) can be used at most once; capacity 1 into \(t\) means each \(y\in Y\) can be used at most once. An integral path \(s\to x\to y\to t\) is therefore exactly one legal matched pair \((x,y)\).
Because every capacity is an integer, the integrality theorem for max-flow guarantees an optimal flow with integer edge values. Since every relevant capacity is 1, those values are 0 or 1, so the positive-flow \(X\to Y\) edges directly form a matching rather than a fractional assignment.
Why Matching-Specific Algorithms Can Be Faster
The reduction proves correctness, but it also reveals extra structure: all capacities are 1 and every augmenting flow path alternates between the two bipartite sides. Hopcroft–Karp exploits exactly this structure by finding many shortest augmenting paths in phases, achieving \(O(E\sqrt{V})\) instead of treating the instance as an arbitrary flow network.
Hall, König, and Berge answer three different questions
Hall
Existence: when can all vertices on one side be matched?
König
Duality: how does maximum pairing equal minimum blocking?
Berge
Optimality: how do we know whether a current matching can still grow?
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 deferred acceptance. This is a different optimization goal from maximum-cardinality matching: instead of merely maximizing the number of pairs, it seeks a stable outcome under preference rankings, with no doctor-program pair that would both prefer each other over their assigned partners. Kidney-exchange programs use another branch of matching theory, arranging compatible donor-patient exchanges into pairs, cycles, or chains under medical compatibility constraints.
Matching Problems Can Have Different Objectives
The word matching describes the pairing structure, but real applications may optimize different things:
- Maximum-cardinality matching: pair as many compatible items as possible.
- Weighted/assignment matching: choose pairs with minimum cost or maximum value (the Hungarian algorithm deep dive).
- Stable matching: respect preference rankings so no unmatched pair would both prefer each other over their assigned partners (deferred acceptance / Gale–Shapley).
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.