Maximize pairings across mutually exclusive groups by flipping alternating chains of assignments.
- Call the stranded applicant when greedy assignment locks two early roles on the four-applicant board
- Step the MatchingBoard to trace the Ben–Wren–Ana–Xiu augmenting path that flips commitments
- Take the boss round bet on how Kőnig's min vertex cover proves that four placements are impossible
After thisYou will resolve competing resource conflicts, satellite transponder switching, and network dualities.
Short on timeWatch the MatchingBoard step through the resignation chain that elevates the match from 2 to 3.
The Four-Applicant Bottleneck
3 minthe hook
Assign each applicant the first free choice on their list and the board stops at two placements, with Ben and Dan stranded while Xiu and Zed sit empty. The ceiling is three of the four, and Ben–Wren–Ana–Xiu is the chain that reaches it.
Four applicants face four roles on the board below: Ana, Ben, Cara, Dan on the left; Wren, Xiu, Yara, Zed on the right. Six edges mark mutual acceptability, and the ceiling holds because Cara and Dan accept only Yara.
The picture is the chain of resignations: a free applicant, the role they accept, the applicant holding that role, that applicant’s next role, and so on until a free role. Flip the chain and each applicant steps into the role the one ahead vacated, so the path adds a placement and turns nobody out.
Cara and Dan both qualify exclusively for Yara. Can any clever matching strategy ever place all four applicants simultaneously?
NextWhy does a greedy allocation leave applicants stranded while valid berths remain open?
The Greedy Myopia
2 minthe trap
Suppose you walk down the roster in alphabetical order, assigning each applicant the first available role they accept.
Ana acts first and claims Wren. Next arrives Ben: because Ben qualifies only for Wren, Ben is stranded without an assignment, even though Xiu and Zed sit entirely vacant!
A rigid algorithm that never revokes a handshake permanently stalls at 2 matches. True optimization requires the ability to reach backwards, shift existing commitments, and reopen pathways for stranded peers.
NextHow does an alternating path of assignments flip matched and unmatched edges to gain one unit?
Alternating Paths and Edge Independence
2 minthe invariant
A matching is a subset of edges sharing no common endpoints. Edges in the matching are active bonds; all remaining edges are idle candidates. A vertex touching no active edge is free.
An alternating path weaves between non-matched and matched edges in strict alternation. If such a path starts and ends at free vertices, it is an augmenting path.
Flipping the chain of resignations transforms every non-matched link into an active bond and demotes every matched link. Because the path began and ended on free edges, the total matching size increases by exactly one!
NextHow does Hall's marriage condition certify whether a complete matching exists?
The Triad of Equivalence: Hall, Berge, and König
2 minthe algebra
Three classical theorems pin the exact limits of bipartite matching.
Hall’s Marriage Theorem (Hall 1935). A bipartite graph admits a matching covering every left vertex if and only if every left subset satisfies . On our board, the subset has , proving algebraically why 4 matches are impossible.
Berge’s Lemma (Claude Berge 1957). A matching is maximum if and only if it admits zero augmenting paths. If any larger matching exists, their symmetric difference must contain an alternating path with more edges from the superior matching, which is by definition an augmenting path. When augmenting path search returns empty, optimality is guaranteed.
König’s Duality Theorem (Dénes König 1931). In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover:
On our board, the vertex subset contains 3 vertices and intercepts every single permitted edge. Since this cover has size 3 and our matching achieves size 3, weak duality snaps shut with zero gap.
The bipartite restriction is indispensable: an odd cycle like a triangle has maximum matching 1, but demands 2 vertices to cover all edges.
1 minboss round
Ana greedily claims Wren on the first move, leaving Ben (who only accepts Wren) stranded. Is the search stuck?
NextHow does the Hopcroft-Karp algorithm squeeze multiple augmenting paths into square-root rounds?
Flipping Commitments in Real Time
2 minthe simulation
Step through Kuhn’s augmenting path algorithm below. The gold trail traces the alternating path the search has found.
current matching
alternating path
none — either no free left vertex has been tried, or the search exhausted its alternating tree
Alternating means: non-matching edge, matching edge, non-matching edge, ending at a free vertex on the right. Flipping along it grows the matching by one.
Matching size is 0 of a possible 4. A matching is maximum exactly when the search finds no augmenting path anywhere — Berge's lemma (Berge 1957).
Kuhn's augmenting-path search on the board from section 0. Ana takes Wren first and strands Ben; Ben's step repairs it along Ben–Wren–Ana–Xiu; Dan's step finds nothing, which is Hall's shortfall drawn as a failed search.
Watch the chain of resignations; when it reaches a free role, the invariant is that the flip adds one pair and breaks none. Dan’s failed search is Hall’s shortfall: no chain leaves Dan, because he and Cara accept only Yara.
Step one: Ana seizes Wren, stranding Ben. Step two: Ben initiates a search; the system discovers the path Ben–Wren–Ana–Xiu and flips it, neatly accommodating both candidates.
Step three: Cara pairs effortlessly with Yara, lifting the score to 3. Step four: Dan searches for an augmenting route, but every branch chokes at the already-committed Yara; the search halts at size 3, certifying optimality via Berge’s condition.
Now observe the same instance modeled as a unit-capacity network flow with a source and sink.
initial state: no flow, the residual graph is the capacitated network itself
| edge | capacity | flow | residual (fwd / bwd) |
|---|---|---|---|
| s → Ana | 1 | 0 | 1 / 0 |
| s → Ben | 1 | 0 | 1 / 0 |
| s → Cara | 1 | 0 | 1 / 0 |
| s → Dan | 1 | 0 | 1 / 0 |
| Ana → Wren | 1 | 0 | 1 / 0 |
| Ana → Xiu | 1 | 0 | 1 / 0 |
| Ana → Zed | 1 | 0 | 1 / 0 |
| Ben → Wren | 1 | 0 | 1 / 0 |
| Cara → Yara | 1 | 0 | 1 / 0 |
| Dan → Yara | 1 | 0 | 1 / 0 |
| Wren → t | 1 | 0 | 1 / 0 |
| Xiu → t | 1 | 0 | 1 / 0 |
| Yara → t | 1 | 0 | 1 / 0 |
| Zed → t | 1 | 0 | 1 / 0 |
weak duality: primal ≤ dual at every iteration (gap on the same axis)
Edmonds–Karp augmenting paths (Ford–Fulkerson 1956 / Edmonds–Karp 1972). Weak duality says every flow value is at most every cut capacity, so the primal curve can only meet the dual from below; the gap closes to zero exactly when no augmenting path remains.
The board's instance as a unit-capacity flow network: source to applicants, the six acceptable pairs as pipes, placements to sink. Max flow 3, min cut 3, gap zero.
Every unit of flow along an edge corresponds to an active matching pair. The max-flow min-cut theorem (Ford & Fulkerson 1956) yields a max flow of 3 and a minimum cut of 3, echoing König’s theorem through the lens of continuous duality.
NextHow does bipartite matching schedule high-speed satellite crossbar communication switches?
Timetables, Corridors, and the Hopcroft–Karp Squeeze
2 minsystems
Bipartite matching models resource arbitration across industry: assigning medical shifts, scheduling examination timetables, and matching display advertisers to viewer impressions.
When graphs scale to millions of nodes, searching for single augmenting paths takes time. Hopcroft & Karp (1973) accelerated this by structuring execution into phases: each phase constructs a BFS level graph and extracts a maximal set of vertex-disjoint shortest augmenting paths in parallel.
Because each phase strictly increases the length of shortest augmenting paths, at most phases are required, yielding an overall runtime of:
The Birkhoff Polytope and the 0–1 Permanent
To compute the total count of distinct perfect matchings rather than locating just one, inspect the 0–1 biadjacency matrix . The number of perfect matchings is the permanent of —the signless analog of the determinant.
Leslie Valiant (1979) proved computing the permanent is #P-complete, demonstrating the vast gulf between finding one witness and counting all witnesses.
The Birkhoff–von Neumann theorem (Birkhoff 1946; von Neumann 1953) illuminates the geometry: the convex hull of all permutation matrices forms the Birkhoff polytope of doubly stochastic matrices. Fractional matchings form a continuous polyhedron whose extreme vertices are precisely the discrete matchings.
Attributions
- Hall 1935 — On Representatives of Subsets: Hall’s marriage condition characterizing left-saturating matchings.
- König 1931 — Graphs and Matrices: Duality theorem equating maximum bipartite matching to minimum vertex cover.
- Berge 1957 — Two theorems in graph theory: Augmenting path criterion certifying matching optimality.
- Ford & Fulkerson 1956 — Network flow formulations and the unit-capacity matching reduction.
- Hopcroft & Karp 1973 — An algorithm for maximum matchings in bipartite graphs using phased shortest augmenting paths.
- Birkhoff 1946 & von Neumann 1953 — The Birkhoff–von Neumann theorem decomposing doubly stochastic matrices into permutation matchings.