Zusammenhängender Graph/Eulersch/Gerader Grad/Kantenfolge/Fakt/Beweis

Beweis

Der konstruierte „Überbrückungsgraph“ besitzt ebenfalls die Eigenschaft, dass jeder Knotenpunkt einen geraden Grad besitzt. Wenn er zusammenhängend ist, so gibt es nach Fakt einen geschlossenen Eulerzug durch ${}G'$. Da an ${}u'$ nur die beiden Kanten ${}\{v,u'\}$ und ${}\{u',w\}$ anliegen, werden diese hintereinander durchlaufen. Wenn man die Konstruktion rückgängig macht (also ${}u$ und ${}u'$ identifiziert), so erhält man einen Eulerzug von ${}G$, bei dem die beiden Kanten hintereinander vorkommen. Wenn es umgekehrt einen Eulerzug von ${}G$ gibt, der die beiden Kanten hintereinander durchläuft, so kann man daraus direkt einen Eulerzug von ${}G'$ konstruieren, was zeigt, dass ${}G'$ zusammenhängend ist.

Zur bewiesenen Aussage