Vierfarbensatz

In der Mathematik besagt der Vierfarbensatz , auch Vierfarbensatz genannt , dass man höchstens vier Farben benötigt, um die Bereiche einer beliebigen Karte so einzufärben, dass keine zwei benachbarten Bereiche die gleiche Farbe haben. Benachbart bedeutet, dass zwei Bereiche eine gemeinsame Grenze ungleich null Länge besitzen (d. h. nicht nur eine Ecke, an der drei oder mehr Bereiche zusammentreffen). ^{[ 1 ]} Es war der erste bedeutende Satz, der mithilfe eines Computers bewiesen wurde . Anfänglich wurde dieser Beweis nicht von allen Mathematikern akzeptiert, da die computergestützte Beweisführung für einen Menschen nicht manuell überprüfbar war . ^{[ 2 ]} Inzwischen hat der Beweis weite Verbreitung gefunden, obwohl einige Vorbehalte bestehen bleiben. ^{[ 3 ]}

Der Satz ist eine stärkere Version des Fünffarbensatzes und lässt sich mit einem deutlich einfacheren Argument beweisen. Obwohl der schwächere Fünffarbensatz bereits im 19. Jahrhundert bewiesen wurde, blieb der Vierfarbensatz bis 1976 unbewiesen, als Kenneth Appel und Wolfgang Haken ihn mithilfe eines Computerbeweises bewiesen . Dies geschah nach zahlreichen Fehlbeweisen und irrtümlichen Gegenbeispielen in den Jahrzehnten zuvor.

Der Appel-Haken-Beweis basiert auf der Analyse einer sehr großen Anzahl von „reduzierbaren Konfigurationen“, also Abbildungen mit einer bestimmten Eigenschaft. Robertson, Sanders, Seymour und Thomas verbesserten diesen Beweis 1997 und reduzierten die Anzahl solcher Konfigurationen auf 633 – was immer noch eine extrem umfangreiche Fallanalyse darstellt. Im Jahr 2005 wurde der Satz von Georges Gonthier mithilfe einer universellen Beweissoftware verifiziert .

Die Färbung von Karten lässt sich auch graphentheoretisch ausdrücken , indem man sie als Konstruktion einer Graphfärbung des planaren Adjazenzgraphen zwischen Regionen betrachtet. Graphentheoretisch besagt der Satz, dass für einen schleifenlosen planaren Graphen , dessen chromatische Zahl mit bezeichnet wird , gilt : . ${\displaystyle G}$${\displaystyle \chi (G)}$${\displaystyle \chi (G)\leq 4}$

Damit dies sinnvoll ist, muss die intuitive Aussage des Vierfarbensatzes – „bei jeder Unterteilung einer Ebene in zusammenhängende Bereiche können die Bereiche mit höchstens vier Farben so eingefärbt werden, dass keine zwei benachbarten Bereiche die gleiche Farbe haben“ – entsprechend interpretiert werden.

Erstens gelten Regionen als benachbart, wenn sie ein gemeinsames Grenzsegment aufweisen; zwei Regionen, die nur einzelne Grenzpunkte gemeinsam haben, gelten nicht als benachbart. (Andernfalls würde eine Karte in Form eines Tortendiagramms beliebig viele Regionen an einer gemeinsamen Ecke „benachbart“ darstellen und folglich beliebig viele Farben erfordern.) Zweitens sind ungewöhnliche Regionen, wie solche mit endlicher Fläche, aber unendlich langem Umfang, nicht zulässig; Karten mit solchen Regionen können mehr als vier Farben benötigen. ^{[ 4 ]} (Sicherheitshalber beschränken wir uns auf Regionen, deren Grenzen aus endlich vielen geraden Liniensegmenten bestehen. Es ist zulässig, dass eine Region Exklaven enthält , d. h. sie umschließt eine oder mehrere andere Regionen vollständig.) Der Begriff „zusammenhängende Region“ (technisch: zusammenhängende offene Teilmenge der Ebene) ist nicht identisch mit dem Begriff „Land“ auf herkömmlichen Karten, da ein Land nicht zusammenhängend sein muss: Es kann Exklaven enthalten , wie Angola mit seiner Provinz Cabinda , Aserbaidschan mit seiner Autonomen Republik Nachitschewan , Russland mit seinem Gebiet Kaliningrad , Frankreich mit seinen Überseegebieten und die Vereinigten Staaten mit dem Bundesstaat Alaska . Wenn wir fordern, dass das gesamte Staatsgebiet eines Landes dieselbe Farbe erhält, reichen vier Farben nicht immer aus. Betrachten wir beispielsweise die vereinfachte Karte:

Auf dieser Karte gehören die beiden mit A gekennzeichneten Regionen zum selben Land. Sollen diese Regionen dieselbe Farbe erhalten, sind fünf Farben erforderlich, da die beiden Regionen A zusammen an vier weitere Regionen angrenzen, von denen jede wiederum an jede andere angrenzt.

Eine einfachere Formulierung des Satzes verwendet die Graphentheorie . Die Menge der Regionen einer Karte lässt sich abstrakter als ungerichteter Graph darstellen, der für jede Region einen Knoten und für jedes Paar von Regionen mit gemeinsamer Grenze eine Kante besitzt. Dieser Graph ist planar : Er kann in der Ebene kreuzungsfrei gezeichnet werden, indem man jeden Knoten an einer beliebigen Stelle innerhalb der zugehörigen Region platziert und die Kanten als kreuzungsfreie Kurven zeichnet, die von einem Knoten einer Region über eine gemeinsame Grenze zu einem Knoten einer benachbarten Region führen. Umgekehrt lässt sich jeder planare Graph auf diese Weise aus einer Karte erzeugen. In der graphentheoretischen Terminologie besagt der Vierfarbensatz, dass die Knoten jedes planaren Graphen mit höchstens vier Farben so gefärbt werden können, dass keine zwei benachbarten Knoten die gleiche Farbe erhalten; kurz: Jeder planare Graph ist vierfärbbar . ^{[ 5 ]}

Soweit bekannt, ^{[ 6 ]} wurde die Vermutung erstmals am 23. Oktober 1852 ^{[ 7 ]} aufgestellt, als Francis Guthrie beim Versuch, die Karte der Grafschaften Englands einzufärben, feststellte, dass nur vier verschiedene Farben nötig waren. Guthries Bruder Frederick war zu dieser Zeit Student von Augustus De Morgan (dem ehemaligen Doktorvater von Francis) am University College London . Francis fragte Frederick danach, der die Vermutung dann an De Morgan weiterleitete. (Francis Guthrie schloss sein Studium später im Jahr 1852 ab und wurde später Mathematikprofessor in Südafrika.) Laut De Morgan:

Ein Student von mir [Guthrie] bat mich heute um eine Begründung für eine Tatsache, deren Existenz mir nicht bekannt war – und auch heute noch nicht bekannt ist. Er meint, wenn eine Figur beliebig unterteilt und die einzelnen Bereiche unterschiedlich eingefärbt würden, sodass Figuren mit einer gemeinsamen Grenzlinie unterschiedlich gefärbt wären – vier Farben wären wünschenswert, aber nicht mehr –, schildert er im Folgenden seinen Fall, in dem vier Farben benötigt würden . Die Frage ist, ob sich nicht eine Notwendigkeit für fünf oder mehr Farben erfinden ließe… ^{[ 8 ]}

„FG“, möglicherweise einer der beiden Guthries, veröffentlichte die Frage 1854 im The Athenaeum ^{[ 9 ]} , und De Morgan stellte die Frage 1860 in derselben Zeitschrift erneut. ^{[ 10 ]} Ein weiterer früher veröffentlichter Hinweis von Arthur Cayley  ( 1879 ) schreibt die Vermutung wiederum De Morgan zu.

Es gab mehrere frühe, erfolglose Versuche, den Satz zu beweisen. De Morgan glaubte, dass er aus einer einfachen Tatsache über vier Regionen folge, obwohl er nicht glaubte, dass diese Tatsache aus elementareren Tatsachen abgeleitet werden könne.

Dies ergibt sich folgendermaßen: Wir benötigen niemals vier Farben in einer Nachbarschaft, es sei denn, es gäbe vier Landkreise, von denen jeder mit jedem der anderen drei gemeinsame Grenzen hat. So etwas ist bei vier Gebieten nur möglich, wenn mindestens eines von ihnen von den übrigen umschlossen wird; und die für den umschlossenen Landkreis verwendete Farbe kann somit weiterverwendet werden. Nun ist dieses Prinzip, dass vier Gebiete nicht jeweils ohne Umschließung mit allen anderen drei eine gemeinsame Grenze haben können, unserer festen Überzeugung nach nicht durch etwas Offensichtlicheres und Elementareres bewiesen werden kann; es muss als Postulat gelten. ^{[ 10 ]}

Ein erster Beweis wurde 1879 von Alfred Kempe vorgelegt und fand breite Anerkennung. ^{[ 11 ]} Ein weiterer Beweis wurde 1880 von Peter Guthrie Tait erbracht . Erst 1890 wurde Kempes Beweis von Percy Heawood widerlegt, und 1891 wurde Taits Beweis von Julius Petersen widerlegt – jeder dieser falschen Beweise blieb elf Jahre lang unwidersprochen. ^{[ 12 ]}

Im Jahr 1890 deckte Heawood nicht nur den Fehler in Kempes Beweis auf, sondern bewies auch den Fünffarbensatz und verallgemeinerte die Vierfarbenvermutung auf Flächen beliebigen Geschlechts . ^{[ 13 ]}

Tait zeigte 1880, dass der Vierfarbensatz äquivalent zu der Aussage ist, dass ein bestimmter Graphentyp ( in der modernen Terminologie als Snark bezeichnet ) nicht planar sein muss . ^{[ 14 ]}

Im Jahr 1943 formulierte Hugo Hadwiger die Hadwiger-Vermutung ^{[ 15 ]} , eine weitreichende Verallgemeinerung des Vierfarbenproblems, die bis heute ungelöst ist.

In den 1960er und 1970er Jahren entwickelte der deutsche Mathematiker Heinrich Heesch Methoden zur computergestützten Beweissuche. Er war der Erste, der das Entladungsprinzip zum Beweis des Theorems einsetzte, welches sich im späteren Appel-Haken-Beweis als wichtig für die Unvermeidbarkeit erwies. Zudem erweiterte er das Konzept der Reduzierbarkeit und entwickelte zusammen mit Ken Durré einen Computertest dafür. Leider gelang es ihm zu diesem entscheidenden Zeitpunkt nicht, die notwendige Rechenzeit eines Supercomputers zu erhalten, um seine Arbeit fortzusetzen. ^{[ 16 ]}

Andere griffen seine Methoden auf, darunter auch seinen computergestützten Ansatz. Während andere Mathematikerteams um die Wette Beweise erbrachten, verkündeten Kenneth Appel und Wolfgang Haken von der Universität Illinois am 21. Juni 1976 ^{[ 17 ]} , dass sie den Satz bewiesen hätten. Bei einigen algorithmischen Arbeiten wurden sie von John A. Koch unterstützt . ^{[ 18 ]}

Wäre die Vierfarbenvermutung falsch, gäbe es mindestens eine Karte mit der kleinstmöglichen Anzahl an Regionen, die fünf Farben benötigt. Der Beweis zeigte, dass ein solches minimales Gegenbeispiel nicht existieren kann, und zwar mithilfe zweier technischer Konzepte: ^{[ 19 ]}

1. Eine unvermeidbare Menge ist eine Menge von Konfigurationen, sodass jede Abbildung, die bestimmte notwendige Bedingungen für eine minimale nicht-4-färbbare Triangulierung erfüllt (z. B. einen minimalen Grad von 5 hat), mindestens eine Konfiguration aus dieser Menge haben muss.
2. Eine reduzierbare Konfiguration ist eine Anordnung von Ländern, die in einem minimalen Gegenbeispiel nicht vorkommen kann. Enthält eine Karte eine reduzierbare Konfiguration, so lässt sie sich auf eine kleinere Karte reduzieren. Diese kleinere Karte erfüllt die Bedingung, dass, falls sie mit vier Farben eingefärbt werden kann, dies auch für die ursprüngliche Karte gilt. Daraus folgt: Kann die ursprüngliche Karte nicht mit vier Farben eingefärbt werden, so kann auch die kleinere Karte dies nicht, und somit ist die ursprüngliche Karte nicht minimal.

Appel und Haken fanden mithilfe mathematischer Regeln und Verfahren, die auf den Eigenschaften reduzierbarer Konfigurationen basieren, eine unvermeidliche Menge reduzierbarer Konfigurationen und bewiesen damit, dass es kein minimales Gegenbeispiel zur Vierfarbenvermutung geben kann. Ihr Beweis reduzierte die unendliche Anzahl möglicher Abbildungen auf 1834 reduzierbare Konfigurationen (später auf 1482), die einzeln per Computer überprüft werden mussten und über tausend Stunden in Anspruch nahmen. Dieser Teil der Arbeit, der die Reduzierbarkeit bewies, wurde unabhängig voneinander mit verschiedenen Programmen und Computern gegengeprüft. Der Beweis der Unvermeidbarkeit hingegen basierte auf über 400 Seiten Mikrofiche , die manuell mit Unterstützung von Hakens Tochter Dorothea Blostein überprüft werden mussten . ^{[ 20 ]}

Die Ankündigung von Appel und Haken fand weltweit breite Beachtung in den Medien ^{[ 21 ]} , und die Mathematikfakultät der Universität von Illinois versah sie mit einem Poststempel, der die Aufschrift „Vier Farben genügen“ trug. ^{[ 22 ]} Gleichzeitig sorgten die ungewöhnliche Natur des Beweises – es war der erste bedeutende Satz, der mit umfassender Computerunterstützung bewiesen wurde – und die Komplexität des vom Menschen überprüfbaren Teils für erhebliche Kontroversen. ^{[ 23 ]} Nicht alle Mathematiker akzeptierten, dass ein computergestützter Beweis als echter Beweis gelten konnte. Selbst einige Befürworter, wie Ian Stewart , empfanden den Beweis als unbefriedigend, da er sich als vollendete Tatsache erwies und jegliche Struktur vermissen ließ. „Die Antwort erscheint wie ein ungeheurer Zufall“, schrieb Stewart. HSM Coxeter hielt es für „sehr unwahrscheinlich, dass irgendjemand diesen Beweis in etwas zerlegen kann, das man als gewöhnlichen Beweis ansehen würde“. ^{[ 24 ]}

Anfang der 1980er Jahre kursierten Gerüchte über einen Fehler im Beweis von Appel und Haken. Ulrich Schmidt von der RWTH Aachen hatte den Beweis von Appel und Haken für seine 1981 veröffentlichte Masterarbeit untersucht. ^{[ 25 ]} Er hatte etwa 40 % des Unvermeidbarkeitsteils überprüft und einen signifikanten Fehler im Entladungsverfahren gefunden ( Appel & Haken 1989 ). 1986 wurden Appel und Haken vom Herausgeber des Mathematical Intelligencer gebeten , einen Artikel zu den Gerüchten über Fehler in ihrem Beweis zu verfassen. Sie antworteten, die Gerüchte beruhten auf einer „Fehlinterpretation von Schmidts Ergebnissen“ und kamen dieser Bitte mit einem ausführlichen Artikel nach. ^{[ 25 ]} Ihr Hauptwerk , Every Planar Map is Four-Colorable , ein Buch, das einen vollständigen und detaillierten Beweis (mit einem über 400 Seiten umfassenden Mikrofiche-Anhang) enthielt, erschien 1989. Es erklärte und korrigierte den von Schmidt entdeckten Fehler sowie mehrere weitere, von anderen gefundene Fehler. ^{[ 20 ]}

Seit dem Beweis des Theorems hat ein neuer Ansatz sowohl zu einem kürzeren Beweis als auch zu einem effizienteren Algorithmus für 4-Färbungskarten geführt. 1996 entwickelten Neil Robertson , Daniel P. Sanders , Paul Seymour und Robin Thomas einen Algorithmus mit quadratischer Laufzeit ( O ( n² ⁾ , wobei n die Anzahl der Knoten ist), der einen Algorithmus mit quartischer Laufzeit basierend auf dem Beweis von Appel und Haken verbesserte. ^{[ 26 ]} Der neue Beweis, der auf denselben Ideen beruht, ähnelt dem von Appel und Haken, ist aber effizienter, da er die Komplexität des Problems reduziert und nur die Überprüfung von 633 reduzierbaren Konfigurationen erfordert. Sowohl die Unvermeidbarkeits- als auch die Reduzierbarkeitsteile dieses neuen Beweises müssen von einem Computer ausgeführt werden und sind von Hand praktisch nicht überprüfbar. ^{[ 27 ]} Im Jahr 2001 kündigten dieselben Autoren einen alternativen Beweis an, indem sie die Snark-Vermutung bewiesen . ^{[ 28 ]} Dieser Beweis ist jedoch weiterhin unveröffentlicht.

Im Jahr 2005 formalisierten Benjamin Werner und Georges Gonthier einen Beweis des Theorems innerhalb des Beweisassistenten Coq . Dadurch entfiel die Notwendigkeit, den verschiedenen Computerprogrammen zu vertrauen, die zur Überprüfung bestimmter Fälle verwendet wurden; es genügte, dem Coq-Kernel zu vertrauen. ^{[ 29 ]}

Die folgende Erläuterung ist eine Zusammenfassung der Einleitung zu „ Every Planar Map is Four Colorable“ ( Appel & Haken 1989 ). Kempes ursprünglicher, vermeintlicher Beweis des Vierfarbensatzes war zwar fehlerhaft, lieferte aber einige der grundlegenden Werkzeuge, die später für dessen Beweis verwendet wurden. Die Erklärung hier ist in der obenstehenden modernen graphentheoretischen Formulierung neu formuliert.

Kempes Argumentation lautet wie folgt: Erstens, wenn planare Bereiche, die durch den Graphen getrennt sind, nicht trianguliert sind (d. h. nicht genau drei Kanten an ihren Rändern besitzen), können wir Kanten hinzufügen, ohne neue Knoten einzuführen, um jeden Bereich, einschließlich des unbeschränkten äußeren Bereichs, trianguliert zu machen. Wenn dieser triangulierte Graph mit vier oder weniger Farben färbbar ist, so ist auch der ursprüngliche Graph färbbar, da dieselbe Färbung gültig ist, wenn Kanten entfernt werden. Es genügt also, den Vierfarbensatz für triangulierte Graphen zu beweisen, um ihn für alle planaren Graphen zu beweisen, und ohne Beschränkung der Allgemeinheit nehmen wir an, dass der Graph trianguliert ist.

Seien v , e und f die Anzahl der Knoten, Kanten und Flächen. Da jede Fläche dreieckig ist und jede Kante von zwei Flächen gemeinsam genutzt wird, gilt 2e = 3f . Dies lässt sich zusammen mit der Eulerschen Formel v − e + f = 2 verwenden, um zu zeigen, dass 6v − 2e = 12. Der Grad eines Knotens ist die Anzahl der an ihn angrenzenden Kanten. Wenn v _{_n} die Anzahl der Knoten vom Grad n und D der maximale Grad eines beliebigen Knotens ist,

${\displaystyle 6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.}$

Da aber 12 > 0 und 6 − i ≤ 0 für alle i ≥ 6 gilt, beweist dies, dass es mindestens einen Knoten vom Grad 5 oder weniger gibt.

Wenn es einen Graphen gibt, der fünf Farben benötigt, dann gibt es einen minimalen solchen Graphen, der durch Entfernen eines beliebigen Knotens vierfärbbar wird. Nennen wir diesen Graphen G. Dann kann G keinen Knoten vom Grad 3 oder kleiner haben, denn wenn d ( v ) ≤ 3, können wir v aus G entfernen , den kleineren Graphen vierfärben, v wieder hinzufügen und die Vierfärbung auf ihn ausdehnen, indem wir eine Farbe wählen, die sich von seinen Nachbarn unterscheidet.

Kempe zeigte auch korrekt, dass G keinen Knoten vom Grad 4 haben kann. Wie zuvor entfernen wir den Knoten v und färben die verbleibenden Knoten viermal. Wenn alle vier Nachbarn von v unterschiedliche Farben haben, beispielsweise rot, grün, blau und gelb im Uhrzeigersinn, suchen wir nach einem alternierenden Pfad aus rot und blau gefärbten Knoten, der die roten und blauen Nachbarn verbindet. Ein solcher Pfad wird Kempe-Kette genannt . Es kann eine Kempe-Kette geben, die die roten und blauen Nachbarn verbindet, und es kann eine Kempe-Kette geben, die die grünen und gelben Nachbarn verbindet, aber nicht beide, da sich diese beiden Pfade zwangsläufig schneiden würden und der Knoten, an dem sie sich schneiden, nicht gefärbt werden kann. Angenommen, es sind die roten und blauen Nachbarn, die nicht miteinander verkettet sind. Wir untersuchen alle Knoten, die über alternierende rot-blaue Pfade mit dem roten Nachbarn verbunden sind, und kehren dann die Farben rot und blau an all diesen Knoten um. Das Ergebnis ist immer noch eine gültige Vierfärbung, und v kann nun wieder hinzugefügt und rot gefärbt werden.

Damit bleibt nur noch der Fall übrig, in dem G einen Knoten vom Grad 5 besitzt; Kempes Argumentation war jedoch für diesen Fall fehlerhaft. Heawood bemerkte Kempes Fehler und stellte außerdem fest, dass man, wenn man sich mit dem Beweis zufriedengibt, dass nur fünf Farben benötigt werden, die obige Argumentation durchgehen (und lediglich ändern könnte, dass das minimale Gegenbeispiel 6 Farben erfordert) und Kempe-Ketten im Fall von Knoten vom Grad 5 verwenden könnte, um den Fünffarbensatz zu beweisen .

Um den Fall eines Knotens vom Grad 5 zu behandeln, ist ein komplexerer Ansatz erforderlich als das bloße Entfernen eines Knotens. Die Argumentation wird verallgemeinert, indem Konfigurationen betrachtet werden . Diese sind zusammenhängende Teilgraphen von G , deren Knoten den Grad jedes Knotens (in G) angeben. Beispielsweise besteht die im Abschnitt über Knoten vom Grad 4 beschriebene Konfiguration aus einem einzigen Knoten mit dem Grad 4 in G. Wie bereits erwähnt, genügt es zu zeigen, dass die Vierfärbung des verbleibenden Graphen nach dem Entfernen der Konfiguration so modifiziert werden kann, dass sie auch auf die wieder hinzugefügte Konfiguration angewendet werden kann. Eine solche Konfiguration wird als reduzierbare Konfiguration bezeichnet. Wenn mindestens eine Konfiguration aus einer Menge von Konfigurationen in G vorkommen muss, wird diese Menge als unvermeidbar bezeichnet . Die obige Argumentation begann mit der Angabe einer unvermeidlichen Menge von fünf Konfigurationen (ein einzelner Knoten mit Grad 1, ein einzelner Knoten mit Grad 2, ..., ein einzelner Knoten mit Grad 5) und zeigte dann, dass die ersten 4 reduzierbar sind; die Angabe einer unvermeidlichen Menge von Konfigurationen, in der jede Konfiguration reduzierbar ist, würde den Satz beweisen.

Da G dreieckig ist, ist der Grad jedes Knotens in einer Konfiguration bekannt, und alle Kanten innerhalb der Konfiguration sind bekannt. Die Anzahl der Knoten in G , die zu einer gegebenen Konfiguration benachbart sind, ist festgelegt, und diese Knoten bilden einen Zyklus. Diese Knoten bilden den Ring der Konfiguration; eine Konfiguration mit k Knoten in ihrem Ring ist eine k -Ring-Konfiguration, und die Konfiguration zusammen mit ihrem Ring wird als Ringkonfiguration bezeichnet . Wie in den einfachen Fällen oben kann man alle verschiedenen Viererfärbungen des Rings aufzählen; jede Färbung, die ohne Änderung zu einer Färbung der Konfiguration erweitert werden kann, wird als anfänglich gut bezeichnet . Beispielsweise war die oben genannte Konfiguration mit einem Knoten und 3 oder weniger Nachbarn anfänglich gut. Im Allgemeinen muss der umgebende Graph systematisch umgefärbt werden, um die Ringfärbung in eine gute zu verwandeln, wie es im obigen Fall mit 4 Nachbarn geschehen ist; für eine allgemeine Konfiguration mit einem größeren Ring erfordert dies komplexere Techniken. Aufgrund der großen Anzahl verschiedener Viererfärbungen des Rings ist dies der erste Schritt, der Computerunterstützung erfordert.

Schließlich gilt es, eine unvermeidbare Menge von Konfigurationen zu identifizieren, die sich mit diesem Verfahren reduzieren lassen. Die primäre Methode zur Ermittlung einer solchen Menge ist die Entladungsmethode . Die intuitive Idee hinter der Entladung besteht darin, den planaren Graphen als elektrisches Netzwerk zu betrachten. Anfangs wird positive und negative „elektrische Ladung“ so auf die Knoten verteilt, dass die Gesamtladung positiv ist.

Erinnern Sie sich an die obige Formel:

${\displaystyle \sum _{i=1}^{D}(6-i)v_{i}=12.}$

Jedem Knoten mit Grad wird eine Anfangsladung von zugewiesen . Anschließend wird die Ladung systematisch gemäß festgelegter Regeln von einem Knoten auf seine Nachbarknoten verteilt ( Entladeprozedur) . Da die Gesamtladung anfänglich positiv war (12) und Ladung erhalten bleibt, tragen einige Knoten weiterhin positive Ladung. Die Regeln schränken die möglichen Konfigurationen positiv geladener Knoten ein, sodass die Aufzählung aller möglichen Konfigurationen eine unausweichliche Menge ergibt. ${\displaystyle i}$${\displaystyle 6-i}$

Solange ein Element der unvermeidbaren Menge nicht reduzierbar ist, wird das Entladungsverfahren so modifiziert, dass es eliminiert wird (wobei gleichzeitig andere Konfigurationen eingeführt werden). Das von Appel und Haken entwickelte endgültige Entladungsverfahren war äußerst komplex und füllte zusammen mit der Beschreibung der resultierenden unvermeidbaren Konfigurationsmenge einen 400-seitigen Band. Die generierten Konfigurationen konnten jedoch mechanisch auf ihre Reduzierbarkeit überprüft werden. Die Überprüfung des Bandes, der die unvermeidbare Konfigurationsmenge selbst beschrieb, erfolgte über mehrere Jahre durch ein Peer-Review-Verfahren.

Ein technisches Detail, das hier nicht besprochen wird, aber für den Beweis erforderlich ist, ist die Immersionsreduzierbarkeit .

Der Vierfarbensatz ist berüchtigt dafür, im Laufe seiner langen Geschichte zahlreiche falsche Beweise und Widerlegungen hervorgerufen zu haben. Die New York Times weigerte sich zunächst aus Prinzip, über den Appel-Haken-Beweis zu berichten, aus Furcht, er könnte sich wie die vorherigen als falsch erweisen. ^{[ 21 ]} Einige vermeintliche Beweise, wie die oben erwähnten von Kempe und Tait, standen über ein Jahrzehnt lang unter öffentlicher Beobachtung, bevor sie widerlegt wurden. Viele weitere, von Laien verfasste Beweise wurden jedoch nie veröffentlicht.

In der ersten Karte, die mehr als vier Farben verwendet, würde das Ersetzen der roten Bereiche durch eine der vier anderen Farben nicht funktionieren, und das Beispiel scheint zunächst gegen den Satz zu verstoßen. Die Farben können jedoch, wie in der zweiten Karte, neu angeordnet werden.

Die einfachsten, wenn auch ungültigen Gegenbeispiele versuchen in der Regel, eine Region zu schaffen, die alle anderen Regionen berührt. Dadurch müssen die verbleibenden Regionen mit nur drei Farben eingefärbt werden. Da der Vierfarbensatz gilt, ist dies immer möglich; da sich der Kartenzeichner jedoch auf die eine große Region konzentriert, bemerkt er nicht, dass die übrigen Regionen tatsächlich mit drei Farben eingefärbt werden können.

Dieser Trick lässt sich verallgemeinern: Es gibt viele Karten, bei denen, wenn die Farben einiger Bereiche im Voraus festgelegt werden, es unmöglich wird, die verbleibenden Bereiche mit mehr als vier Farben einzufärben. Ein zufälliger Betrachter des Gegenbeispiels kommt möglicherweise nicht auf die Idee, die Farben dieser Bereiche zu ändern, sodass das Gegenbeispiel als gültig erscheint.

Möglicherweise liegt diesem weit verbreiteten Missverständnis die Tatsache zugrunde, dass die Farbbeschränkung nicht transitiv ist : Ein Bereich muss nur anders eingefärbt sein als Bereiche, die er direkt berührt, nicht aber Bereiche, die Bereiche berühren, die er selbst berührt. Wäre dies die Beschränkung, bräuchten planare Graphen beliebig viele Farben.

Andere falsche Widerlegungen verletzen die Voraussetzungen des Theorems, wie etwa die Verwendung eines Gebiets, das aus mehreren unzusammenhängenden Teilen besteht, oder das Verbot, dass sich Gebiete der gleichen Farbe an einem Punkt berühren.

Während jede planare Karte mit vier Farben eingefärbt werden kann, ist die Komplexität der Entscheidung, ob eine beliebige planare Karte mit nur drei Farben eingefärbt werden kann, NP-vollständig . ^{[ 30 ]}

Eine kubische Karte kann genau dann mit nur drei Farben eingefärbt werden, wenn jede innere Region eine gerade Anzahl benachbarter Regionen hat. ^{[ 31 ]} Im Beispiel der US-Bundesstaatenkarte hat der Binnenstaat Missouri (MO) acht Nachbarn (eine gerade Zahl): Er muss sich von allen diesen unterscheiden, aber die Nachbarn können die Farben abwechselnd haben, daher benötigt dieser Teil der Karte nur drei Farben. Der Binnenstaat Nevada (NV) hingegen hat fünf Nachbarn (eine ungerade Zahl): Diese Nachbarn erfordern drei Farben, und er muss sich von ihnen unterscheiden, daher sind hier vier Farben nötig.

Der Vierfarbensatz gilt nicht nur für endliche planare Graphen, sondern auch für unendliche Graphen , die sich ohne Kreuzungen in der Ebene darstellen lassen, und sogar allgemeiner für unendliche Graphen (möglicherweise mit überabzählbarer Anzahl von Knoten), deren endliche Teilgraphen planar sind. Zum Beweis kann man den Beweis des Satzes für endliche planare Graphen mit dem Satz von De Bruijn-Erdős kombinieren, der besagt, dass ein unendlicher Graph k- färbbar ist, wenn jeder seiner endlichen Teilgraphen k -färbbar ist ( Nash-Williams 1967 ). Dies lässt sich auch als unmittelbare Folge des Kompaktheitssatzes von Kurt Gödel für die Prädikatenlogik erster Stufe auffassen , indem man die Färbbarkeit eines unendlichen Graphen durch logische Formeln ausdrückt.

Man kann das Färbungsproblem auch auf anderen Flächen als der Ebene betrachten. ^{[ 32 ]} Das Problem auf der Kugel oder dem Zylinder ist äquivalent zu dem auf der Ebene. Für geschlossene (orientierbare oder nicht-orientierbare) Flächen mit positivem Geschlecht hängt die maximale Anzahl p der benötigten Farben von der Euler-Charakteristik χ der Fläche ab. Mit Ausnahme der Kleinschen Flasche lautet die Formel wie folgt: wobei die äußeren Klammern die Abrundungsfunktion bezeichnen . $${\displaystyle p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,}$$

Für eine orientierbare Fläche bedeutet dies, dass p durch das Geschlecht g der Fläche ausgedrückt werden kann: $${\displaystyle p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor .}$$

Die wichtigste Formel, die Heawood-Vermutung , wurde 1890 von P. J. Heawood vorgeschlagen und nach Beiträgen mehrerer Personen 1968 von Gerhard Ringel und J. W. T. Youngs bewiesen. Die einzige Ausnahme von der Formel ist die Kleinsche Flasche , die die Euler-Charakteristik χ = 0 besitzt (daher ergibt die Formel p = 7 ), aber, wie Philip Franklin 1934 zeigte, nur sechs Farben benötigt .

Der Torus hat beispielsweise die Euler-Charakteristik χ = 0 (und das Geschlecht g = 1 ) und somit p = 7 , daher benötigt man höchstens sieben Farben, um eine beliebige Abbildung auf einem Torus zu färben. Diese obere Schranke von 7 ist scharf : Bestimmte toroidale Polyeder , wie etwa das Szilassi-Polyeder , benötigen sieben Farben.

Ein Möbiusband benötigt sechs Farben ( Tietze 1910 ), ebenso wie 1-planare Graphen (Graphen mit höchstens einer einfachen Kreuzung pro Kante) ( Borodin 1984 ). Werden sowohl die Knoten als auch die Flächen eines planaren Graphen so gefärbt, dass keine zwei benachbarten Knoten, Flächen oder Knoten-Flächen-Paare die gleiche Farbe haben, so sind wiederum höchstens sechs Farben erforderlich ( Borodin 1984 ).

Die reelle projektive Ebene hat die Euler-Charakteristik χ = 1 und die Formel ergibt p = 6 , sodass nicht mehr als sechs Farben benötigt werden.

• 
  Ein radialsymmetrischer, siebenfarbiger Torus – Bereiche gleicher Farbe winden sich entlang gestrichelter Linien.
• 
  Ein achtfarbiger Doppeltorus (Fläche vom Geschlecht zwei) – Blasen kennzeichnen den eindeutigen Kontakt zweier Bereiche
• 
  Ein neunfarbiger dreifacher Torus (Oberfläche vom Geschlecht drei) – die Flecken bezeichnen die Enden ihrer jeweiligen Tunnel.
• 
  Eine sechsfarbige Klein-Flasche
• 
  Tietzes Unterteilung eines Möbiusbandes in sechs zueinander benachbarte Regionen erfordert sechs Farben. Die Knoten und Kanten dieser Unterteilung bilden eine Einbettung des Tietze-Graphen in das Band.
• 
  Eine Scheibe repräsentiert die reelle projektive Ebene; gegenüberliegende Punkte auf dem Kreis werden identifiziert. Die projektive Ebene lässt sich anhand des Petersen-Graphen in sechs Fünfecke unterteilen , was zu einer 6-Färbung führt.
• 
  Interaktives Szilassi-Polyedermodell . Jede der sieben Flächen grenzt an jede andere – im SVG-Bild kann die Drehung durch Bewegen der Maus erfolgen.

Für Graphen, deren Knoten als Punktpaare auf zwei verschiedenen Flächen dargestellt werden und deren Kanten als sich nicht kreuzende Kurven auf einer der beiden Flächen gezeichnet sind, kann die chromatische Zahl mindestens 9 und höchstens 12 betragen , genauere Schranken sind jedoch nicht bekannt; dies ist Gerhard Ringels Erde -Mond-Problem . ^{[ 33 ]}

Das Ergebnis der Färbung lässt sich nicht ohne Weiteres auf dreidimensionale Körper übertragen. Mithilfe von n gefalteten Stäben kann man erreichen, dass jeder Stab jeden anderen berührt. Die Anordnung erfordert dann n Farben, oder n + 1, wenn der leere Raum (der ebenfalls jeden Stab berührt) mit einbezogen wird. Die Zahl n kann als beliebige ganze Zahl gewählt werden, beliebig groß. Solche Beispiele waren Frederick Guthrie bereits 1880 bekannt. ^{[ 34 ]} Selbst für achsenparallele Quader (zwei Quader gelten als benachbart, wenn sie eine gemeinsame zweidimensionale Begrenzungsfläche haben) kann eine unbegrenzte Anzahl von Farben erforderlich sein. ^{[ 35 ]}

Dror Bar-Natan machte eine Aussage über Lie-Algebren und Vassiliev-Invarianten , die äquivalent zum Vierfarbensatz ist. ^{[ 36 ]}

Obwohl die Verwendung des Theorems ursprünglich für die farbliche Darstellung politischer Länderkarten gedacht war, ist es für Kartographen nicht von besonderem Interesse . Laut einem Artikel des Mathematikhistorikers Kenneth May sind „Karten, die nur vier Farben verwenden, selten, und die, die dies tun, benötigen in der Regel nur drei. Bücher zur Kartographie und zur Geschichte der Kartographie erwähnen die Vierfarbeneigenschaft nicht.“ ^{[ 37 ]} Das Theorem garantiert auch nicht die übliche kartographische Anforderung, dass nicht zusammenhängende Gebiete desselben Landes (wie die Exklave Alaska und der Rest der Vereinigten Staaten ) identisch eingefärbt werden. ^{[ 38 ]} Da das Vierfarbentheorem nicht gilt, wenn die Gebiete auf der Karte nicht zusammenhängend sind, ist es auch nicht auf die Weltkarte anwendbar. Auf der Weltkarte grenzen der Ozean, Belgien, Deutschland, die Niederlande und Frankreich aneinander, da die Niederlande auf der Insel Saint-Martin an Frankreich grenzen .

Der Satz ist auch dann nicht anwendbar, wenn man fordert, dass alle Gewässer dieselbe Farbe erhalten, die nicht für ein Land verwendet werden kann (z. B. Blau). Dann ist die Karte Europas selbst nicht vierfarbig. Frankreich, Deutschland und Belgien benötigen drei verschiedene Farben, da sie alle aneinandergrenzen, sodass insgesamt vier Farben verwendet werden. Frankreich und die Niederlande können dieselbe Farbe erhalten, Luxemburg benötigt jedoch eine fünfte. ^{[ 39 ]}

• Apollonisches Netzwerk
• Fünffarbensatz
• Graphfärbung
• Satz von Grötzsch : Dreiecksfreie planare Graphen sind 3-färbbar.
• Hadwiger-Nelson-Problem : Wie viele Farben werden benötigt, um die Ebene so einzufärben, dass keine zwei Punkte im Abstand von einer Einheit die gleiche Farbe haben?

• „Vierfarbenproblem“ , Enzyklopädie der Mathematik , EMS Press , 2001 [1994]
• Wilson, Robin (März 2026). „Der Vierfarbensatz: 1852–1976“ (PDF) . Notices of the American Mathematical Society . 73 (3): 216–228 . doi : 10.1090/noti3305 .
• Liste der Verallgemeinerungen des Vierfarbensatzes auf MathOverflow