Paarung/Perfekt etc./Zusammenhangskomponente/Aufgabe

Es sei ${}P$ eine Paarung in einem Graphen ${}G$. Zeige, dass ${}P$ genau dann perfekt (maximal, optimal) ist, wenn dies für die Einschränkungen von ${}P$ auf jede Zusammenhangskomponente von ${}G$ gilt.

Eine Lösung erstellen