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 K5 oder K3,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 K5 und K3,3 kein kombinatorisches Dual. Die Theorie der Matroide hatte zahlreiche Anwendungen, zu einer Lösung des Vier-Farben-Problems führte sie aber nicht.

1 / 2 / Auf einer Seite lesen

Kommentare (5)

  1. #1 Joachim
    29. April 2021

    Wirklich vielen Dank für diese Serie.

    Allerdings fällt es mir wirklich nicht leicht, den Ausführungen zu folgen. Entweder ist man Mathematiker. Dann dürfte man den Artikel eigentlich nicht benötigen oder man ist es nicht, dann braucht man doch – untertrieben – etwas länger. So frage ich mich, für wen ist das eigentlich? Das ich das gut finde kann der Autor ja nicht ahnen. Der Gedanke “für mich” ist vermessen. Oder ist das wie Jazz, die Freude am Spielen? So oder so, ich mag Jazz.

    Vielleicht wäre es irgendwann sinnvoll, etwas zu Computer gestützten Beweisen zu sagen. Auch wenn es hier beim Vier-Farben-Problem keinen Zweifel gibt, etwa np-Vollständigkeit, das Halteproblem usw spielen hier keine Rolle. Es kann aber immer “ein Bit kippen”. Die Wahrscheinlichkeit, dass immer der selbe Fehler immer wieder auftritt ist ungeheuer klein, doch nicht Null. So ist das einfach kein mathematischer Beweis.

    Eins noch wo ich schmunzeln musste: Das Geschlecht einer Fläche letztlch als die Anzahl Löcher zu definieren ist … Wer (Alfred Clebsch) denkt sich denn sowas aus?

  2. #2 Lausbub
    30. April 2021

    Die Antwort lautet 42, meine Herren.

  3. #3 Joachim
    30. April 2021

    @Lausbub: Nach meiner Analyse ist das falsch. 42 war die Fehlermeldung des Rechners beim Speicherüberlauf des Programms zur Suche nach der Antwort auf alle Fragen. Der Speicher war so knapp, dass er sogar die Frage löschen musste. Und so…

  4. #4 Jere
    30. April 2021

    @Joachim: Ich kann die Frage nach dem Zielpublikum nicht beantworten, aber ich glaube, der Gedanke, als Mathematikerin “dürfte man den Artikel eigentlich nicht benötigen” ist ein bisschen zu viel der Ehre: Die wenigsten kennen sich wirklich in allen Gebieten perfekt aus.

    Ich selbst finde tatsächlich spannend, wie ich bei manchen Artikeln, die näher bei meinen Schwerpunkten liegen, querlesen kann, ohne dass irgendwas unklar bleibt, während ich vor anderen vermutlich mit dem selben Unverständnis und Faszination sitze wie “der Laie”

  5. #5 Joachim
    30. April 2021

    @Jere #4: diese Antwort finde ich plausibel.

    Allerdings, und das spricht aus meiner Sicht sehr für diesen Blog, werden sehr viele sehr fundamentale oder für Mathematiker wichtige Themen und deren Geschichte angesprochen. In sehr vielen Fällen kann ich mir nicht vorstellen, dass ein Mathematiker da nun gar nicht mitkommt.

    Dennoch, beruhigend, dass nicht nur ich da so manchmal (nee meistens!) das Hirn einschalten und nachdenken/nachschlagen muss. Das ist es sogar, was ich hier so schätze.

    “Another fine tune, you’ve got me into” (Gilgamesh, 1978) um es mal musikalisch auszudrücken.