Die Schreibtischunterlage in meinem Kinderzimmer war wie bei vielen anderen auch eine Weltkarte. Darauf waren alle damaligen Staaten abgebildet, die der Sichtbarkeit halber unterschiedlich eingefärbt waren. Welche Farben das genau waren, weiß ich nicht mehr. Aber inzwischen ist klar: Es sind nur vier Farben nötig, um jede beliebige Karte so auszumalen, dass aneinandergrenzende Länder stets verschieden gefärbt sind. Was sich nach einem einfachen Problem anhört, bereitete Mathematikerinnen und Mathematikern mehr als 120 Jahre lang Kopfzerbrechen. Und richtig zufrieden sind die Fachleute bis heute nicht. Der 1976 vorgestellte Beweis des Vier-Farben-Satzes markierte eine Zeitenwende in der Mathematikgeschichte: Es war der erste Beweis, der auf die Unterstützung von Computern angewiesen ist.

Die lange Geschichte des Vier-Farben-Satzes beginnt mit dem britischen Studenten Francis Guthrie, der 1852 die damaligen englischen Grafschaften in einer Karte färben wollte – vermutlich eine kreative Art der Prokrastination. Obwohl die Karte so kleinteilig war, fiel ihm auf, dass er nur vier Farben benötigte. Deshalb fragte er sich, ob sich das auch mathematisch beweisen ließe und wandte sich dafür an seinen jüngeren Bruder Frederick, der am University College in London Mathematik studierte. Der scheiterte jedoch an einem Beweis und erzählte seinem Betreuer, dem renommierten Mathematiker Augustus De Morgan, von dem Problem.

De Morgans Interesse war sofort geweckt. Doch auch ihm gelang es nicht, die Vermutung zu beweisen. Er fing also an, mit seinen Kollegen darüber zu sprechen, wodurch die Vier-Farben-Vermutung langsam an Bekanntheit gewann. Das Interesse wuchs schlagartig an, als der englische Mathematiker Arthur Cayley 1878 in der britischen Gelehrtengesellschaft Royal Society fragte, ob jemand die Vermutung schon bewiesen habe. Nur ein Jahr später veröffentlichte sein Kollege Sir Alfred Kempe einen Beweis im »American Journal of Mathematics«. Doch wie sich elf Jahre später herausstellen sollte, enthielt die Arbeit einen Fehler.

Dennoch war Kempes Ansatz innovativ und diente auch als Vorlage für den 100 Jahre später erschienenen, endgültigen Beweis. Aber wie geht man ein solches Problem an? Um ein Gefühl dafür zu bekommen, kann man zunächst versuchen, verschiedene echte Karten zu färben. Um es möglichst kompliziert zu machen, könnte man etwa alle Landkreise Deutschlands kolorieren:

Wie Sie feststellen werden, gelingt das mit vier Farben. Das ist aber natürlich kein Beweis für die Vier-Farben-Vermutung. Als nächsten Schritt kann man versuchen, sich eine möglichst komplexe, fiktive Karte auszudenken, bei denen viele Länder aneinandergrenzen. Auch hier wird man feststellen, dass man mit vier Farben auskommt. Um die Vermutung zu beweisen, muss man jedoch ausräumen, dass es irgendeine Karte gibt, die fünf verschiedene Farben benötigt. Mit einem einzigen Gegenbeispiel hätte man die Vermutung widerlegt.

Von Karten zu Netzwerken

Um die Aufgabe zu vereinfachen, haben Mathematiker das getan, was sie am besten können: abstrahieren. Dafür haben sie versucht, sich auf die relevanten Informationen des Problems zu konzentrieren. Zum Beispiel spielt die genaue Form der aneinandergrenzenden Regionen bei der Vier-Farben-Vermutung keine Rolle. Das Einzige, was zählt, ist, welche Länder oder Landkreise benachbart sind. Daher kann man sie durch Punkte darstellen und durch eine Kante verbinden, falls sie aneinandergrenzen. Statt einer Karte erhält man somit ein Netzwerk.

Zwar lässt sich jede Karte in einen Graphen verwandeln, aber nicht andersherum. Es gibt Netzwerke, die keiner Karte entsprechen. Das ist immer dann der Fall, wenn sich die Kanten eines Graphen schneiden und nicht entwirren lassen, ein Beispiel dafür ist das »Haus vom Nikolaus«. Da die Regionen im Vier-Farben-Problem eine endliche Ausdehnung und Grenze haben und man nur direkt benachbarte Bereiche betrachtet, entstehen daraus immer Netzwerke, deren Kanten sich nicht kreuzen, so genannte planare Graphen.

Solche Graphen haben eine wichtige Eigenschaft: Sie enthalten stets einen Punkt, der bloß mit fünf oder weniger Kanten verbunden ist. Diese Tatsache nutzte Kempe, um seinen – wie sich später herausstellte, fehlerhaften – Beweis zu führen. Dafür wählte er die Methode der vollständigen Induktion: Man stellt eine Behauptung auf und zeigt, dass sie für einen kleinen Spezialfall gilt (etwa für eine Karte mit nur vier Ländern). Anhand der Annahme, die Behauptung, also der Vier-Farben-Satz, gelte für alle Karten mit n Ländern, zeigt man, dass der Satz dann automatisch auch für Karten mit n+1 Ländern wahr ist. Damit hätte man bewiesen, dass der Vier-Farben-Satz für Karten mit 4, 5, 6, 7, … Ländern stimmt, also für alle Karten.

Ein fehlerhafter Beweis

Dass man eine Karte mit vier Ländern mit vier verschiedenen Farben kolorieren kann, ist klar. Nun kann man sich eine Karte mit n+1 Ländern ansehen. Da diese einem planaren Graphen entspricht, muss dieser mindestens einen Punkt haben, der von höchstens fünf anderen Punkten umgeben ist. Nun entfernt man diesen Punkt und alle dazugehörigen Kanten aus dem Graphen.

Man hat damit also ein Netzwerk mit n Punkten. Die Induktionsannahme besagt, dass sich ein solcher Graph durch vier Farben kolorieren lässt. Wenn man also den Punkt wieder in den Graphen einsetzt, muss man zeigen, dass sich das neue Netzwerk ebenfalls durch bloß vier Farben ausmalen lässt. Wenn das möglich ist, ist der Vier-Farben-Satz bewiesen.

Kempe tat dies, indem er die verschiedenen Fälle betrachtete, die eintreten können, wenn man den entfernten Punkt wieder in das Netzwerk einfügt.

1. Falls der Punkt zuvor nur mit drei oder weniger Punkten verbunden war, dann kann man ihn problemlos wieder einfügen und färben: Er erhält die vierte Farbe, die sich von den anderen drei gefärbten Punkten unterscheidet. In diesem Fall ist der Graph mit n+1 Punkten problemlos durch vier Farben kolorierbar.
2. Falls der Punkt mit vier unterschiedlich gefärbten Punkten verbunden war, gestaltet sich das Ganze etwas schwieriger. Kempe entwarf daher eine Methode, um alle Punkte des Graphen umzufärben, damit am Ende vier Farben genügen. Wenn der neu hinzugefügte Punkt mit vier anderen verbunden ist, befindet er sich in der Mitte von vier sich gegenüberliegenden Punkten. Kempe wollte versuchen, die Farben im gesamten Graphen so zu ändern, dass zwei sich gegenüberliegende Punkte die gleiche Farbe annehmen, also entweder v₁ und v₃ oder v₂ und v₄. Angenommen, man schnappt sich v₁ und v₃: Diese darf man nur dann nicht gleich färben, wenn sie durch eine »Kempe-Kette« miteinander verbunden sind. Das heißt, v₁ und v₃ sind durch eine Kette von Punkten verbunden, die abwechselnd die Farbe von v₁ und v₃ haben und die beiden Endpunkte dadurch zwingt, unterschiedliche Farben zu haben. Wenn es aber eine solche Kette gibt, dann können v₂ und v₄ nicht durch eine Kempe-Kette verbunden sein. Denn sonst würden sich die beiden Ketten kreuzen, was in planaren Graphen nicht möglich ist. Somit konnte Kempe beweisen, dass sich in diesem Fall alle Färbungen des Graphen so ändern lassen, damit v₂ und v₄ gleich gefärbt sind – und der hinzugefügte Vertex erhält dann die übrige Farbe.
3. Den letzten Fall, den Kempe also untersuchen musste, ist jener, bei dem der entfernte Punkt mit fünf anderen verbunden war. Hierbei nutzte der Mathematiker dieselbe Argumentation wie zuvor: Nicht alle fünf umgebenden Punkte können durch Kempe-Ketten verbunden sein. Daher kann man zwei Punktepaare je gleich färben und kommt somit mit vier Farben aus. In der obigen Graphik wären dann v₂ und v₄ gelb sowie v₁ und v₃ sowie v₅ und v₃ blau.

Doch wie sich herausstellte, lauerte in der letzten Fallunterscheidung ein Fehler. Im Jahr 1890, erst elf Jahre nach Kempes Veröffentlichung, erkannte der Mathematiker Percy John Heawood, dass die Argumentation für den Spezialfall mit fünf Verbindungspunkten nicht korrekt war. Denn der Farbwechsel in einer Kempe-Kette kann Auswirkungen auf die Färbungen der anderen Punkte im Graphen haben. Damit hatte Heawood zwar den Beweis von Kempe ausgehebelt, das bedeutet allerdings nicht, dass die Vier-Farben-Vermutung falsch ist.

Tatsächlich folgt aus Kempes Argumentation – wenn man den fehlerhaften Teil ignoriert –, dass man höchstens fünf Farben braucht, um eine Karte zu färben. Ein konkretes Beispiel einer solchen Karte, die wirklich fünf Farben benötigt, hatte man aber nicht. Deshalb vermutete die Fachwelt weiterhin, die Vier-Farben-Vermutung sei korrekt.

Von der Ebene weg – und hin zu Donuts und Brezeln

In den folgenden Jahrzehnten versuchte Heawood, einen Beweis für die Vermutung zu finden, doch er scheiterte. Er untersuchte aber auch Spezialfälle und Verallgemeinerungen des Problems. Etwa: Wie viele Farben man braucht, um eine Karte auf anderen Oberflächen als der Ebene zu kolorieren, zum Beispiel auf einem donutförmigen Objekt (Torus)? Wie er herausfand, lautet die Antwort sieben.

Heawood machte große Fortschritte und formulierte die »Heawood-Vermutung«: Um eine Karte auf einer geschlossenen Oberfläche mit h Löchern zu färben, braucht man höchstens 3,5 + 0,5·√(1+48h) Farben (wenn der Zahlenwert keine ganze Zahl ist, muss man das Ergebnis abrunden). Falls Sie sich über diese komplizierte Form wundern: Sie sind damit nicht allein, sie hat auch Fachleute erstaunt.

Den Spezialfall des Torus (h=1) konnte er beweisen. Tatsächlich glaubte Heawood, die ungewöhnliche Formel allgemein für Oberflächen mit h Löchern bewiesen zu haben, aus der sich eine seltsame Zahlenfolge für die Anzahl benötigter Farben ergibt: 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, 16, 16, 17, 17, 18, … Doch auch ihm war ein Fehler unterlaufen: Die Formel gab für Oberflächen mit mehr als einem Loch bloß die maximale Anzahl an Farben an. Er konnte aber nicht ausräumen, dass man vielleicht weniger bräuchte. Das gelang Gerhard Ringel und J. W. T. Youngs aber schließlich im Jahr 1968.

Ringel und Youngs bewiesen die Heawood-Vermutung für alle Lochzahlen h, außer für h=0 (also eine Kugel oder Ebene) sowie die Kleinsche Flasche. Der Vier-Farben-Satz ist extrem hartnäckig: Nutzt man dieselben Überlegungen wie für die Heawood-Vermutung kommt dabei nur heraus, dass die maximale Anzahl an Farben fünf lautet. Man kam damit also nicht weiter.

Langsam kristallisierte sich heraus, wie man stattdessen vorgehen musste. Alles lief auf etliche Fallunterscheidungen hinaus: Welche Konstellationen von Punkten und Kanten können in planaren Graphen vorkommen und wie färbt man das Netzwerk in den jeweiligen Situationen ein?

Der erste Beweis mit Hilfe eines Computers

Der Mathematiker Heinrich Heesch lieferte in den 1960er Jahren einen Plan, wie man den Vier-Farben-Satz beweisen könnte. Wäre die Vermutung falsch, gäbe es mindestens einen Graphen mit der kleinstmöglichen Anzahl an Punkten, der fünf Farben erfordert. Die Idee bestand darin zu zeigen, dass ein solches minimales Gegenbeispiel nicht existieren kann. Heesch führte dazu eine riesige Liste von Teilgraphen vor, die in den planaren Netzwerken vorkommen könnten, die man untersuchen müsste. Allerdings reichte die damalige Rechenleistung nicht aus, um den Beweis tatsächlich zu führen.

Erst 1976 konnten die Mathematiker Kenneth Appel und Wolfgang Haken von der University of Illinois den Ansatz von Heesch vereinfachen. Zudem hatte sich die Leistung von Computern inzwischen weiterentwickelt, so dass sie einen Rechner 1482 Konfigurationen von Graphen prüfen ließen. Nach mehreren tausend Stunden Rechenzeit erhielten sie das gewünschte Ergebnis: Die Vier-Farben-Vermutung ist korrekt.

Anfangs waren nicht alle Fachleute von diesem Ergebnis überzeugt. Schließlich ließ sich das Resultat nicht direkt von einem Menschen verifizieren: Selbst wenn Appel und Haken den Quellcode ihres Computerprogramms veröffentlichten, müsste man dem Compiler sowie der Hardware vertrauen, dass sie richtig arbeiten.

Inzwischen wurde der Beweis vielfach überarbeitet, die Anzahl der zu prüfenden Fälle verringert (auf etwa 600) und das Ergebnis sogar mit einem Beweisassistenten verifiziert. Solche Computerprogramme gehen die logischen Schlussfolgerungen durch und decken Fehler in geführten Beweisen auf. Auch wenn an der Richtigkeit des Ergebnisses von Haken und Appel also kaum noch Zweifel herrschen, fehlt es dem Beweis an Eleganz: Viele Mathematikerinnen und Mathematiker wünschen sich eine Argumentation, die sich nicht bloß auf das Abarbeiten von Fallunterscheidungen stützt. Doch eine solche steht noch aus.

Der Vier-Farben-Satz ist schon lange kein Außenseiter mehr: In den letzten Jahrzehnten wurden weitere bedeutende Beweise mit Hilfe eines Computers geführt, etwa die Keplersche Vermutung oder die Kellersche Vermutung. Heute sind rechnergestützte Beweise in der Wissenschaft weithin akzeptiert. Aber wahrscheinlich werden wir uns in Zukunft mit neuen Fragen auseinandersetzen müssen: Werden wir einem mathematischen Beweis trauen, den eine KI geführt hat?