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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Von (1) nach (2) ist klar, da bei einen 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 . Deshalb muss es in einen Kreis geben. Man kann ja inn 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. Wenn erstmal ein schon erreichter Punkt erneut auftaucht, ist der Kreis fertig, die „Vorperiode“ kann man außer Acht lassen. Es seien die Kanten des Kreises und wir betrachten den neuen Graphen . Wenn ein Punkt aus zu einer Kante aus inzident ist, so reduziert sich der Grad in diesem Knoten um , 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 jeder Punkt wieder einen geraden Grad. Der neue Graph muss nicht mehr zusammenhängend sein, allerdings erfüllen die einzelnen Zusammenhangskomponenten von wieder die Voraussetzung, dass sämtliche Grade gerade sind. Nach Induktionsvoraussetzung besitzen die Zusammenhangskomponenten jeweils eine Darstellung als Vereinigung mit kantendisjunkten Kreisen. Also besitzt eine Darstellung als Vereinigung mit kantendisjunkten Kreisen und zusammen mit ergibt sich eine Darstellung von als Vereinigung mit kantendisjunkten Kreisen.

Von (3) nach (1). Es seien , , die beteiligten kantendisjunkten Kreise, die ü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 Kreise, die wir als durchnummerieren, derart gefunden hat, dass es einen Eulerzug für

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