Mathematik verständlich erklärt

Der Vier-Farben-Satz einfach erklärt

Vier Farben genügen für jede Landkarte der Welt - das ist der Vier-Farben-Satz. Ein Satz, der sich in einer Zeile sagen lässt, aber 124 Jahre und schließlich einen Computer brauchte, um bewiesen zu werden. Hier ist die ganze Geschichte: was der Vier-Farben-Satz besagt, warum er so schwer zu beweisen war, wie der Beweis am Ende doch gelang - und wo er an seine Grenzen stößt.

Cartographer macht genau diesen Satz zum Spiel - 120 handgezeichnete Karten, die ersten 10 kostenlos.

Was besagt der Vier-Farben-Satz?

Der Vier-Farben-Satz ist eine der knappsten Aussagen der Mathematik: Jede Landkarte lässt sich mit höchstens vier Farben so einfärben, dass keine zwei benachbarten Gebiete dieselbe Farbe tragen. Egal wie viele Länder die Karte hat und wie verschlungen ihre Grenzen verlaufen - vier Farben reichen immer.

Zwei Begriffe darin sind genauer gefasst, als es beim ersten Lesen wirkt. Benachbart sind zwei Gebiete nur, wenn sie eine echte Grenzlinie teilen - ein einzelner Berührungspunkt zählt nicht. Und jedes Gebiet muss zusammenhängend sein, ein Land aus zwei getrennten Teilen zählt nicht als eines. Beide Einschränkungen wirken wie Kleingedrucktes, sind aber der Grund, warum der Vier-Farben-Satz überhaupt beweisbar ist - und warum er, wie weiter unten beschrieben, auf manche echten Landkarten nicht sauber passt.

Mathematisch ist der Vier-Farben-Satz eigentlich eine Aussage über Graphen, nicht über Landkarten: Jede Karte lässt sich in einen sogenannten planaren Graphen übersetzen, indem jedes Gebiet zu einem Punkt und jede gemeinsame Grenze zu einer Verbindungslinie wird. Der Vier-Farben-Satz sagt dann: Jeder planare Graph lässt sich mit höchstens vier Farben so färben, dass zwei durch eine Linie verbundene Punkte nie dieselbe Farbe tragen. Landkarten sind nur die anschaulichste Version dieser abstrakteren, allgemeineren Aussage.

Warum ist der Vier-Farben-Satz nicht offensichtlich?

Dass drei Farben manchmal nicht reichen, lässt sich in Sekunden zeigen: Drei Gebiete, die sich alle gegenseitig berühren, brauchen drei verschiedene Farben. Naheliegend wäre die Vermutung, dass sich dieser Trick beliebig weitertreiben lässt - fünf gegenseitig angrenzende Gebiete für fünf Farben, sechs für sechs, und so weiter, ohne Obergrenze. Genau das passiert aber nicht. Ab einer bestimmten Grenze verhindert die reine Geometrie der Ebene, dass sich beliebig viele Gebiete gegenseitig berühren können - und diese Grenze liegt bei vier. Der Vier-Farben-Satz ist die Aussage, dass diese Grenze nicht nur für kleine, sondern für jede noch so komplizierte Landkarte gilt. Genau dieser Sprung von "in jedem bisher betrachteten Fall" zu "in jedem denkbaren Fall, für immer" macht aus einer Beobachtung einen Satz - und aus einem Satz ein 124 Jahre altes offenes Problem.

Die Geschichte des Vier-Farben-Satzes

Die Vermutung stammt von einem Studenten: 1852 färbte der Londoner Francis Guthrie eine Karte der englischen Grafschaften und bemerkte, dass er nie mehr als vier Farben brauchte, wie er die Grenzen auch zog. Sein Bruder Frederick trug die Frage an den Mathematiker Augustus De Morgan heran, der sie noch am selben Tag - dem 23. Oktober 1852 - in einem Brief an William Rowan Hamilton weitergab. Hamilton zeigte sich uninteressiert, doch De Morgan ließ die Frage nicht los und trug sie in der mathematischen Gemeinschaft Londons weiter.

1878 trug Arthur Cayley die weiterhin ungelöste Frage vor die London Mathematical Society. Ein Jahr später veröffentlichte der Anwalt und Hobbymathematiker Alfred Kempe einen Beweis, der elf Jahre lang als gültig galt. Kempes Methode - heute als Kempe-Ketten bekannt - ist selbst hübsche Mathematik: Man betrachtet zwei der vier Farben und verfolgt die zusammenhängende Kette von Gebieten, die abwechselnd nur diese beiden Farben tragen. Lässt sich diese Kette an einer Stelle durchtrennen, kann man die beiden Farben auf einem Teil der Kette einfach vertauschen, ohne irgendwo einen Konflikt zu erzeugen - und schafft sich so Platz für die vierte Farbe an der Stelle, die vorher Schwierigkeiten machte. Parallel dazu versuchte sich 1880 auch Peter Guthrie Tait an einem eigenen Beweis.

1890 fand Percy Heawood die Lücke in Kempes Argument: Für bestimmte Konstellationen lassen sich zwei Ketten nicht unabhängig voneinander vertauschen, ohne dass sich an anderer Stelle ein neuer Konflikt öffnet. Kempes Beweis war widerlegt - der Vier-Farben-Satz wieder offen. Heawood rettete aus den Trümmern immerhin den Fünf-Farben-Satz: Mit Kempes Kettentechnik lässt sich vollständig von Hand beweisen, dass fünf Farben für jede Landkarte immer reichen. Nur der letzte, entscheidende Schritt von fünf auf vier blieb unbewiesen. 1891 widerlegte zudem Julius Petersen auch Taits Beweisversuch von 1880. Für fast ein weiteres Jahrhundert blieb der Vier-Farben-Satz eine offene Vermutung.

Der Beweis von 1976: Computer gegen Handrechnung

Erst 1976 gelang Kenneth Appel und Wolfgang Haken an der University of Illinois der Durchbruch - aber nicht auf dem Papier. Ihre Beweisstrategie folgt einem Muster, das schon Kempe vorschwebte: Man nimmt an, es gäbe eine Landkarte, die den Vier-Farben-Satz verletzt, und wählt unter allen solchen Gegenbeispielen das kleinstmögliche. Dann zeigt man, dass dieses minimale Gegenbeispiel unmöglich ist - und damit auch jedes größere, denn ein größeres ließe sich immer auf ein kleineres zurückführen.

Der Trick liegt darin, eine unvermeidbare Menge reduzierbarer Konfigurationen zu finden: eine Liste von Kartenmustern, von denen mindestens eines in jedem minimalen Gegenbeispiel vorkommen muss (unvermeidbar), und von denen sich jedes einzelne als unmöglich erweisen lässt (reduzierbar). Um diese Liste überhaupt zu finden, nutzten Appel und Haken die sogenannte Entladungsmethode: Jedem Gebiet wird eine Startladung zugewiesen, die von der Zahl seiner Nachbarn abhängt, und diese Ladung wird nach festen Regeln zwischen benachbarten Gebieten umverteilt - ähnlich wie in einem elektrischen Netzwerk. Am Ende zeigt sich, welche Gebiete zwangsläufig zu einer der reduzierbaren Konfigurationen gehören müssen.

Am Ende blieben 1.936 Konfigurationen übrig, später auf 1.476 verkleinert - viel zu viele, um sie von Hand zu prüfen. Appel und Haken ließen einen Computer rund 1.200 Stunden lang rechnen. Das Ergebnis: Der Vier-Farben-Satz stimmt. Aber kein Mathematiker konnte den Beweis mehr von Anfang bis Ende von Hand nachvollziehen - er war schlicht zu lang für einen Menschen, nicht zu schwer.

„Four colors suffice.“Poststempel der University of Illinois, nach 1976 jahrelang im Umlauf

Das sorgte für echten Streit in der mathematischen Gemeinschaft. War ein Beweis, den man nicht mehr lesen, sondern nur noch laufen lassen konnte, überhaupt ein Beweis? 1989 veröffentlichten Appel und Haken eine rund 400 Seiten lange, vollständige Beweisführung. 1997 verkleinerten Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas die nötige Fallzahl auf 633 - der Beweis wurde einfacher, blieb aber computergestützt. Die endgültige Beruhigung kam erst 2005: Georges Gonthier und Benjamin Werner ließen den kompletten Beweis noch einmal von einem sogenannten Beweisassistenten namens Coq überprüfen - einer Software, die jeden einzelnen logischen Schritt formal nachrechnet, ohne die kleinste Lücke für Zweifel zu lassen.

1.476 Kartenmuster sind eher etwas für Computer. Eine einzelne Insel dagegen lässt sich gut von Hand lösen - in Cartographer warten 120 davon.

Kostenlos ausprobieren

Warum keiner den Beweis komplett von Hand nachrechnen kann

Der Unterschied zwischen dem Vier-Farben-Satz und dem Fünf-Farben-Satz zeigt gut, worum es hier eigentlich geht. Der Fünf-Farben-Satz - die schwächere Aussage, dass fünf Farben immer reichen - lässt sich mit Kempes Kettentechnik vollständig von Hand beweisen, auf wenigen Seiten, von jedem Mathematikstudierenden nachvollziehbar. Beim Vier-Farben-Satz dagegen ist die Zahl der Fälle, die die Entladungsmethode am Ende offen lässt, schlicht zu groß für ein menschliches Gehirn - nicht zu kompliziert, sondern zu viel. Das war 1976 etwas komplett Neues: der erste bedeutende mathematische Beweis, der wesentlich auf einen Computer angewiesen war. Heute ist das in vielen Teilgebieten der Mathematik normal, aber der Vier-Farben-Satz war der Fall, an dem die Fachwelt zum ersten Mal ernsthaft fragen musste, was ein Beweis eigentlich ist, wenn ihn kein Mensch mehr vollständig prüfen kann.

Wo der Vier-Farben-Satz an seine Grenzen stößt

Der Vier-Farben-Satz beschreibt reine Geometrie - sobald echte Länder und echte Grenzen ins Spiel kommen, zeigt er auch seine Grenzen.

Der Vier-Farben-Satz in der Praxis: Graphfärbung

Der Vier-Farben-Satz selbst ist eine Aussage über Landkarten und planare Graphen - aber die dahinterliegende Idee, das Einfärben von Graphen so, dass verbundene Punkte nie dieselbe Farbe teilen, ist als Graphfärbung ein eigenes, viel allgemeineres Werkzeug der Informatik. Bei der Stundenplanung etwa werden Veranstaltungen zu Punkten, und zwei Veranstaltungen werden verbunden, wenn sie sich nicht überschneiden dürfen - zum Beispiel, weil dieselbe Lehrkraft beide hält. Eine gültige Färbung entspricht dann einem Stundenplan ohne Kollisionen, wobei jede Farbe ein Zeitfenster ist. Auch bei der Registerzuweisung in Compilern, wenn Programmvariablen auf eine begrenzte Zahl von Prozessorregistern verteilt werden müssen, ist das Grundproblem dasselbe. Anders als bei Landkarten sind diese Graphen aber meist nicht planar - die Vier-Farben-Grenze gilt dort also nicht, oft werden deutlich mehr Farben gebraucht. Was bleibt, ist die Idee, die der Vier-Farben-Satz berühmt gemacht hat.

Den Vier-Farben-Satz selbst ausprobieren

Cartographer übersetzt den Vier-Farben-Satz in ein Spiel: 120 handgezeichnete Inselkarten, bei denen genau diese Regel gilt - Nachbarn dürfen nie dieselbe Farbe tragen. Die ersten 10 Karten sind kostenlos, direkt im Browser gibt es eine spielbare Demo.

Demo spielen

Häufige Fragen zum Vier-Farben-Satz