Aufgabe:
Sei G=(V, E) ein zusammenhängender Graph und sei n ∈ ℕ die Anzahl der Knoten von V mit ungeradem Knotengrad in G. Wie können wir \( \frac{n}{2} \) viele Wege in G konstruieren, sodass jede Kante aus E in genau einem dieser Wege enthalten ist?
Problem/Ansatz:
Meine Lösung lautet wie folgt:
Sei G=(V, E) ein zusammenhängender Graph mit n ∈ ℕ Knoten mit ungeradem Knotengrad. Es gilt wegen des Handschlag-Lemmas, dass n eine gerade Zahl ist, daher ist \( \frac{n}{2} \) ∈ ℕ. Paare zwei beliebige ungerade Knoten und entferne einen beliebigen Pfad zwischen diesen. Die Existenz eines Pfades ist garantiert, da der Graph zusammenhängend ist. Dadurch reduzieren sich die Grade dieser beiden Knoten um 1 und werden gerade. Die Knoten entlang des Pfades reduzieren sich um 2, also ändert sich deren Parität nicht. Wiederhole diesen Prozess mit den verbleibenden Zusammenhangskomponenten. Falls eine Komponente keine ungeraden Knoten mehr besitzt, aber mindestens noch eine Kante hat, dann ist die Komponente eulersch. Entferne die Kanten der existierenden eulerschen Tour. Der Algorithmus terminiert, wenn alle Kanten entfernt wurden.
Ist mein Beweis korrekt?
