Ungerichteter Graph/Bipartit/Gerade Kreise/Fakt/Beweis/Aufgabe/Lösung


Es sei eine bipartite Zerlegung eines bipartiten Graphen. In jedem Weg in einem bipartiten Graphen gehören die Knoten abwechselnd zu oder zu . Die Existenz eines Kreises mit ungerader Anzahl führt daher direkt zu einem Widerspruch.

Es sei nun umgekehrt die Kreisbedingung erfüllt. Wir können annehmen, dass zusammenhängend ist. Es sei ein fixierter Punkt. Wir definieren

und

Wegen der Zusammenhangseigenschaft ist

Nehmen wir an, dass und nicht disjunkt sind, sagen wir . Es gibt dann Wege

und

mit gerade und ungerade. Indem man die beiden Wege zusammensetzt, erhält man einen Zyklus mit ungerade vielen Knoten. Wenn es in ihm Wiederholungen gibt, so kann man daraus zwei kleinere Zyklen herausarbeiten, von denen einer ebenfalls eine ungerade Anzahl besitzt. Somit erhält man auch einen ungeraden Kreis im Widerspruch zur Voraussetzung. Die beiden Mengen sind also disjunkt. Wenn es eine Kante innerhalb von geben würde, so würden die daran beteiligten Punkte sofort auch zu gehören im Widerspruch zur gezeigten Disjunktheit.