Zeige Weg von Knoten u nach Knoten v - fehlerhafte Aufgabenstellung?

Question

Aufgabe:

Sei G ein Graph und seien u != v die einzigen Knoten von G deren Grad ungerade ist. Zeigen Sie, dass es in G einen Weg zwischen u und v gibt.

Problem:

Ich versuche zur Zeit die Aufgabe zu lösen und weiß nicht, ob ich ein Verständnisproblem habe oder ob die Aufgabenstellung falsch ist. Nehmen wir an die Knoten zwischen u und v haben alle den Grad 0, welcher ja gerade ist. Dann gibt es doch keinen Weg von u nach v, oder?

Answer 1

Nehmen wir an die Knoten zwischen u und v haben alle den Grad 0

Dann stellt sich die Frage, inwiefern diese Knoten zwischen u und v liegen. Es sind ja dann Knoten, die mit den anderen Knoten überhaupt nicht mittels Kanten verbunden sind.

Falls alle Knoten außer u und v den Grad 0 haben, dann müssen u und v durch eine Kante verbunden sein. Ansonsten hätten u und v auch den Grad 0.

Die Summe der Grade aller Knoten ist in jeder Zusammenhangskomponente gerade, weil jede Kante zwei Enden hat.

Gibt es in einer Zusammenhangskomponente eine Ecke mit ungeradem Grad, dann muss es in dieser Zusammenhangskomponente deshalb noch eine weitere Ecke mit ungeradem Grad geben. Also müssen u und v in der gleichen Zusammenhangskomponente liegen. Somit gibt es einen Weg zwischen u und v.