Vier-Farben-Satz

Der Vier-Farben-Satz (früher auch als Vier-Farben-Vermutung oder Vier-Farben-Problem bekannt) der Graphentheorie, Topologie bzw Kartographie besagt, dass vier Farben immer ausreichen, um eine beliebige Landkarte so einzufärben, dass keine zwei angrenzenden Länder die gleiche Farbe bekommen. Dies 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 Enklaven bzw. Exklaven vorhanden sind.

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 einfachsten mit Hilfe der Graphentheorie beschreiben. Man fragt ob die Knoten jedes planaren Graphen mit maximal vier Farben so gefärbt werden können, dass keine benachbarten Knoten die gleiche Farbe tragen. Oder kürzer: "Ist jeder planare Graph 4-fä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, die seit ihrem Beweis im Jahre 1968 "Theorem von Ringel-Youngs" heißt (s. englische Version). 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.