Fünf-Farben-Satz

Eine Karte, die mit fünf Farben eingefärbt wurde.

Der Fünf-Farben-Satz besagt, dass jede Landkarte mit fünf Farben so gefärbt werden kann, dass keine zwei Länder mit derselben Farbe aneinandergrenzen. Die Aussage gilt unter den Einschränkungen, dass ein gemeinsamer Punkt nicht als „Grenze“ zählt und jedes Land aus einer zusammenhängenden Fläche besteht, also keine Exklaven vorhanden sind. Der Fünf-Farben-Satz ist schwächer als der Vier-Farben-Satz und deutlich leichter zu beweisen.

Historisches

Der Satz geht auf Percy Heawood zurück. Dieser entdeckte in dem von Alfred Kempe 1879 veröffentlichten und zunächst als korrekt erachteten Beweis des Vier-Farben-Satzes einen zur damaligen Zeit irreparablen Fehler und bewies daraufhin im Jahre 1890 mit elementaren Mitteln den Fünf-Farben-Satz.

Graphentheoretische Formulierung

Übergang von einer gefärbten Landkarte zu einem Graphen mit Knotenfärbung.

Formal lässt sich das Problem am einfachsten mit Hilfe der Graphentheorie beschreiben. Dabei wird jedem Land der Karte genau ein Knoten zugeordnet. Zwei Knoten des Graphen werden genau dann durch eine (ungerichtete) Kante miteinander verbunden, wenn die Länder aneinandergrenzen. Der so entstehende Graph ist planar (auch „plättbar“ genannt), da er sich aufgrund seiner Konstruktion in die Ebene einbetten lässt, ohne dass sich die Kanten schneiden.

Für einen (beliebigen) Graphen ist eine Knotenfärbung mit (höchstens) $k$ „Farben“ eine Abbildung der Knotenmenge in die Menge $\{1,2,\ldots ,k\}$. Die Färbung ist zulässig, wenn benachbarte Knoten verschiedene Farben zugewiesen bekommen. Der Graph heißt k-färbbar (genauer k-knotenfärbbar), wenn es für ihn eine zulässige Färbung mit $k$ Farben gibt. Der Fünf-Farben-Satz lautet nun in graphentheoretischer Formulierung:

Jeder planare Graph ist 5-färbbar.

Beweis des Satzes

Der Beweis wird durch vollständige Induktion nach der Anzahl der Knoten in dem planaren Graphen geführt.

• Induktionsbasis: Ein Graph mit einem Knoten ist mit einer Farbe nach den Voraussetzungen färbbar.
• Induktionsannahme: Der Satz gilt für $n-1$ Knoten.
• Induktionsbehauptung: Der Satz gilt für $n$ Knoten.
• Induktionsschritt: Basierend auf der Eulerschen Polyederformel kann man festhalten, dass in jedem planaren Graphen mindestens ein Knoten mit Knotengrad kleiner gleich 5, d. h. mit weniger als sechs inzidenten (eingehenden) Kanten bzw. mit weniger als 6 benachbarten Knoten existiert.
  • Fall 1: Im Graph $G$ gibt es einen Knoten $v$ mit Knotengrad kleiner fünf. Man wende die Annahme auf den Graphen $G(1)$, der $G$ ohne den Knoten $v$ entspricht, an. $G(1)$ kann mit fünf Farben gültig gefärbt werden. $v$ hat maximal vier benachbarte Knoten und kann mit der fünften vorhandenen Farbe gefärbt werden. Der Graph kann also gültig gefärbt werden.
  • Fall 2: Es gibt im Graphen $G$ keinen Knoten mit Knotengrad kleiner 5. Aus der Eulerschen Polyederformel folgt dann, dass es einen Knoten $w$ mit Knotengrad gleich 5 geben muss. Der Graph $G(2)$, der $G$ ohne $w$ entspricht, ist nach Induktionsannahme mit 5 Farben färbbar.
    • Fall 2.1: Die Nachbarknoten von $w$ sind nur mit vier unterschiedlichen Farben gefärbt. Dann wird $w$ mit der fünften vorhandenen Farbe gefärbt und man erhält eine gültige Färbung.
    • Fall 2.2: Die Nachbarknoten von $w$ sind in fünf unterschiedlichen Farben gefärbt. Dann wähle man eine beliebige, fixe planare Einbettung von $G$ und bezeichne die Nachbarknoten von $w$ mit $w(1),w(2),\ldots ,w(5)$ im Uhrzeigersinn. Gibt es nun einen Weg $V$ von $w(1)$ nach $w(3)$, der nicht über $w$ führt und nur die Farben von $w(1)$ und $w(3)$ (nach Induktionsannahme logischerweise abwechselnd) verwendet?
      • Fall 2.2.1, Nein: Dann wird der Knoten $w(1)$ auf die Farbe von $w(3)$ umgefärbt. Alle benachbarten Knoten von $w(1)$ mit der Farbe von $w(3)$ werden auf die ehemalige Farbe von $w(1)$ umgefärbt usw. Man erhält wieder eine gültige Färbung von $G$. Die benachbarten Knoten von $w$ sind nun jedoch nur mehr in vier Farben gefärbt ($w(1)$ hat nun dieselbe Farbe wie $w(3)$) und $w$ kann mit der fünften vorhandenen Farbe gefärbt werden, was eine gültige Graphenfärbung ergibt.
      • Fall 2.2.2, Ja: (Durch das Wechseln der Färbung wie im vorigen Fall kann man hier nichts erreichen, da im Endeffekt nur $w(1)$ und $w(3)$ die Farben wechseln.) Man betrachte nun die Knoten $w(2)$ und $w(4)$. Zwischen diesen beiden Knoten kann es keinen Weg geben, der abwechselnd die Farben der beiden Knoten verwendet, denn dieser Weg müsste unweigerlich über einen Knoten gehen, der auf dem Weg $V$ liegt und damit eine andere Farbe als die von $w(2)$ und $w(4)$ hat. Das begründet sich dadurch, dass $w(2)$ sozusagen von diesem Weg $V$ und $w$ (die zusammen ja einen Kreis ergeben) eingekreist wird. Somit kann man auf $w(2)$ und $w(4)$ dasselbe Umfärbprinzip anwenden wie im vorigen Fall auf $w(1)$ und $w(3)$. Damit haben die benachbarten Knoten von $w$ wieder nur vier Farben und man kann $w$ mit der fünften vorhandenen Farbe färben um eine gültige Färbung zu erreichen.

Algorithmus

Der Beweis liefert direkt einen Algorithmus zur Bestimmung einer Fünf-Färbung eines planaren Graphen $G=(V,E)$ in $O((|E|+|V|)\cdot |V|)$ (es gibt jedoch auch Linearzeitalgorithmen zur Bestimmung einer Fünf-Färbung).

• def 5color(Graph G):
  • Abbruchfall: Enthält der Graph nur noch 5 Knoten, färbe sie in den 5 zur Verfügung stehenden Farben ein.
  • Suche nach Knoten mit Grad <5. Findest du einen solchen:
    • Entferne den Knoten aus G.
    • Setze coloring := 5color(G).
    • Füge den Knoten wieder in G ein, und bestimme seine Färbung (diese ist eine der übrig bleibenden Farben, wenn man alle Farben seiner benachbarten Knoten auflistet)
    • Füge in coloring das Tupel (Knoten, Farbe) für den frisch gefärbten Knoten ein, und gib coloring zurück.
  • Suche nach Knoten mit Grad 5. Nenne ihn $k$ und:
    • Entferne $k$ aus G.
    • Setze coloring := 5color(G)
    • Färbe den Graphen G gemäß coloring ein.
    • Schreibe die an $k$ anliegenden Knoten im Uhrzeigersinn in eine Liste $L$ (wobei wir hierbei eine beliebige planare Einbettung betrachten).
    • Führe eine DFS vom ersten Knoten der Liste aus aus, wobei die DFS so modifiziert ist, dass sie nur über Knoten geht, deren Farbe mit einer der Farben des ersten/dritten Knoten der Liste übereinstimmen.
    • Falls die DFS den dritten Knoten der Liste nicht erreicht:
      • Färbe alle Knoten, die die DFS erreicht hat, um (wenn sie zuvor die Farbe des ersten Knoten der Liste hatten, färbe sie in der Farbe des dritten Knoten der Liste und umgekehrt).
      • Füge den Knoten $k$ in den Graphen G ein.
      • Bestimme dessen Färbung (eine Farbe ist nun frei).
      • Füge die Färbung des Knoten k in coloring ein, und gib coloring aus.
    • Falls die DFS den dritten Knoten der Liste erreicht:
      • Führe eine DFS vom zweiten Knoten der Liste aus aus, wobei die DFS so modifiziert ist, dass sie nur über Knoten geht, deren Farbe mit einer der Farben des zweiten/vierten Knoten der Liste übereinstimmen.
      • Färbe alle Knoten, die die DFS erreicht hat, um (wenn sie zuvor die Farbe des zweiten Knoten der Liste hatten, färbe sie in der Farbe des vierten Knoten der Liste und umgekehrt).
      • Füge den Knoten $k$ in den Graphen G ein.
      • Bestimme dessen Färbung (eine Farbe ist nun frei).
      • Füge die Färbung des Knoten k in coloring ein, und gib coloring aus.

Alternativer Beweis

Paul Kainen lieferte im Jahr 1974 einen vereinfachten Beweis des Fünf-Farben-Satzes, der auf Kantenkontraktion und der Nichtplanarität des vollständigen Graphs K₆ beruht. Dieser Beweis lässt sich auf Graphen verallgemeinern, die durch Löschen von 2 Kanten planar gemacht werden können.

Literatur

• P. J Heawood: Map-Colour Theorems. In: Quarterly Journal of Mathematics, Oxford, 24, S. 332–338
• Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise. Springer, 4-te Ausgabe, 2014, ISBN 9783662444573, S. 293–296

Weblinks

• Matroids Matheplanet: Ausführlicher Beweis mit Grafiken.
• Sabrina Klöpfel: Sabrina Klöpfel - 5 Farben Satz - Ausarbeitung.pdf Der Fünffarbensatz. Seminarausarbeitung, Uni Marburg