Ungerichteter Graph/Optimale Paarung/Alternierender Weg/Fakt

Satz von Berge

Eine Paarung ${}P$ in einem Graphen ${}G$

ist genau dann optimal, wenn es keinen alternierenden Weg gibt, dessen Endpunkte verschieden und unabgedeckt sind.

Zum Beweis, Alternativen Beweis erstellen