Der Vierfarbensatz: Ein neuer Beweis

Indem Mathematiker das berühmte Problem wieder betrachteten – das in den 1970er Jahren umstritten mit Computern gelöst wurde –, haben sie wichtige neue Erkenntnisse über die Natur von Graphen gewonnen.

Der Vierfarbensatz ist einfach zu formulieren: Gegeben ist eine zusammenhängende Karte. Ist es möglich, jede Region mit einer von vier Farben so einzufärben, dass benachbarte Regionen keine gleiche Farbe haben?

Einige mathematische Probleme verfolgen Forscher auch noch lange, nachdem sie gelöst wurden. Ein Beweis entsteht, wird sogar gefeiert, aber Unzufriedenheit bleibt. Vielleicht ist das Argument zu kompliziert – man sucht immer noch nach dem ersehnten Einseiten-Papier – oder es gibt keinen tieferen theoretischen Einblick, warum etwas wahr ist. Aus welchem Grund auch immer, Mathematiker kehren immer wieder zu einem Fall zurück, der sonst als abgeschlossen gilt.

Einer der berühmtesten solchen Fälle ist der Vierfarbensatz. Das Problem hat verändert, wie Mathematiker über ihr Fach denken.

Das Problem ist einfach zu formulieren und noch einfacher zu sehen: Gegeben ist eine zusammenhängende Karte. Ist es möglich, jede Region mit einer von vier Farben so einzufärben, dass benachbarte Regionen keine gleiche Farbe haben? Im Mittelinteresse war die Frage für Kartografen im 19. Jahrhundert unbedeutend, die mehr als vier Farben zur Verfügung hatten und keinen Grund sahen, ihre Palette einzuschränken. Aber für Mathematiker, amateurhaft und professionell, wurde das Kopfknistern schnell zur Besessenheit.

Der erste angebliche Beweis, angekündigt 1879, hielt 11 Jahre lang, bevor er als falsch bewiesen wurde. Mehr falsche Antworten folgten, von Anwälten, Ärzten und berühmten Graphentheoretikern auch. „Hier haben wir ein Problem, das sogar ein Kind verstehen kann“, sagte Carsten Thomassen, ein Graphentheoretiker an der Technischen Universität Dänemark. „Ich glaube, das ist der Grund, warum es eine so große Herausforderung war.“

Der Satz wurde fast ein Jahrhundert später bewiesen – aber mit Computermethoden, die damals als skandalös galten. Das ließ Mathematiker hinterfragen, was sie überhaupt als Beweis betrachteten. Der Status des Problems blieb bis 1997 eine Quelle der Debatte, als Computergebrauch üblicher wurde und ein einfacherer computerunterstützter Beweis gefunden wurde.

Auch heute noch zirkuliert die „Vierfarbenkrankheit“, wie Mikkel Thorup, ein Informatiker an der Universität Kopenhagen, es nennt. Er und Thomassen zählen sich zu den Betroffenen. Für eine solch einfache Aussage muss es einen einfacheren Grund geben, warum sie wahr ist. Oder zumindest einen effizienteren Weg, sie zu zeigen.

Nach fast einem Jahrzehnt Arbeit haben Thorup, Thomassen und vier Kollegen in Dänemark, Kanada und Japan einen weiteren Computerbeweis für den Satz vorgelegt.

Der Beweis – online gestellt im März 2026 und vorgestellt im November auf der jährlichen Konferenz Foundations of Computer Science – ist in mancher Weise sogar komplizierter als seine Vorgänger. „Es sieht so aus, als hätten sie Strom großzügig für den eigentlichen Beweis benutzt“, sagte Georges Gonthier, ein Informatiker am Inria in Paris. Aber bei der Erstellung ihres Arguments lieferten die Forscher einen viel effizienteren Weg, Karten und Graphen einzufärben. Und dabei entdeckten sie neue Einblicke in strukturelle Eigenschaften wichtiger mathematischer Objekte, genannt planare Graphen – das eröffnet die Möglichkeit für Fortschritte bei vielen anderen hartnäckigen Problemen in der Graphentheorie.

Angesichts der Geschichte falscher Anfänge und zerschlagener Hoffnungen sagte Gonthier: „Es ist wirklich cool, endlich ein echtes Ergebnis zu sehen.“

Computerisierte Kontroverse

1852 färbte der Mathematiker Francis Guthrie eine Karte englischer Grafschaften ein und bemerkte, dass er nur vier Farben brauchte. War das immer wahr, fragte er sich. Er fragte seinen Bruder Frederick, ebenfalls Mathematiker, dessen Berater Augustus De Morgan sich für die Frage interessierte und sie einem breiteren Publikum anbieten wollte. 1879, als ein Mathematiker namens Alfred Bray Kempe behauptete, eine Lösung zu haben, verkündete eine Pressemitteilung die Errungenschaft in Nature.

Kempe begann damit, das Gegenteil von dem anzunehmen, was er beweisen wollte: Es gibt eine Karte, die nicht mit nur vier Farben eingefärbt werden kann. Dann versuchte er zu zeigen, dass diese Annahme letztlich zu einem Widerspruch führen würde – das bedeutet, dass keine solche Karte existieren könnte. In diesem Fall müssten alle Karten vierfärbig sein.

Erst, sagte er, stell dir vor, dass die nicht vierfärmbare Karte aus deiner Annahme so „minimal“ wie möglich ist: Wenn du ein Land daraus entfernen würdest, wäre die verbleibende Karte vierfärbig. Dann eliminierst du Geographie und andere überflüssige Details, indem du deine Karte als das zeichnest, was als planarer Graph bekannt ist. Stelle jedes Land als Punkt (oder Eckpunkt) dar und zeichne eine Linie (oder Kante) zwischen zwei Punkten, wenn diese Länder eine Grenze teilen. Dein Karteneinfärbungsproblem ist jetzt ein Grapheneinfärbungsproblem, das für die Werkzeuge der Graphentheorie zugänglich ist.

Mark Belan/ Quanta Magazine

Insbesondere im 18. Jahrhundert, der Schweizer Mathe...