Vier-Farben-Satz

Der Vier-Farben-Satz (früher auch als Vier-Farben-Vermutung oder Vier-Farben-Problem bekannt) in der Kartographie bzw. Graphentheorie besagt, dass vier Farben immer ausreichen, um eine beliebige Landkarte so einzufärben, dass keine zwei angrenzenden Länder die gleiche Farbe bekommen. Dabei zählt ein gemeinsamer Punkt nicht als Grenze. Jedes Land besteht aus einer zusammenhängenden Fläche, d.h. es gibt keine Enklaven und keine Exklaven.

Der Satz wurde erstmals 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.

Der Vier-Farben-Satz 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.

Das Vier-Farben Problem ist ein Spezialfall der Heawood-Vermutung. Das klassische Vier-Farben Problem betrifft Landkarten, die auf einer Ebene oder Kugeloberfläche liegen; die 'Heawood-Vermutung' stellt das analoge Problem für allgemeine Oberflächen, etwa die Kleinsche Flasche (6 Farben), das Möbiusband (6 Farben), die Projektive Ebene (6 Farben) und den Torus (7 Farben).

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.

Literatur zum Beweis

Kenneth Appel and Wolfgang Haken, Every Planar Map is Four Colorable, Contemp. Math., vol. 98, Amer. Math. Soc., Providence, RI, 1989.