Zusammenhängender Graph/Offener Eulerzug/Charakterisierung mit Grad/Fakt/Beweis

Beweis

Ein nicht geschlossener Eulerzug besitzt einen Anfangspunkt ${}u$ und einen davon verschiedenen Endpunkt ${}v$. Wenn man den Eulerzug durchläuft und dabei für jeden Punkt die Grade zählt, so erhöht sich bei jedem Durchlauf durch einen Punkt (egal ob ${}u$ oder ${}v$ oder sonst ein Punkt) der Grad um ${}2$. Am Anfang und am Ende kommt für ${}u$ bzw. ${}v$ nochmal ${}1$ dazu.

Es seien ${}u$ und ${}v$ die beiden Punkte mit ungeradem Grad. Wenn ${}\{u,v\}$ nicht zu ${}E$ gehört, so nimmt man diese Kante hinzu und erhält einen neuen Graphen ${}G'$, bei dem nun alle Knotenpunkte einen geraden Grad besitzen. Nach Fakt gibt es in ${}G'$ einen geschlossenen Eulerzug. Dieser ist ohne die Kante ${}\{u,v\}$ ein nichtgeschlossener Eulerzug von ${}G$. Wenn hingegen ${}\{u,v\}$ zu ${}E$ gehört, so nimmt man einen neuen Punkt ${}w$ zur Knotenmenge und die Kanten ${}\{u,w\}$ und ${}\{v,w\}$ zur Kantenmenge hinzu. Im neuen Graphen ${}G'$ besitzt wieder jeder Knoten einen geraden Grad. Ein geschlossener Eulerzug von ${}G'$ enthält den Kantenzug ${}\{u,w\},\{w,v\}$. Da ${}w$ in sonst keiner Kante auftritt, erhält man, indem man dieses Teilstück und ${}w$ weglässt, einen nichtgeschlossenen Eulerzug von ${}G$.

Zur bewiesenen Aussage