Satz von Berge

Def: Weg p heißt M-alternierend, wenn er abwechselnd Kanten aus M und E $\setminus$ M enthält.

Def: alternierender M-Weg heißt erweiternde, falls er zwei nicht gesättigte Knoten verbindet.

Satz (Claude Berge): für jedes Matching M in G sind äquivalent:

• M ist maximal
• es gibt keinen erweiternden M-Weg