Fünf-Farben-Satz

aus Wikipedia, der freien Enzyklopädie

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 ungleich leichter zu beweisen.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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, das 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 einen 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 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$ kan 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.