Ungerichteter Graph/Optimale Paarung/Alternierender Weg/Fakt/Beweis
Nehmen wir zuerst an, dass es einen alternierenden Weg gibt, der die Punkte und verbindet, die beide nicht durch die Paarung abgedeckt sind. Wir müssen zeigen, dass man eine Paarung konstruieren kann, die mehr Kanten als die gegebene Paarung besitzt. Es sei
der alternierende Weg. Dabei gehören die beiden Endkanten nicht zu , da die beiden Endpunkte nicht durch abgedeckt sind. Die Länge des Weges, also , ist ungerade. Wir modifizieren nun die Paarung, indem wir die Kanten für gerade herausnehmen und die Kanten für ungerade hinzunehmen. Dabei wird die Gesamtzahl der Kanten um erhöht. Ferner handelt es sich nach wie vor um eine Paarung. Würde es nämlich in der neuen Paarung einen Knotenpunkt geben, der mit zwei Kanten inzident ist, so würde eine Kante davon gleich sein (mit ungerade) und die andere Kante gleich (oder gleich ) Wenn diese zweite Kante nicht zum alternierenden Weg gehört, so gehört sie zu und würde zusammen mit (bzw. ) der Paarungseigenschaft von widersprechen. Wenn sie zum alternierenden Weg gehört, so wäre sie gleich mit ungerade, und dann würden die an dem Durchschnittspunkt anliegenden Kanten aus der Paarungseigenschaft von widersprechen (bei den Endkanten muss man etwas anders argumentieren).
Nehmen wir nun an, dass nicht optimal ist. Es sei eine optimale Paarung, die ja dann nach Definition mehr Kanten als besitzt. Es ist zu zeigen, dass es einen alternierenden Weg für gibt, dessen Endpunkte von nicht abgedeckt sind. Wir betrachten den Graphen auf mit der symmetrischen Differenz von und als Kantenmenge. Da mehr Kanten als besitzt, gibt es in mehr Kanten aus als aus . Dies muss dann auch für eine Zusammenhangskomponente von gelten, und deren Möglichkeiten sind in Fakt aufgelistet. Daher muss eine Komponente ein linearer Graph sein, mit Kanten abwechselnd aus und und wobei die Endkanten aus sind. Die Endpunkte sind dann insbesondere verschieden und nicht durch abgedeckt.
