Zum Inhalt springen

Zusammenhängender Graph/Eulersch/Gerader Grad/Kantendisjunkte Kreise/Fakt/Beweis

Beweis

Von (1) nach (2) ist klar, da bei einem geschlossenen Eulerzug jeder Knotenpunkt genau so oft besucht wie verlassen wird.

Von (2) nach (3). Wir führen Induktion über die Anzahl der Kanten. Da der Graph zusammenhängend ist, handelt es sich um einen isolierten Punkt oder aber jeder Knoten besitzt einen Grad von zumindest 2. Deshalb muss es in G einen Kreis K geben. Man kann ja in einem beliebigen Punkt starten und von diesem Punkt ausgehend nach und nach einen Kantenzug konstruieren. Wenn der Kantenzug in einen Punkt hineingeht, so kann man den Kantenzug fortsetzen, da zumindest zwei Kanten in dem Punkt zusammenlaufen. Sobald ein schon erreichter Punkt erneut auftaucht, ist der Kreis fertig, die „Vorperiode“ kann man außer Acht lassen. Es seien F die Kanten des Kreises und wir betrachten den neuen Graphen  G′=(V,E∖F).  Wenn ein Punkt aus V zu einer Kante aus F inzident ist, so reduziert sich der Grad in diesem Knoten um 2, da ja jeder Punkt in einem Kreis inzident zu zwei Kanten ist. Wenn ein Punkt im Kreis nicht aufgerufen wird, so ändert sich der Grad nicht. In jedem Fall besitzt in G′ jeder Punkt wieder einen geraden Grad. Der neue Graph muss nicht mehr zusammenhängend sein, allerdings erfüllen die einzelnen Zusammenhangskomponenten von G′ wieder die Voraussetzung, dass sämtliche Grade gerade sind. Nach Induktionsvoraussetzung besitzen die Zusammenhangskomponenten jeweils eine Darstellung als Vereinigung mit kantendisjunkten Kreisen. Also besitzt G′ eine Darstellung als Vereinigung mit kantendisjunkten Kreisen und zusammen mit K ergibt sich eine Darstellung von G als Vereinigung mit kantendisjunkten Kreisen.

Von (3) nach (1). Es seien  Kj=(Vj,Ej),   j∈J,  die beteiligten kantendisjunkten Kreise, die G überdecken. Wir konstruieren induktiv Kantenzüge, die für zunehmend größere Vereinigungen dieser Kreise einen Eulerzug darstellen. Einen einzelnen Kreis kann man unmittelbar als einen Eulerzug für diesen Kreis auffassen. Es sei nun vorausgesetzt, dass man s Kreise, die wir als K1,…,Ks durchnummerieren, derart gefunden hat, dass es einen Eulerzug für

Gs=⋃j=1sKj

gibt. Bei  s<r  gibt es aufgrund des Zusammenhangs des Graphen einen weiteren Kreis, den wir Ks+1 nennen, der einen gemeinsamen Knotenpunkt mit Gs hat, sagen wir u. Dann erhält man aus dem Eulerzug für Gs einen Eulerzug für  Gs+1=Gs∪Ks+1,  indem man, wenn der Eulerzug den Punkt u erreicht, in den Kreis Ks+1 abbiegt, diesen einmal durchläuft und danach an der Stelle u den alten Eulerzug fortsetzt. Da Ks+1 kantendisjunkt zu Gs ist, entsteht dabei wieder ein Eulerzug.