Bipartiter Graph/Paarungszahl/Knotenüberdeckungszahl/Fakt/Beweis
Die Abschätzung gilt nach Fakt in jedem Graphen. Es sei nun der Graph als bipartit mit einer Zerlegung vorausgesetzt und sei eine optimale Paarung in . Wir wählen aus jeder Kante mit , einen Endpunkt nach folgendem Prinzip aus: Wenn es einen in einem von der Paarung unabgedeckten Punkt aus beginnenden alternierenden Weg in gibt, der in endet, so wählen wir , andernfalls . Nennen wir die Menge der so ausgewählten Knotenpunkte . Es ist zu zeigen, dass diese Auswahl eine Knotenüberdeckung ist. Es sei dazu eine beliebige Kante von . Wenn diese zu gehört, so sind wir fertig. Wir können also davon ausgehen, dass nicht zu gehört (mit , ). Da eine optimale Paarung ist, ist ein Endpunkt von mit einem Endpunkt einer Kante aus identisch. Entsprechend betrachten wir zwei Fälle.
Erster Fall. Wenn von der Paarung nicht abgedeckt ist, so ist von der Paarung abgedeckt und es gibt ein und eine Kante . Da in dem nichtabgedeckten Punkt startet, ist diese einzelne Kante ein alternierender Weg, der die geforderten Eigenschaften erfüllt, und daher wurde aus der Paarungskante der Punkt ausgewählt.
Zweiter Fall. Wenn von der Paarung abgedeckt ist, so gibt es ein derart, dass eine Kante von ist. Wenn aus dieser Kante ausgewählt wird, sind wir fertig. Wenn aber ausgewählt wird, so bedeutet dies, dass es einen in einem unabgedeckten Punkt von beginnenden alternierenden Weg gibt, der in endet. Dieser Weg wird durch die beiden Kanten und alternierend mit Endpunkt fortgesetzt. Da eine optimale Paarung vorliegt, folgt nach Fakt, dass durch die Paarung abgedeckt ist. Somit ist .
