Wenn der Graph bipartit ist, wechseln sich auf einem Weg B-Knoten und C-Knoten ab. Wenn ein Weg von einem B-Knoten zu einem B-Knoten führt, z.B. b-c-b-c-b-c-b ist die Anzahl der Knoten ungerade und die Anzahl der Kanten gerade. Insbesondere bei einem Kreis.
Wenn keine Kreise ungerader Länge existieren: Es genügt die einzelnen Zusammenhangskomponenten von V zu betrachten. Daher sei V o.B.d.A. zusammenhängend.
Wir bestimmen durch eine Breitensuche einen aufspannenden Baum mit Wurzel, sagen wir, x. Dies führt zu eine Aufteilung der Knoten in Generationen. In diesem Baum führt von x ein eindeutiger Weg zu jedem Knoten v. Die Länge dieses Wegs entspricht der Generations-Nummer. Es seien B alle Knoten, die zu einer Generation mit gerader Nummer gehören, und C die anderen.
Dies liefert die gewünschte Zerlegung. Denn wenn es eine Kante {b,b'} mit b,b' aus B gäbe, dann haben wir einen Weg, der im Baum von x zu b führt (gerade Anzahl von Kanten), Kante {b,b'}, Weg von b' nach x im Baum (gerade Anzahl von Kanten). Insgesamt eine Kreis von x nach x mit ungerader Kantenzahl.
Analog für den Fall, dass es eine Kante innerhalb von C gäbe.
