Chapter 25 — Matchings in Bipartite Graphs

This is the canonical CLRS fourth-edition chapter guide during the migration period.

Current source

Sections 25.1, 25.2 and 25.3 are native fourth-edition sections. Section 25.1 (maximum bipartite matching revisited) lives in the CLRS.Chapter26.Matching and CLRS.Matchings namespaces, imported through Section 25.1; its sub-modules are:

• Matching API Extensions

• Alternating Paths

• Simple-Path Extraction

• Matching Flow Residuals

• Residual Reachability Translation

• Berge's Lemma and the Flow Method

Section 25.2 (the stable-marriage problem) lives in the CLRS.Matchings and CLRS.StableMarriage namespaces, imported through Section 25.2; its sub-modules are:

• Preference Model

• Gale-Shapley Algorithm

• Optimality

Section 25.3 (the Hungarian algorithm for the assignment problem) lives in the CLRS.AssignmentProblem namespace: Section 25.3.

Coverage boundary

Status: complete. Section 25.1 is formalized (Berge's augmenting-path lemma and the flow-method certification, built on the §26.3 matching-to-flow reduction). Section 25.2 proves Gale-Shapley stability (Theorem 25.5), stable-pairing existence, perfectness, man-optimality (Theorem 25.6), and woman-pessimality. Section 25.3 formalizes the assignment model and Lemma 25.8 (dual optimality via feasible potentials), the alternating tree, the potential-adjustment step, the augmentation step (a tight edge to a free right vertex enlarges the matching via Berge), the tree-growth step, and the local progress theorem; the full adjustment-plus-augmentation loop is packaged as a terminating recursion (innerLoop and exists_perfect_tight) whose perfect tight matching is optimal by Lemma 25.8.

See docs/clrs-fourth-edition-map.csv for the section-level mapping and docs/migrations/clrs4.md for compatibility and deprecation policy.