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

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.

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.