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

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 ${}2$. Deshalb muss es in ${}G$ einen Kreis ${}K$ 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 ${}F$ die Kanten des Kreises und wir betrachten den neuen Graphen ${}G'=(V,E\setminus 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 ${}K_{j}=(V_{j},E_{j})$, ${}j\in 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 ${}K_{1},\ldots ,K_{s}$ durchnummerieren, derart gefunden hat, dass es einen Eulerzug für

${}G_{s}=\bigcup _{j=1}^{s}K_{j}\,$

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

Zur bewiesenen Aussage