Berge's theorem

Link

This note lacks links.

Lead

In graph theory, Berge’s theorem ^[1] states that a matching $M$ in a graph $G$ is maximum if and only if there is no augmenting path with respect to $M$.

Berge’s theorem characterizes maximum-cardinality matchings via a purely combinatorial property and underlies many efficient algorithms, such as Hungarian algorithm and augmenting-path methods.

Berge's theorem

A matching $M$ in a graph $G$ is maximum if and only if there is no augmenting path in $G$ with respect to $M$.

Proof of Berge's theorem

($\Rightarrow$) Suppose $M$ is a maximum matching. If there were an augmenting path $P$, then we could construct a larger matching $M^{\prime }=M△E(P),$ where $△$ denotes the symmetric difference. Along $P$, edges not in $M$ are added and edges in $M$ are removed. Since $P$ starts and ends at unmatched vertices, this increases the size of the matching by $1$, contradicting maximality of $M$.

($\Leftarrow$) Suppose $M$ is not maximum. Let $M^{\prime }$ be a matching with $|M^{\prime }|>|M|$. Consider the symmetric difference $H=M△M^{\prime }.$

The graph $H$ consists of disjoint paths and even cycles in which edges alternate between $M$ and $M^{\prime }$. Since $|M^{\prime }|>|M|$, there must exist a connected component of $H$ that contains more edges from $M^{\prime }$ than from $M$. Such a component must be an alternating path whose endpoints are unmatched in $M$, i.e. an augmenting path.

Thus, if $M$ is not maximum, an augmenting path exists.

Combining both directions, $M$ is maximum if and only if there is no augmenting path. $\square$

References

1. [1]

   “Berge’s theorem”, Wikipedia, Available: https://en.wikipedia.org/wiki/Berge%27s_theorem, Accessed: 2026-06-18 ↩