4-Farben-Satz

Einleitung

Der vier Farben Satz beschreibt, dass man in jedem planaren Graphen die Knoten mit 4 Farben färben kann, ohne dass eine Kante an beiden Endknoten die gleiche Farbe hat.

Viel anschaulicher bedeutet das, dass man jede Landkarte, egal welche Form und Anordnung die Länder haben, mit 4 Farben färben kann, ohne dass zwei benachbarte Länder (also zwei Länder, die sich eine Grenze teilen) die gleiche Farbe haben.

//Bild einfügen

Planarer was?

Ein Graph besteht aus Knoten und Kanten. Eine Kante verbindet jeweils zwei Knoten. Man kann sich Knoten gut als Punkte und Kanten als Verbindungen (Linien) zwischen den Knoten vorstellen, aber Graphen können alles mögliche repräsentieren, beispielsweise können Knoten für Länder stehen und Kanten für Grenzen zwischen Ländern (sodass genau dann eine Kante zwischen zwei Ländern existiert, wenn diese benachbart sind).

Ein planarer Graph ist nun einfach ein Graph, der in einer 2-dimensionalen Ebene, mit Punkten als Knoten und Linien als Kanten, gezeichnet werden kann, ohne dass sich zwei Kanten schneiden. Dies ist für das Landkarten-Problem auf jeden Fall erfüllt, da man offensichtlich einfach die Länder durch Punkte und die Ländergrenzen durch Linien zwischen den Punkten ersetzten kann, sodass man einen Graphen erhält, wo sich keine Linien überschneiden müssen, da sich unterschiedliche Ländergrenzen auch nicht überschneiden können.

5-Farben-Satz

Der 5-Farben Satz ist der kleine langweilige Bruder des 4-Farben Satzes. Er besagt, dass man die Knoten eines planaren Graphen mit 5 Farben färben kann, ohne dass zwei Knoten, die durch eine Kante direkt miteinander verbunden sind, die gleiche Farbe haben. Also einfach wie der 4-Farben Satz nur mit 5 Farben. Offensichtlich impliziert der 4-Farben Satz den 5-Farben Satz.

Dafür kann man den 5-Farben Satz verständlich beweisen (und der Beweis ist schön). Für Informationen über den Beweis vom 4-Farben Satz siehe nächste Sektion.

Um den Beweis zu verstehen, braucht man möglicherweise etwas mehr Wissen über planare Graphen, als wir jetzt hier erklären. Wenn etwas nicht verständlich ist (wie bspw. was ist die eulersche Polyederformel und was besagt sie im Kontext von planaren Graphen), gerne einfach googlen. ;)

Beweis vom 5-Farben-Satz

Der Beweis ist deutlich einfacher zu verstehen, wenn man ihn graphisch präsentiert bekommt, wie beispielsweise in diesem Video: https://www.youtube.com/watch?v=42-ws3bkrKM&t=972s (the proof starts at time 4:50)

Im Folgenden bezeichne '5-färbbar', dass man die Knoten eines Graphen mit 5 Farben färben kann, sodass keine zwei Knoten, die durch eine Kante verbunden sind, die gleiche Farbe haben.

Der Satz wird durch vollständige Induktion bewiesen:

Induktionsanfang: Offensichtlich ist ein Graph mit einem Knoten mit 5-färbbar.

Induktionsschritt: Es wird gezeigt, dass wenn jeder planare Graph mit n-1 Knoten 5-färbbar ist, auch jeder planare Graph mit n Knoten 5-färbbar ist.

Jeder planare Graph enthält einen Knoten Grad von maximal 5, bzw. es gibt einen Knoten mit maximal 5 Nachbarknoten. Dies folgt aus einer einfachen Umformung der eulerschen Polyederformel.

Nun können wir folgende zwei Fälle separat betrachten:

Fall 1: Es gibt einen Knoten vom Grad von maximal 4. Da der Graph ohne diesen Knoten nach der Induktionsannahme 5-färbbar ist, können wir die Färbung dieses Graphen einfach für den Graph mit dem Knoten übernehmen und den Knoten in einer Farbe färben, die kein Nachbarknoten von dem Knoten hat. Da es 5 Farben und nur maximal 4 Nachbarknoten gibt, existiert eine solche Farbe.

Fall 2: Es gibt keinen Knoten vom Grad von maximal 4. Wie oben schon beschrieben, gibt es jedoch einen Knoten mit maximal 5 Nachbarknoten. Sei dieser Knoten der Knoten w. Nach Induktionsannahme ist der Graph ohne w 5-färbbar. Hier gibt es wieder 2 Fälle zu unterscheiden:

Fall 2.1: Die Nachbarknoten von w sind nur mit maximal unterschiedlichen Farben gefärbt. In diesem Fall können wir w einfah mit einer Farbe färben, mit der kein Nachbarknoten gefärbt ist.

Fall 2.2: Die 5 Nachbarknoten sind mit 5 unterschiedlichen Farben gefärbt. Wir bezeichnen die Nachbarknoten von w als w1, w2, ..., w5 im Uhrzeigersinn. Nun überprüfen wir, ob es einen Weg von w1 nach w3 gibt, der nicht über den Knoten w geht, sodass die Knoten auf diesem Weg nur mit den Farben von w1 und w3 gefärbt sind.

Fall 2.2.1: Nein, es existiert kein solcher Weg. Dann wird der Knoten w auf die Farbe von w1 und w1 auf die Farbe von w3 umgefärbt. Die Nachbarknoten von w1 mit der Farbe von w3 werden dann auf die ursprüngliche Farbe von w1 umgefärbt und die Nachbarknoten von diesen Knoten mit der ursprünglichen Farbe von w1 wieder auf die Farbe von w3 umgefärbt und so weiter. Der resultierende Graph ist offensichtlich mit 5 Farben so gefärbt, dass keine zwei Knoten, die durch eine Kante direkt verbunden sind, die gleiche Farbe haben.

Fall 2.2.2: Ja, ein solcher Weg existiert. Da der Graph planar ist, kann es keinen Weg mit von w2 zu w4 geben, der nicht über w geht, sodass alle Knoten des Weges nur mit den Farben von w2 und w4 gefärbt sind, da ein solcher Weg unweigerlich durch einen Knoten auf dem beschriebenen Weg zwischen w1 und w3 gehen müsste, der ja entweder die Farbe von w1 oder w3 hat. Daher können wir nun den Knoten w mit der Farbe von w2 färben, den Knoten w2 mit der Farbe von w4, die Nachbarknoten von w2, die die Farbe von w4 haben mit der ursprünglichen Farbe von w2 färben, und so weiter, sodass der resultierende Graph wie gewünscht 5-gefärbbt ist. (Wie bei Fall 2.2.1, nur mit w2 und w4 anstatt mit w1 und w3.)

4-Farben-Satz

Der 4-Farben-Satz wurde 1852 erstmals von dem südafrikanischen Mathematiker Francis Guthrie als Vermutung aufgestellt. Bereits im 19. Jahrhundert wurden einige vermeintliche Beweise dieses Satzes aufgestellt, jedoch stellten sich alle Versuche im Nachhinein als inkorrekt heraus.

Erst 1976 verkündeten Kenneth Appel und Wolfgang Hagen der University of Illinois, dass es ihnen gelang, den Satz durch einen computergestützten Beweis zu zeigen. Der Beweis widerlegte, dass es eine minimale Anzahl an Flächen gibt, sodass der Graph nicht mehr vierfärbbar wäre, indem die unendliche Menge von Graphen auf 1834 (später auf 633) relevante Möglichkeiten vereinfacht wurde. Zu seine Zeit war dies der erste computergestützte Beweis seiner Art.