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.