Aufgabe:
Beweis folgender Aussage: Ein Multigraph Γ besitzt genau dann einen geschlossenen Eulerweg, falls Γ zusammenhängend ist und alle Ecken gerade Valenz haben.
Hier soll nur die Rückrichtung bewiesen werden (<=).
Problem/Ansatz:
1. Warum gibt es nach Satz 5.2.7 einen Kreis im Graph Γ? (Oben auf S. 261) Ein Baum ist laut Definition 5.2.4 ein zusammenhängender Graph, der keine Kreise besitzt. Und warum dehnt man die Definition eines Kreises auf die Folge zweier verschiedener Kanten zwischen zwei Ecken aus? Ich erkenne hier leider nicht ganz den Zusammenhang.
2. Unterhalb der Veranschaulichung (S. 261) steht, dass alle Valenzen der Γi gerade sind, da durch die Wegnahme vom Kreis C 0 oder 2 Kanten abgezogen werden. Warum werden denn durch die Wegnahme von C 0 oder 2 Kanten abgezogen?
Bei 2 Kanten stelle ich es mir so vor, dass die Γi jeweils durch eine Brücke mit dem Kreis C verbunden sind und alle Valenzen innerhalb des Kreises auch 2 sind. Wie könnte es sein, dass 0 Kanten abgezogen würden? Hieße dies nicht, dass kein Kreis existieren würde?
3. Und warum wird der Kreis C weggenommen, also warum betrachten wir denn überhaupt Γ' = Γ ⁄ C ? Was haben wir von der Existenz eines Kreises C im Graph Γ?
4. Wenn wir C entlang laufen und dann zwischendurch die Γi durchlaufen, müssen die Valenzen der Eckpunkte, die die Brücken zwischen C und den Γi bilden nicht jeweils 3 sein? Da die Valenzen innerhalb C und innerhalb der Γi gerade sind.
Ich weiß nicht, was ich falsch verstehe und würde mich sehr freuen, wenn mir jemand beim Verstehen dieses Beweises helfen könnte. Vielen Dank schon mal.
Der Beweis wird im Folgenden aufgeführt:
Satz: Ein Multigraph \( \Gamma \) besitzt genau dann einen geschlossenen Eulerweg, falls \( \Gamma \) zusammenhängend ist und alle Ecken gerade Valenz haben.
Beweisidee: Der Beweis beschränkt sich auf eine Richtung \( \left(, \Longleftarrow^{\text {i }}\right) . \) Er nutzt ein induktives Argument. Falls es nämlich einen Multigraphen gibt, der zusammenhängend ist und bei dem alle Ecken gerade Valenz haben, dann gibt es auch eine kleinste Eckenzahl, für die das zutrifft. Also zerlegen wir unseren Graphen so in kleinere Teilgraphen, dass diese Teile jeweils zusammenhängend sind und nur Ecken gerader Valenz haben. Durch diese Teilgraphen gibt es jeweils Eulerwege, die man geschickt zu einem großen Weg durch den ganzen Graphen zusammensetzt.
Beweis: Es genügt, nur die eine Richtung zu beweisen. Sei also \( \Gamma \) zusammenhängend und \( d(v) \equiv 0(\bmod 2) \) für alle \( v \in E \)
Mit dieser Voraussetzung sind alle Valenzen \( \geq 2 \) und es gibt nach Satz \( 5.2 .7 \) einen Kreis \( C \) in \( \Gamma \) (wobei wir nutzen, dass Satz \( 5.2 .7 \) offenbar auch für zusammenhängende Multigraphen gilt, falls wir die Definition eines Kreises auch auf die Folge zweier verschiedener Kanten zwischen zwei Ecken ausdehnen).
Sei \( \Gamma^{\prime}=\Gamma \backslash C \) und seien \( \Gamma_{1}, \ldots, \Gamma_{t} \) die Zusammenhangskomponenten in \( \Gamma^{\prime} \). Anschaulich kann man sich das ungefähr so vorstellen:
Die \( \Gamma_{i} \) 's sind zusammenhängend und alle Valenzen sind gerade, da entweder 0 oder 2 Kanten durch die Wegnahme von \( C \) abgezogen werden. Per Induktion enthalten dann alle \( \Gamma_{i} \) geschlossene Eulerwege. Wir erhalten einen geschlossenen Eulerweg in \( \Gamma \) nun wie folgt: Wir starten irgendwo auf \( C \) und wandern \( \operatorname{auf} C \) bis zur ersten Ecke in einem \( \Gamma_{i} . \) Wir gehen nun den Eulerweg in \( \Gamma_{i} \) und wandern auf \( C \) weiter bis zum nächsten \( \Gamma_{j} . \) Hier gehen wir wieder den Eulerweg usw.; die Schritte können wir entsprechend wiederholen, bis wir zum Ausgangspunkt zurückkommen. \( \square \)
Weiterer Anhang zum Verständnis:
Satz 5.2.7 Sei \( \Gamma=\Gamma(E, K) \) ein Baum und \( |E| \geq 2 \). Dann hat \( \Gamma \) mindestens zwei Ecken der Valenz \( 1 . \)
Definition 5.1.4 Sei \( \Gamma \) ein Graph und \( e \in E \) eine Ecke. Sei
\( De = { k | k aus K, e aus k} [Anmerkung: K ist die Menge der Kanten k] Dann nennt man \( d(e)=\left|D_{e}\right| \) die Valenz der Ecke \( e \).
Die Valenz ist damit genau die Anzahl der Kanten, auf denen die Ecke \( e \) liegt. Denkt man an den Stadtplan, mit dem wir gearbeitet haben, dann ist die Valenz die Anzahl der Straßen, die von einer Kreuzung oder Verzweigung abgehen.
Definition 5.2.4 Ein zusammenhängender Graph, der keine Kreise besitzt, \( 5.2 .4 \)
wird Baum genannt.
Definition 5.2.1 Sei \( \Gamma=\Gamma(E, K) \) ein Graph und \( u, v \in E . \) Eine Tour von u nach v ist eine Folge von Ecken u = u0, u1, ..., us = v
mit \( \left\{u_{i-1}, u_{i}\right\} \in K \) für \( i=1,2, \ldots, s \). Sind alle \( u_{i} \) verschieden, so nennen wir eine Tour auch einen Weg und \( s \) die Länge des Weges. Ist \( s>2, u=v \) und sind alle \( u_{i} \) für \( i=1, \ldots, s \) verschieden, so sprechen wir von einem Kreis der Länge \( s \).
