Theorema Magnum MCMLXXVI: der Vier-Farben-Satz

Die Frage, ob jede Landkarte mit vier Farben gefärbt werden kann, wurde erstmals 1852 von de Morgan in einem Brief an Hamilton formuliert. Kempes gefeierter Beweis von 1878 stellte sich zwölf Jahre später als fehlerhaft heraus. Heawood, der den Fehler im Beweis gefunden hatte, bewies immerhin korrekt die Färbbarkeit mit fünf Farben, und er fand eine obere Schranke für die Anzahl benötigter Farben auf Flächen höheren Geschlechts, deren Optimalität er aber nicht beweisen konnte.

Zu einer ebenen Landkarte hat man den ebenfalls in die Ebene eingebetteten dualen Graphen: Ecken entsprechen Ländern, Kanten den Grenzlinien. Die Kartenfärbung der ursprünglichen Karte entspricht einer Eckenfärbung des Graphen. Um die so aufgeworfene Frage, ob sich jeder ebene Graph mit vier Farben eckenfärben läßt, entwickelte sich im 20. Jahrhundert eine ganze Teilwissenschaft, die Graphentheorie. (Genauer die Theorie endlicher Graphen. Dénes König schrieb 1936 ein Buch über endliche und unendliche Graphen, wo er mit einer Art Kompaktheitsargument bewies, dass der Vier-Farben-Satz für unendliche Graphen aus dem für endliche Graphen folgt.)

Natürlich läßt sich nicht jeder Graph mit vier Farben einfärben. Es mußte bei der Vier-Farben-Vermutung also um eine spezielle Eigenschaft ebener Graphen gehen.

Spezifisch für ebene Graphen ist zunächst die aus dem Jordanschen Kurvensatz folgende Gleichung E-K+F=2 für die Anzahl der Ecken, Kanten und Flächen des ursprünglichen Graphen. Aus dieser Formel kann man leicht herleiten, dass es in jeder Karte ein Land mit höchstens fünf Nachbarn gibt. Andernfalls hätte man die Ungleichung 6F≤2K, woraus mit 3E≤2K der Widerspruch E-K+F≤0 folgen würde. Das genügt bereits, um die Färbbarkeit mit 6 Farben durch vollständige Induktion nach der Anzahl der Länder zu beweisen: man kann die anderen Länder (bis auf jenes mit höchstens 5 Nachbarn) nach Induktionsannahme mit 6 Farben färben und färbt dann das verbliebene Land einfach mit einer Farbe, die bei den fünf Nachbarn nicht verwendet worden ist. 
Ähnlich führte Heawood den Induktionsbeweis für den Fünf-Farben-Satz durch den Beweis der Existenz gewisser unvermeidbarer Strukturen in ebenen Graphen. Garrett Birkhoff und viele andere Autoren gingen mit diesem Ansatz auch die Vier-Farben-Vermutung an und konnten die Anzahl unvermeidbarer Konfigurationen nach und nach vergrößern. Letztlich war dieser Ansatz für die Vier-Farben-Vermutung aber zunächst nicht erfolgreich und so suchte man im 20. Jahrhundert lange nach anderen Ansätzen und auch nach anderen Charakterisierungen ebener Graphen. Kuratowski charakterisierte ebene Graphen 1930 dadurch, dass sie keine Unterteilung des K₅ oder K_3,3 enthalten. Birkhoff hatte 1912 bewiesen, dass die durch P(n)=#n-Färbungen definierte Funktion ein Polynom ist – das chromatische Polynom. Die Vier-Farben-Vermutung ist natürlich äquivalent zu P(4)>0.
Hassler Whitney fand in seiner Dissertation von 1932 tiefliegende Resultate über ebene Graphen. Neben einem Satz über die Existenz geschlossener, alle Ecken durchlaufender Kreise in 4-zusammenhängenden ebenen Graphen, und einer wesentlichen Vereinfachung der Berechnung des chromatischen Polynoms – er konnte die Anzahl der zu betrachtenden Teilgraphen drastisch reduzieren – war es vor allem die Entdeckung der Matroide, die eine neue Entwicklung einleitete. Ihm gelang es, die vermittels der Bijektion Ecken<-->Länder gegebene Dualität ebener Graphen rein kombinatorisch zu formulieren und daraus eine neue Charakterisierung ebener Graphen herzuleiten.  
Ausgehend von den dualen Begriffen Baum-Kreis arbeitete er dann die genauen Axiome für die Existenz eines kombinatorischen Duals in beliebigen Mengensystemen heraus – den Begriff des Matroids. Ein Matroid ist eine Struktur aus einer endlichen Menge und einer Familie “unabhängiger” Teilmengen. Die Anwendung auf die Graphentheorie besteht in der Betrachtung der kreisfreien Teilgraphen eines (als Menge von Kanten) gegebenen Graphen als unabhängiger Mengen. Analog zu Kuratowskis Charakterisierung ebener Graphen kann man beweisen, dass ein Graph genau dann ein ebener Graph ist, wenn sein duales Matroid das Matroid eines Graphen ist. Zum Beispiel haben K₅ und K_3,3 kein kombinatorisches Dual. Die Theorie der Matroide hatte zahlreiche Anwendungen, zu einer Lösung des Vier-Farben-Problems führte sie aber nicht.

1968 bewiesen Ringel und Young die Heawood-Vermutung für Flächen höheren Geschlechts, also die Formel für die Anzahl benötigter Farben in Abhängigkeit vom Geschlecht. Beispielsweise braucht man – was schon Heawood bewiesen hatte – immer sieben Farben, um eine Karte auf dem Torus zu färben.

Zum klassischen Vier-Farben-Problem in der Ebene hatte seit den 30er Jahren aber eigentlich nur noch Heinrich Heesch gearbeitet. Er war in Göttingen Assistent von Hermann Weyl gewesen, hatte damals über Gruppen und Ornamente gearbeitet und als Reaktion auf die politischen Säuberungen 1933 seine Stelle an der Universität aufgegeben, dann bis einige Jahre nach dem Krieg als Privatgelehrter im Kieler Haus seiner Eltern gewohnt. Neben anderen Forschungen hatte er schon vor dem Krieg als erster den ursprünglichen Ansatz im Vier-Farben-Problem wieder aufgenommen und große Fortschritte sowohl im Reduzibilitätsaspekt wie in der Analyse unvermeidlicher Mengen erzielt. (Über die Struktur eines minimales Gegenbeispiel war durch Birkhoff einiges bekannt: jede Ecke hat Grad mindestens 5, nach Polyederformel gibt es mindestens 12 Ecken von Grad 5, also mindestens so viele wie im Gerüstgraph des Ikosaeders, es gibt keinen trennenden Graph der Länge < 5 und bei einem trennendem Kreis der Länge 5 ist eines der Gebiete nur eine Ecke. Gesucht war in Birkhoffs Programm dann eine unvermeidbare Menge reduzierbarer Konfigurationen. Eine Reihe von Arbeiten hatten reduzierbare Konfigurationen gefunden, aber man war weit entfernt von einer unvermeidbaren Menge.) Heesch war bald klar geworden, dass eine unvermeidliche Menge möglicherweise tausende, jedenfalls zu viele, Konfigurationen enthalten musste, um ohne Rechenhilfe bewältigt werden zu können. Demzufolge wurde die Geschichte des Vier-Farben-Problems eine Geschichte der Entwicklung von Hochleistungsrechnern. Nachdem er eine Lehrtätigkeit an der Technischen Hochschule Hannover aufgenommen hatte, leistete Heesch später auch grundlegende Beiträge zu einer computergestützten Lösung des Vier-Farben-Problems. Gelöst wurde das Problem aber nicht von ihm, sondern von Appel und Haken. Haken, der die Theorie der Normalflächen in der dreidimensionalen Topologie eingeführt und unter anderem einen theoretischen Algorithmus zur Klassifikation von Haken-Mannigfaltigkeiten entwickelt hatte, trug zur Lösung des Vier-Farben-Problems die konzeptionellen Ideen bei, während Appel den Großteil der Programmierung durchführte. In ihrem ersten Beweis fanden sie 1825 unvermeidbare Strukturen, in einer späteren Version kamen sie mit 1478 aus. Der Beweis der Unvermeidbarkeit dieser Strukturen kam durch massiven Computereinsatz zustande und konnte nur per Computer verifiziert werden. Sie benötigten 1200 Stunden Rechenzeit auf einer IBM 360 mit 64 kB Arbeitsspeicher - solche Ressourcen hatte Heesch in Hannover nicht zur Verfügung gehabt. Die Universität Illinois brachte zur Feier des Beweises einen Poststempel "Vier Farben genügen!" heraus. 1996 fanden Robertson, Sanders, Seymour und Thomas einen Beweis mit ‘nur’ 633 unvermeidbaren Strukturen, der aber auch nur von einem Computer geprüft werden kann. Trotz seiner Bekanntheit nimmt das Vier-Farben-Problem eine einsame Stelle in der Mathematik ein, weil der Beweis unangemessen lang und ohne Beziehungen zu anderen Teilen der Mathematik ist. Bild: https://commons.wikimedia.org/wiki/File:Wolfgang_Haken_2008.jpg