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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Ein nicht geschlossener Eulerzug besitzt einen Anfangspunkt und einen davon verschiedenen Endpunkt . 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 oder oder sonst ein Punkt) der Grad um . Am Anfang und am Ende kommt für bzw. nochmal dazu.

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