Zeige oder widerlege: G'' besitzt eine Eulertour.

Question

Aufgabe:

Sei G ein einfacher, zusammenhängender Graph. Betrachte den Graphen G'' mit parallelen Kanten, der entsteht, wenn in G alle Kanten verdoppelt werden. Zeige oder widerlege: G'' besitzt eine Eulertour.

Problem/Ansatz:

Können Sie mir bitte bei diese Frage auch helfen? Ein Paat tipps reicht schon.

Vielen Dank im Voraus.

Answer 1

Hallo,

eine Eulertour existiert ja, falls jeder Knotengrad gerade ist. Indem du in G'' jede Kante verdoppelst, verdoppelst du auch die Knotengrade und somit hat jeder Knoten eine gerade Gradzahl. Deswegen findet man eine Eulertour.

Shii

Comments

Vielen lieben Dank.