Der Vierfarbensatz

Zu den berühmtesten Problemen der Graphentheorie gehört die Frage:

Wie viele Farben brauchen wir, um die Ecken eines planaren Graphen so einzufärben, dass benachbarte Ecken stets verschieden gefärbt sind?

Das Problem lässt sich äquivalent auch als Färbungsproblem für die Länder einer Landkarte formulieren. Fassen wir die Länder als Ecken eines Graphen auf und fügen wir für je zwei aneinandergrenzende Länder eine Kante ein, so entsprechen gute Färbungen der Ecken des Graphen guten Färbungen der Länder. Dabei fügen wir Kanten nur ein, wenn die Länder eine gemeinsame Grenzmauer besitzen, d. h. sich nicht nur in einem Punkt berühren.

Der Vierfarbensatz besagt, dass vier Farben genügen. Der Satz wurde lange vermutet, aber erst 1970 von Appel und Haken bewiesen. Bis heute nimmt der Beweis eine ungewöhnliche Stellung ein, da Computer eingesetzt werden, um die Aussage für eine endliche Zahl von Graphen zu überprüfen. Aus diesen Spezialfällen lässt sich die allgemeine Aussage durch einen (computerfreien) Beweis gewinnen.

Die folgenden Diagramme zeigen minimale Färbungen der Graphen der Platonischen Körper. Es werden 4, 2, 3, 3 bzw. 4 Farben benötigt.

Formal ist eine Färbung eines Graphen G = (E, K) eine Funktion f der Form f : E → { 1, …, m }. Die Elemente von { 1, …, m } werden anschaulich als Farben bezeichnet, und für jede Ecke a des Graphen heißt f (a) die Farbe von a unter der Färbung f. Eine Färbung f : E → { 1, …, m } von G mit m Farben heißt eine (gute) m-Färbung von G, falls je zwei benachbarte Ecken verschieden gefärbt sind, d. h. falls gilt

f (a) ≠ f (b) für alle ab  ∈  K.

Der Vierfarbensatz besagt also, dass jeder planare Graph eine 4-Färbung besitzt. Überraschenderweise lassen sich etwas schwächere Ergebnisse relativ leicht beweisen. Ein bestechendes Beispiel für die Kraft der mathematischen Induktion ist der Beweis von:

Satz (Sechsfarbensatz)

Sei G = (E, K) ein planarer Graph. Dann gibt es eine 6-Färbung von G.

Beweis

Wir zeigen die Aussage durch Induktion nach e = | E | ≥ 1. Der Induktionsanfang ist klar, denn für e = 1 genügt eine Farbe. Im Induktionsschritt von e nach e + 1 betrachten wir einen planaren Graphen mit e + 1 Ecken. Nach obigem Satz gibt es ein a*  ∈  E mit d(a) ≤ 5. Wir streichen a* und erhalten so einen planaren Untergraphen G′ mit e Ecken. Nach Induktionsvoraussetzung gibt es eine 6-Färbung f von G′. Da a* höchstens fünf Nachbarn in G besitzt, gibt es eine Farbe c*, die von den Farben aller Nachbarn von a* verschieden ist. Wir setzen f auf E durch f (a*) = c* fort und erhalten so eine 6-Färbung von G.

Schon deutlich trickreicher ist der Beweis von:

Satz (Fünffarbensatz)

Sei G = (E, K) ein planarer Graph. Dann gibt es eine 5-Färbung von G.

Beweis

Wir argumentieren wie im Sechsfarbensatz induktiv:

Seien a* und G′ wie im Induktionsschritt oben, und sei f eine 5-Färbung von G′. Wir nehmen an, dass a* genau fünf Nachbarn besitzt, die in den fünf verfügbaren Farben gefärbt sind (denn andernfalls haben wir eine Farbe zur Färbung von a* frei und sind fertig). Nun betrachten wir eine planare Darstellung von G, in der die Nachbarn a₁, …, a₅ von a* zyklisch (im Uhrzeigersinn) angeordnet sind und mit den Farben 1, …, 5 gefärbt sind (dies können wir durch eine Umnummerierung der Farben erreichen). Für alle 1 ≤ i < j ≤ 5 sei H_ij der Untergraph von G′, der genau die Ecken der Farben i und j enthält. Wir betrachten nun Wege in einem Untergraphen H_ij. Dies sind genau die Wege in G′, auf denen sich die Farben i und j abwechseln. Wir zeigen:

(+) Ist a₃ erreichbar von a₁ in H₁₃, so ist a₄ nicht erreichbar von a₂ in H₂₄.

Beweis von (+)

Sei Z ein Weg in H₁₃ von a₁ nach a₃. Der Weg Z wird in G durch Verlängerung um a₃, a, a₁ zu einem Kreis. Dann liegt a₂ oder a₄ aufgrund der Anordnung der Ecken a₁, …, a₅ im Inneren dieses Kreises. Liegt a₂ im Inneren, so liegt jeder in a₂ beginnende Weg in H₂₄ aufgrund der Planarität der Darstellung und der Entfernung von a* ganz im Inneren des Kreises. Damit kann es keinen Weg in H₂₄ von a₂ nach a₄ geben. Analoges gilt, wenn a₄ im Inneren des Kreises liegt.

Wir betrachten nun die Zusammenhangskomponente A von a₁ in H₁₃ und die Zusammenhangskomponente B von a₂ in H₂₄. Nach (+) gilt a₃  ∉  A oder a₄  ∉  B. Ist a₃  ∉  A, so tauschen wir die Farben 1 und 3 in A aus. Die entstehende Färbung ist nach wie vor eine 5-Färbung von G′. Wegen a₃  ∉  A bleibt die Farbe 3 von a₃ erhalten, während a₁ nun die Farbe 3 besitzt. Damit ist die Farbe 1 zur Färbung von a* frei, sodass wir eine 5-Färbung von G erhalten. Analog verfahren wir, wenn a₄  ∉  B.

Das Hauptargument im Beweis von (+) lässt sich sehr anschaulich formulieren. Wir betrachten einen 5-Stern mit Zentrum a* und zyklisch angeordneten Ecken a₁, …, a₅ in einer planaren Darstellung eines Graphen. Nun seien zwei Kreise gegeben, die durch a₁, a*, a₃ bzw. a₂, a*, a₄ verlaufen, also den Stern kreuzen. Dann besitzen die beiden Kreise neben a* eine weitere gemeinsame Ecke b*, da sie sich aufgrund der Kreuzung noch einmal schneiden und dieses Schneiden in der planaren Darstellung nur über eine Ecke und nicht wie sonst auch über eine Kante erreicht werden kann. Damit können die beiden Kreise ohne die Ecke a* nicht mit zwei disjunkten Farbmengen eingefärbt werden, da sonst die Ecke b eine Farbe aus beiden Farbmengen erhalten würde.

Illustration des Beweises von (+) mit einer noch ungefärbten Ecke a*: Gibt es einen rot-grün-Weg von a₁ nach a₃, so gibt es keinen blau-lila-Weg von a₂ nach a₄