Augmenting Paths and Berge's Theorem
What you'll learn: You'll discover how augmenting paths provide a definitive test for whether a matching in a graph is as large as possible.
The Core Idea
Imagine you've matched some vertices in a graph (perhaps pairing students with projects). The natural question: Can you do better?
An M-augmenting path (relative to matching M) is a path that:
- Starts at an unmatched vertex
- Ends at a different unmatched vertex
- Alternates between edges not in M and edges in M
Think of it as a "trading chain": you walk along edges, alternating between unused and used edges, connecting two unmatched vertices.
Why Augmenting Paths Matter
If such a path exists, you can improve your matching! Swap the edges: remove the M-edges from the path and add the non-M edges. Since the path has one more non-M edge than M-edges (it starts and ends on non-M edges), you've increased your matching size by 1.
Berge's Theorem
Berge's Theorem makes this precise:
A matching M is maximum if and only if there exists no M-augmenting path.
Proof sketch:
- (⇐) If M is not maximum, then some larger matching M' exists. Look at the symmetric difference M ⊕ M' (edges in exactly one matching). This creates alternating paths and cycles. Since |M'| > |M|, at least one component must be an M-augmenting path.
- (⇒) If an M-augmenting path P exists, flipping edges along P creates a larger matching, contradicting maximality.
Key Takeaway: A matching is maximum precisely when no augmenting path exists—giving us both a stopping criterion and the foundation for efficient matching algorithms.