Vier-Farben-Satz
Das Vier-Farben-Problem ist die Frage, ob vier Farben immer ausreichen, um eine beliebige Landkarte so einzufärben, dass keine zwei angrenzenden Länder die gleiche Farbe haben.
(Ein gemeinsamer Punkt zählt nicht als Grenze.)
Dass dem so ist, wurde als erstes 1853 von Francis Guthrie als Vermutung veröffentlicht.
Es ist offensichtlich, dass drei Farben nicht ausreichen.
Mathematiker konnten beweisen, dass fünf Farben in jedem Fall ausreichen.
Ein Beweis für vier Farben konnte lange nicht gefunden werden.
Erst 1977 konnten Ken Appel und Wolfgang Haken einen solchen finden.
Der Beweis reduzierte die Anzahl der problematischen Fälle von Unendlich auf 1936 (eine spätere Version sogar 1476), die durch einen Computer einzeln geprüft wurden.
1996 konnten Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas einen modifizierten Beweis finden, der die Fälle auf 633 reduzierte.
Auch diese mussten per Computer geprüft werden.
Das Vier-Farben-Problem war das erste große mathematische Problem, das mit Hilfe von Computern gelöst wurde.
Deshalb wurde der Beweis von einigen Mathematikern nicht anerkannt, da er nicht direkt durch einen Menschen nachvollzogen werden kann.
Schließlich muss man sich auf die Korrektheit des Compilers und der Hardware verlassen.
Auch die mathematische Eleganz des Beweises wurde kritisiert ("Ein guter Beweis liest sich wie ein Gedicht - dieser sieht aus wie ein Telefonbuch!").
Formale Formulierung
Formal lässt sich das Problem am besten mit Hilfe der Graphentheorie beschreiben.
Man sucht einen planaren Graphen, dessen Knoten mit maximal vier Farben gefärbt werden können, sodass keine benachbarten Knoten die gleiche Farbe haben.
Oder kürzer: "Ist jeder planare Graph vierfärbbar?"
Dabei wird jedem Land der Karte genau ein Knoten zugewiesen und zwei Knoten, deren Länder angrenzen, verbunden.
Bemerkung:
Wenn (so wie in der Realität öfters der Fall) ein Land auf mehrere nicht-angrenzende Gebiete verteilt ist (Kolonien, Enklaven, ...), dann ist der zugehörige Graph nicht planar und es sind möglicherweise mehr als vier Farben zur Färbung notwendig.
/Diskussion