Eulersche Graphen

Für die genaue Formulierung des Problems brauchen wir einige Definitionen.

Definition (Euler-Zug)

Sei G = (E, K) ein Graph. Ein geschlossener Kantenzug heißt ein (geschlossener) Euler-Zug in G, falls er jede Kante des Graphen genau einmal besucht. Der Graph G heißt Eulersch, wenn ein Euler-Zug in G existiert.

Beispiele

(1)	Wir betrachten den folgenden Graphen G = (E, K): Der Kantenzug Z = 1, 2, 4, 3, 7, 8, 1, 3, 5, 6, 4, 1 ist ein Euler-Zug in G. Der Graph ist also Eulersch. Wir können den Euler-Zug Z visualisieren, indem wir den Besuchszeitpunkte der Kanten eintragen:

(2)	Jeder Kreis ist Eulersch.

(3)	Ein aus genau zwei Ecken und einer Kante bestehender Graph ist nicht Eulersch.

(4)	Hat G mindestens zwei Zusammenhangskomponenten und zudem keine isolierten Ecken, so ist G nicht Eulersch.

(5)	Hat G eine beliebige Eckenmenge und keine Kanten, so ist G Eulersch, denn für jede Ecke a ist a ein Euler-Zug der Länge 0.

Bis auf die Zusatzbedingung „keine isolierten Ecken“ (die leicht vergessen wird) ist also „zusammenhängend“ eine notwendige Bedingung für „Eulersch“. Das ist noch nicht besonders aufregend. Interessanter ist:

Satz (notwendige Bedingung von Euler)

Sei G = (E, K) Eulersch. Dann hat jede Ecke in G einen geraden Grad.

Beweis

Sei Z = a₀, …, a_n, a₀ ein Euler-Zug in G. Wir betrachten zunächst eine von a₀ verschiedene Ecke a. Wird die Ecke a auf Z entlang einer Kante ba besucht, so wird die Ecke a unmittelbar danach entlang einer anderen Kante ac wieder verlassen, sodass der Besuch von a die Form

… b, a, c … mit b ≠ c

besitzt. Damit können jedem Besuch von a genau zwei Kanten mit der Ecke a zugeordnet werden. Da auf Z jede Kante mit der Ecke a genau einmal besucht wird, taucht jede Kante mit der Ecke a in genau einer dieser Zuordnungen auf. Wird also a genau k mal auf Z besucht, so gilt d(a) = 2k. Damit ist d(a) gerade.

Für die Startecke a₀ argumentieren wir analog, indem wir das Besuchspaar a₀ a₁ und a_n a₀ mit einbeziehen. Alternativ können wir auch den verschobenen Euler−Zug a₁, …, a_n, a₀, a₁ betrachten, bei dem a₀ nicht mehr die Startecke ist. Obiges Argument zeigt, dass d(a₀) gerade ist.

Der Beweis lässt sich anschaulich so zusammenfassen: Laufen wir in eine Ecke a hinein, so müssen wir aus der Ecke a auf einer anderen Kante wieder herauslaufen. Bei jedem Rein-Raus-Laufen werden zwei der d(a) Kanten verbraucht. Da am Ende alle Kanten verbraucht sind, muss d(a) gerade sein. Die Ecke a selbst wird d(a)/2-oft besucht.

Beispiel

Wir betrachten noch einmal obigen Graphen G und den Euler-Zug Z. Die Ecke 3 hat den Grad 4. Beim ersten Besuch der Ecke 3 werden die Kanten 43 und 37 verbraucht, beim zweiten Besuch die Kanten 13 und 35. Die Ecke 1 besitzt das Besuchspaar 81 und 13, und zudem das besondere Paar 12 und 41, das der Sonderrolle der 1 als Start- und End-Ecke entspricht.

Überraschenderweise ist die Geradheit aller Grade auch für eine hinreichende Bedingung nützlich. Um die Sprechweise zu vereinfachen, definieren wir:

Definition (gerader Graph)

Ein Graph G heißt gerade, falls jede Ecke von G einen geraden Grad besitzt.

Entscheidend ist folgender Hilfssatz:

Satz (Rückkehrlemma)

Sei G = (E, K) ein gerader Graph. Weiter sei a eine Ecke mit positivem Grad. Dann gibt es einen einfachen geschlossenen Kantenzug von a nach a positiver Länge.

Beweis

Wir starten bei a und durchlaufen solange neue, d. h. bislang unbesuchte Kanten, bis wir wieder bei a ankommen. Der so erzeugte Kantenzug endet bei der Ecke a, da wir jede besuchte Ecke b ≠ a wegen d(b) gerade auf einer bislang unbesuchten Kante wieder verlassen können (und da die Anzahl der Kanten des Graphen endlich ist).

Beispiel

Wir betrachten noch einmal obigen Graphen. Startend in der Ecke 6 laufen wir entlang unbesuchter Kanten von jeder Ecke zur kleinsten Nachbarecke, bis wir wieder bei der Startecke ankommen. Auf dieser Weise ergibt sich der Kantenzug

6, 4, 1, 2, 4, 3, 5, 6

Diesen Kantenzug können wir visualisieren, indem wir die aktuell besuchte Ecke besonders einfärben und nach jedem Schritt die durchlaufene Kante entfernen:

Befinden wir uns also in einem Ausgangsraum eines Labyrinths und wissen wir, dass von jedem Raum des Labyrinths eine gerade Zahl von Gängen abführt, so müssen wir nur stets neue Gänge durchlaufen, um irgendwann wieder im Ausgangsraum anzukommen. Es reicht, die durchlaufenen Gänge zu markieren, den genauen Verlauf dieser Erkundung müssen wir gar nicht protokollieren.

Nach diesen Vorbereitungen können wir nun relativ leicht zeigen:

Satz (hinreichende Bedingung von Euler und Hierholzer)

Sei G = (E, K) ein zusammenhängender gerader Graph. Dann ist G Eulersch.

Beweis

Es genügt, folgende Aussage zu beweisen:

(+)	Sei Z ein einfacher geschlossener Kantenzug in G, der kein Euler-Zug ist. Dann können wir Z zu einem geschlossenen einfachen Kantenzug Z′ erweitern, der mehr Kanten als Z besucht.

Zum Beweis von (+) sei Z ein einfacher geschlossener Kantenzug in G, der kein Euler-Zug ist. Wir wählen eine auf Z nicht besuchte Kante bc derart, dass die Ecke b auf Z besucht wird.

Beweis der Existenz einer solchen Kante

Da Z kein Euler-Zug ist, gibt es eine auf Z nicht besuchte Kante a*b*. Da G zusammenhängend ist, gibt es in G einen Kantenzug der Form

a*, b*, …, a₀, mit der Startecke a₀ von Z.

Die erste Kante dieses Kantenzugs, die zu einer besuchten Ecke von Z führt, ist eine Kante wie gewünscht.

Wir streichen nun alle Kanten von Z aus G und erhalten so den Teilgraphen G′. Der Graph G′ ist immer noch gerade, da wir den Grad jeder Ecke um eine gerade Zahl vermindert haben. (Der Graph G′ ist nicht mehr notwendig zusammenhängend, was wir nicht brauchen.) Nach dem Rückkehrlemma existiert in G′ ein einfacher geschlossener Kantenzug

W = b, c, …, b.

Wir fügen nun W an der ersten Stelle i eines Besuchs von b in Z ein, und erhalten dadurch einen Kantenzug, den wir Z + W nennen:

Z = a₀, …, a_i = b, a_i + 1, …, a_n, a₀

Z + W = a₀, …, a_i = b, c, …, b, a_i + 1, … a_n, a₀

Der Kantenzug Z′ = Z + W ist einfach, geschlossen und länger als Z.

Die Notation Z + W des Beweises verwenden wir auch im Folgenden: Z + W ist der Kantenzug, der aus Z durch Einfügen von W an der ersten möglichen Stelle hervorgeht. Dabei ist W geschlossen.