Course contentsShow
← Mathematics
Lesson 2701 of 3,12153. Graph TheoryFree lesson

Augmenting Paths and Berge's Theorem

Define M-augmenting paths and prove Berge's theorem: a matching is maximum if and only if no augmenting path exists.

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.