Ungerichteter Graph/Optimale Paarung/Alternierender Weg/Fakt/Beweis/Aufgabe/Lösung

Nehmen wir zuerst an, dass es einen alternierenden Weg gibt, der die Punkte ${}u$ und ${}v$ 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

$\{u,u_{2}\},\{u_{2},u_{3}\},\ldots ,\{u_{n-1},v\}$

der alternierende Weg. Dabei gehören die beiden Endkanten nicht zu ${}P$, da die beiden Endpunkte nicht durch ${}P$ abgedeckt sind. Die Länge des Weges, also ${}n-1$, ist ungerade. Wir modifizieren nun die Paarung, indem wir die Kanten ${}\{u_{i},u_{i+1}\}$ für ${}i$ gerade herausnehmen und die Kanten ${}\{u_{i},u_{i+1}\}$ für ${}i$ ungerade hinzunehmen. Dabei wird die Gesamtzahl der Kanten um ${}1$ 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 ${}\{u_{i},u_{i+1}\}$ sein (mit ${}i$ ungerade) und die andere Kante gleich ${}\{u_{i},x\}$ (oder gleich ${}\{u_{i+1},x\}$) Wenn diese zweite Kante nicht zum alternierenden Weg gehört, so gehört sie zu ${}P$ und würde zusammen mit ${}\{u_{i-1},u_{i}\}$ (bzw. $\{u_{i+1},u_{i+2}\}$) der Paarungseigenschaft von ${}P$ widersprechen. Wenn sie zum alternierenden Weg gehört, so wäre sie gleich ${}\{u_{j},u_{j+1}\}$ mit ${}j$ ungerade, und dann würden die an dem Durchschnittspunkt anliegenden Kanten aus ${}P$ der Paarungseigenschaft von ${}P$ widersprechen (bei den Endkanten muss man etwas anders argumentieren).

Nehmen wir nun an, dass ${}P$ nicht optimal ist. Es sei ${}Q$ eine optimale Paarung, die ja dann nach Definition mehr Kanten als ${}P$ besitzt. Es ist zu zeigen, dass es einen alternierenden Weg für ${}P$ gibt, dessen Endpunkte von ${}P$ nicht abgedeckt sind. Wir betrachten den Graphen ${}H$ auf ${}V$ mit der symmetrischen Differenz von ${}P$ und ${}Q$ als Kantenmenge. Da ${}Q$ mehr Kanten als ${}P$ besitzt, gibt es in ${}H$ mehr Kanten aus ${}Q\setminus P$ als aus ${}P\setminus Q$. Dies muss dann auch für eine Zusammenhangskomponente von ${}H$ gelten, und deren Möglichkeiten sind in Fakt aufgelistet. Daher muss eine Komponente ein linearer Graph sein, mit Kanten abwechselnd aus ${}P$ und ${}Q$

und wobei die Endkanten aus ${}Q\setminus P$ sind. Die Endpunkte sind dann insbesondere verschieden und nicht durch ${}P$ abgedeckt.

Zur gelösten Aufgabe