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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
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 . Da an nur die beiden Kanten und anliegen, werden diese hintereinander durchlaufen. Wenn man die Konstruktion rückgängig macht (also und identifiziert), so erhält man einen Eulerzug von , bei dem die beiden Kanten hintereinander vorkommen. Wenn es umgekehrt einen Eulerzug von gibt, der die beiden Kanten hintereinander durchläuft, so kann man daraus direkt einen Eulerzug von konstruieren, was zeigt, dass zusammenhängend ist.