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.