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

Es sei ${}V=A\uplus B$ eine bipartite Zerlegung eines bipartiten Graphen. In jedem Weg in einem bipartiten Graphen gehören die Knoten abwechselnd zu ${}A$ oder zu ${}B$. 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 ${}G$ zusammenhängend ist. Es sei ${}v\in V$ ein fixierter Punkt. Wir definieren

${}A={\left\{x\in V\mid {\text{ es gibt einen geradzahligen Weg von }}v{\text{ nach }}x\right\}}\,$

und

${}B={\left\{x\in V\mid {\text{ es gibt einen ungeradzahligen Weg von }}v{\text{ nach }}x\right\}}\,.$

Wegen der Zusammenhangseigenschaft ist

${}V=A\cup B\,.$

Nehmen wir an, dass ${}A$ und ${}B$ nicht disjunkt sind, sagen wir ${}y\in A\cap B$. Es gibt dann Wege

${}v=v_{0}\sim v_{1}\sim \ldots \sim v_{r}=y\,$

und

${}v=v_{0}\sim u_{1}\sim \ldots \sim u_{s}=y\,$

mit ${}r$ gerade und ${}s$ 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 ${}A$ geben würde, so würden die daran beteiligten Punkte sofort auch zu ${}B$ gehören im Widerspruch zur gezeigten Disjunktheit.

Zur gelösten Aufgabe