Die Färbung planarer Karten verständlich erklärt

Auf einer flachen Landkarte genügen vier Farben, damit angrenzende Bezirke nie gleich aussehen. Doch diese vier zu finden ist schwer. Die Seite zeigt, woran einfache Verfahren scheitern und welcher alte Kniff dann hilft.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Karte und vier Buntstifte

Sie bekommen die Karte eines kleinen Landes mit vielen Bezirken und dazu Buntstifte. Die Regel ist einfach: Zwei Bezirke, die ein Stück Grenze teilen, dürfen nicht dieselbe Farbe tragen. Bezirke, die sich nur in einer Ecke berühren, dürfen gleich aussehen.

Vier Stifte genügen, sagt der Vierfarbensatz. Er gilt für jede Karte, die flach auf dem Tisch liegt und deren Bezirke je aus einem Stück bestehen. Bewiesen wurde er erst mit Hilfe von Computerrechnungen.

Mathematiker zeichnen dazu ein Bild. Jeder Bezirk wird ein Punkt. Zwei Punkte verbindet ein Strich, wenn die Bezirke aneinander grenzen. Ein solches Netz aus Punkten und Strichen heißt Graph. Gefärbt werden die Punkte, und jeder Strich muss zwei verschiedene Farben verbinden.

Dasselbe Bild passt auf Funkmasten: Benachbarte Masten dürfen nicht dieselbe Frequenz nutzen, sonst stören sie sich. Die Frequenzen sind die Farben.

Die Vier ist garantiert, aber schwer zu finden

Der Satz sagt nicht, wie man die Färbung findet. Wer Bezirk für Bezirk anmalt, kann in eine Sackgasse geraten: Ein Bezirk hat Nachbarn in allen vier Farben, und für ihn ist kein Stift mehr übrig.

Zwei einfache Vorgehen zeigen das Problem.

• Nacheinander malen (Fachwort: Greedy): Die Bezirke kommen in einer festen Reihenfolge dran. Jeder bekommt die erste Farbe, die noch erlaubt ist.
• Das engste zuerst (Fachwort: DSATUR): Als Nächstes kommt der Bezirk, in dessen Nachbarschaft schon die meisten verschiedenen Farben stehen. Er hat die kleinste Auswahl.

Beide Vorgehen nehmen sofort eine erlaubte Farbe und nie etwas zurück. Das nennt man gierig. Wie oft sie damit scheitern, zeigt die Messung weiter unten.

Der alte Trick: Farben in einer Kette tauschen

Mit fünf Stiften lässt sich die Sackgasse auf einer flachen Karte immer auflösen, ohne neu zu beginnen. Mit vier Stiften ist es der schwere Fall, dazu gleich mehr. Ein Beispiel: Der Bezirk Mitte ist noch weiß. Fünf Nachbarn umgeben ihn im Kreis: Nord ist rot, Nordost gelb, Südost blau, Süd grün und West lila. Alle fünf Stifte sind rund um Mitte vergeben.

Die Lösung ist eine Kette. Sie besteht aus Bezirken, die nur rot oder blau sind und sich der Reihe nach berühren. Wir suchen die Kette, die bei Nord beginnt. Vertauscht man in ihr rot und blau, bleibt die Karte erlaubt. Ein Bezirk neben der Kette, der nicht dazugehört, ist weder rot noch blau, sonst gehörte er zur Kette. Er hat nach dem Tausch also nie die Farbe seines Nachbarn in der Kette. Zwei Nachbarn in der Kette waren vorher verschieden und sind es danach wieder. (Nach dem Mathematiker Alfred Kempe heißt sie Kempe-Kette.)

Es gibt zwei Möglichkeiten.

• Erster Fall: Die Kette von Nord erreicht Südost nicht. Wir tauschen rot und blau in ihr. Nord wird blau, rot ist rund um Mitte frei, und Mitte wird rot.
• Zweiter Fall: Die Kette von Nord führt bis Südost. Mit Mitte als Glied bildet sie eine geschlossene Schleife auf der Karte. Nordost liegt innerhalb, Süd und West liegen außerhalb. Nun suchen wir die gelb-grüne Kette, die bei Nordost beginnt. Um Süd zu erreichen, müsste sie die Schleife durchqueren. Auf einer flachen Karte geht das nicht, ohne dass sich zwei Linien kreuzen. Wir tauschen gelb und grün in ihr: Nordost wird grün, gelb ist rund um Mitte frei, und Mitte wird gelb.

So kommt man mit fünf Stiften immer aus, wie der Mathematiker Percy Heawood zeigte. Mit vier Stiften reicht dieser Gedankengang nicht, denn dort sind mehrere Tausche nacheinander nötig, die einander wieder zerstören können. Kempe hielt ihn dennoch für den Beweis des Vierfarbensatzes. Heawood fand Jahre später eine Karte, an der das geschieht.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf am Ende dieses Teils öffnet sie, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Die Demo färbt erfundene Karten. Sie würfelt Standorte aus und verbindet nahe Standorte zu Dreiecken; jeder Standort ist ein Bezirk. Das ist ein vereinfachtes Rechenbild. Die Aussagen im Rest dieses Teils beschreiben dieses Rechenbild, nicht die Wirklichkeit.

Zu den zwei einfachen Vorgehen kommt ein drittes mit dem Kettentrick: Es malt nacheinander mit höchstens fünf Stiften und tauscht Ketten, wenn es sonst nicht weiterkäme. Danach räumt es auf und versucht, den fünften Stift durch weitere Tausche wieder loszuwerden.

Was die Messung zeigt

Für jede Kartengröße färbte die Demo 20 Karten und zählte, bei wie vielen ein Vorgehen mit vier Farben auskommt. Bei 30 Bezirken waren es 75 % (nacheinander malen), 65 % (das engste zuerst) und 100 % (das dritte Vorgehen). Bei 100 Bezirken sanken die beiden einfachen auf 0 % und 5 %, bei 300 Bezirken auf 0 % und 0 %, die übrigen Karten endeten bei fünf Farben. Das dritte Vorgehen blieb bei 95 % und 90 %.

Diesen Unterschied macht das Aufräumen, nicht der Kettentausch beim Malen. Es gelingt aber nicht bei jeder Karte.

Häufige Missverständnisse

• „Vier Farben genügen für jedes Netz aus Punkten und Strichen.“ Nein. Fünf Bezirke, die einander alle berühren, brauchen fünf Farben, weil je zwei verschieden sein müssen. Auf einer flachen Karte lassen sich solche Bezirke nicht zeichnen, weil sich dabei irgendwo zwei Grenzen kreuzen müssten.
• „Wenn das Aufräumen scheitert, gehen vier Farben nicht.“ Nein. Auf einer flachen Karte gehen vier Farben nach dem Satz stets; nur der Weg über Ketten findet sie nicht immer.

Woran Sie das im Alltag erkennen

Anzeichen bei jeder Einteilung:

• Manche Paare dürfen nicht in dieselbe Gruppe. Beispiel: Zwei Prüfungen mit denselben Studierenden brauchen verschiedene Termine. Die Termine sind die Farben.
• Sie planen nacheinander, und zuletzt passt eine Sache in keine Gruppe mehr, obwohl der Rest gut aufgeht. Das ist die Sackgasse.
• Folgerung für Sitzordnung oder Stundenplan: Bei Beziehungen wie Nachbarschaften auf einer flachen Karte genügen vier Gruppen. Bei beliebigen Konflikten nicht: Fünf Kinder, die sich paarweise nicht vertragen, brauchen fünf Tische.

Wie ernst ist das Rechenbild zu nehmen?

Jede Zahl stammt aus nur 20 erfundenen Karten je Größe. Sie zeigt Tendenzen, keine feinen Unterschiede.

Was Sie mitnehmen:

• Dass es eine Lösung gibt, heißt nicht, dass ein einfaches Vorgehen sie findet.
• Vor einem Neuanfang lohnt das Vertauschen einzelner Zuteilungen; es klappte in der Messung meist, nicht immer.
• Fragen Sie bei jeder Garantie nach ihren Bedingungen: Gilt sie auch, wenn beliebige Paare einander stören?

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt Modell, Verfahren und Messreihen der zugehörigen Demo, eines Programms zum Ausprobieren im Browser.

• Problem: Gegeben ist ein einfacher ungerichteter planarer Graph \(G=(V,E)\) mit \(n\) Knoten und \(m\) Kanten, geradlinig und kreuzungsfrei gezeichnet. Gesucht ist eine Färbung \(c\), die jedem Knoten eine Farbe (eine Zahl ab null) zuordnet, mit \(c(u)\ne c(v)\) für jede Kante \(uv\in E\) und möglichst wenigen Farben. Die kleinste Farbenzahl, mit der eine zulässige Färbung gelingt, heißt \(\chi(G)\); \(d(v)\) ist der Grad von \(v\). Bei einer Landkarte sind die Gebiete die Knoten und gemeinsame Grenzstücke die Kanten; das setzt Gebiete aus je einem Stück voraus.
• Kempe-Kette: Für zwei Farben \(a\ne b\) und einen Knoten \(u\) mit \(c(u)\in\{a,b\}\) ist die Kette von \(u\) die Zusammenhangskomponente von \(u\) in dem Teilgraphen, der von den Knoten der Farben \(a\) und \(b\) induziert wird.
• Smallest-Last-Ordnung: eine Reihenfolge \(v_1,\dots,v_n\), in der \(v_i\) ein Knoten kleinsten Grades in \(G-\{v_1,\dots,v_{i-1}\}\) ist.
• Netztypen: Karte (Kanten der Delaunay-Triangulierung zufällig im Quadrat gezogener Standorte, also der kreuzungsfreien Zerlegung in Dreiecke, deren Umkreise keinen weiteren Standort enthalten; bei einer Dichte unter 100 % zufällig verdünnt) und Raster (Gitter mit einer Diagonale je Zelle). Die Dichte ist die Kantenzahl in Prozent von \(3n-6\), der Höchstzahl der Kanten eines planaren einfachen Graphen mit \(n\ge 3\) Knoten. Dazu sechs Lehrbuch-Graphen: Ikosaeder, Oktaeder, \(K_4\), \(K_5\) ohne eine Kante, \(K_5\) und Petersen-Graph. Rechnung dieser Seite: Eine volle Delaunay-Triangulierung hat \(3n-3-h\) Kanten (\(h\): Zahl der Standorte auf dem äußeren Rand der Standortwolke); 100 % heißt bei der Karte also „alle Delaunay-Kanten“, knapp unter \(3n-6\).
• Greedy: färbt in umgekehrter Smallest-Last-Ordnung jeden Knoten mit der kleinsten Farbe, die kein bereits gefärbter Nachbar trägt. DSATUR: wählt als Nächstes den ungefärbten Knoten mit den meisten verschiedenen Nachbarfarben und gibt ihm die kleinste freie Farbe. Beide nutzen die Zeichnung nicht; die Schranke von sechs Farben für Greedy folgt allerdings aus der Planarität (Herleitung unten).
• Heawood-Verfahren: setzt die Knoten in umgekehrter Smallest-Last-Ordnung ein; jeder hat dann höchstens fünf bereits gefärbte Nachbarn. Ist unter den Farben 0 bis 4 eine frei, erhält der Knoten die kleinste freie (für eine Messreihe wählt eine Variante zufällig unter den freien). Sonst werden die Nachbarn nach dem Winkel in der Zeichnung rund um den Knoten geordnet (im Umlauf), und es wird die erste Kette zwischen zwei Nachbarn getauscht, die diese beiden nicht verbindet; dadurch wird eine Farbe frei. Es braucht höchstens fünf Farben.
• Kempe-Reduktion: Für jeden Knoten \(v\) mit der fünften Farbe wird für eine Farbe \(a<4\) wiederholt eine Kette der Farben \(a\) und \(b\) mit \(b\ne a\), \(b<4\) getauscht, sofern dadurch die Zahl der Nachbarn von \(v\) mit der Farbe \(a\) sinkt. Getauscht wird die Kette, die bei einem Nachbarn \(u\) von \(v\) mit \(c(u)=a\) beginnt. Probiert werden die Farben \(a\) in aufsteigender Reihenfolge, bis eine frei wird; ist die Zahl null, erhält \(v\) die Farbe \(a\). Das läuft höchstens 30 Durchläufe über alle betroffenen Knoten, früher bei einem Durchlauf ohne Änderung. Es ist eine Heuristik ohne Garantie.
• Exakte Entscheidung „vier Farben möglich?“: Verzweigung nach DSATUR (der Knoten mit den meisten verschiedenen Nachbarfarben, jede erlaubte Farbe, höchstens eine neue Farbe je Schritt gegen Symmetrie) mit einem Budget von 100.000 Verzweigungsknoten. Ist es erreicht, lautet die Antwort „unentschieden“, nie „nein“.
• Messreihen: (1) Anteil der Karten mit höchstens vier Farben je Verfahren auf vollen Delaunay-Karten mit \(n = 30, 60, 100, 200, 300\) Knoten, je 20 feste (einmal gezogene) Karten, dazu die mittlere Zahl getauschter Ketten. (2) Kettenbedarf des Heawood-Verfahrens auf Karten mit 30, 100 und 300 Knoten (kleinste oder zufällige freie Farbe) und am Ikosaeder in 30 zufälligen Reihenfolgen mit zufälliger Farbwahl. (3) Exakte Entscheidung gegen Kempe-Reduktion für \(n = 30\) bis 200 und Dreifärbbarkeit verdünnter Karten (55 % von \(3n-6\) Kanten).

Die Formeln

Der Vierfarbensatz sagt, dass jeder planare Graph mit vier Farben auskommt:

\[\chi(G)\le 4\]

Das sagt, dass eine Färbung existiert, nicht wie man sie findet. Garantiert ist sie nur für planare Graphen: \(\chi(K_5)=5\). Bewiesen wurde sie mit Computerhilfe (Appel und Haken; später Robertson, Sanders, Seymour und Thomas). Die Demo beweist den Satz nicht, sie wendet ihn an. Die elementare Abschwächung ist der Fünffarbensatz von Heawood:

\[\chi(G)\le 5\]

Der Fünffarbensatz und die Garantien von Smallest-Last-Greedy und Heawood-Verfahren stützen sich auf die Kantenschranke planarer einfacher Graphen (der Beweis des Vierfarbensatzes braucht mehr):

\[m\le 3n-6\]

Daraus folgt, dass die Gradsumme \(2m\le 6n-12\) unter \(6n\) liegt, der mittlere Grad also unter 6. Jeder planare Graph hat deshalb einen Knoten vom Grad höchstens 5, und weil Teilgraphen planarer Graphen planar sind, gilt das auch in jedem Restgraphen der Smallest-Last-Ordnung.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.

Ein Kettentausch erhält die Zulässigkeit.

• Schritt 1: Sei \(K\) eine Kette der Farben \(a\) und \(b\) in einer zulässigen Färbung \(c\), und \(c'\) die Färbung, die auf \(K\) die Farben \(a\) und \(b\) vertauscht und sonst mit \(c\) übereinstimmt.
• Schritt 2: Eine Kante \(xy\) mit beiden Enden in \(K\): \(c(x)\) und \(c(y)\) sind verschieden und liegen in \(\{a,b\}\), also bleiben sie nach dem Vertauschen verschieden.
• Schritt 3: Eine Kante \(xy\) mit \(x\in K\), \(y\notin K\): Es gilt \(c(y)\notin\{a,b\}\), sonst läge \(y\) in der Komponente \(K\). Also ist \(c'(y)=c(y)\ne c'(x)\), denn \(c'(x)\in\{a,b\}\). Kanten außerhalb von \(K\) bleiben unverändert.

Der Fünffarbensatz (Heawood).

• Schritt 1: Nach der Kantenschranke gibt es einen Knoten \(v\) mit \(d(v)\le 5\). Induktion über \(n\): Entferne \(v\), färbe den planaren Graphen \(G-v\) mit höchstens fünf Farben und setze \(v\) wieder ein.
• Schritt 2: Tragen die höchstens fünf Nachbarn von \(v\) höchstens vier verschiedene Farben, ist eine der fünf Farben für \(v\) frei.
• Schritt 3: Sonst hat \(v\) genau fünf Nachbarn \(v_1,\dots,v_5\) im Umlauf um \(v\) mit den Farben \(1,\dots,5\). Sei \(P\) die Kette der Farben 1 und 3 ab \(v_1\). Erreicht \(P\) den Knoten \(v_3\) nicht, vertausche 1 und 3 auf ihr (zulässig nach der ersten Herleitung). Die Farbe 1 kommt dann unter den Nachbarn nicht mehr vor, und \(v\) erhält sie.
• Schritt 4: Erreicht \(P\) den Knoten \(v_3\), bilden ein Weg in \(P\) von \(v_1\) nach \(v_3\) und der Knoten \(v\) einen Kreis in der Ebene. Im Umlauf liegt \(v_2\) auf der einen Seite des Kreises, \(v_4\) und \(v_5\) liegen auf der anderen. Die Kette \(Q\) der Farben 2 und 4 ab \(v_2\) kann den Kreis nicht überqueren: Seine Knoten tragen die Farben 1 und 3 (und \(v\) ist noch ungefärbt), und kreuzungsfreie Kanten schneiden einander nicht. Also enthält \(Q\) den Knoten \(v_4\) nicht. Vertausche 2 und 4 auf \(Q\); die Farbe 2 wird frei, und \(v\) erhält sie.
• Schritt 5: Damit gilt \(\chi(G)\le 5\) für jeden planaren Graphen. Der Beweis braucht nur die Paare \(v_1,v_3\) und \(v_2,v_4\). Die Demo prüft nacheinander alle fünf Paare von Nachbarn mit Abstand zwei im Umlauf (eine Obermenge) und tauscht die erste Kette, die ihre beiden Nachbarn nicht verbindet. Der Umlauf ergibt sich aus dem Winkel in der Zeichnung; er ist nur bei geradliniger, kreuzungsfreier Zeichnung die Reihenfolge der Einbettung.
• Grenze des Schlusses: Er überträgt sich nicht auf vier Farben, weil dort mehrere Tausche nacheinander nötig sind, die einander stören können (allgemein bekannt, hier nicht geprüft). Kempes Versuch von 1879 war deshalb fehlerhaft; Heawood fand den Fehler 1890.

Smallest-Last-Greedy braucht höchstens sechs Farben. Beim Färben in der Reihenfolge \(v_n,\dots,v_1\) hat \(v_i\) nur Nachbarn unter \(v_{i+1},\dots,v_n\) schon gefärbt. Das sind genau seine Nachbarn in \(G-\{v_1,\dots,v_{i-1}\}\), und es sind höchstens fünf, weil \(v_i\) dort minimalen Grad hat und jeder planare Graph einen Knoten vom Grad höchstens 5 besitzt. Die kleinste freie Farbe liegt also unter den Farben 0 bis 5. Das Heawood-Verfahren nutzt dieselbe Reihenfolge und spart die sechste Farbe durch den Kettentausch; ohne Kette und mit kleinster freier Farbe färbt es genau wie Greedy (Nachzählung: gleiche Anteile in allen fünf Größen der ersten Messreihe).

Wann eine Kette überhaupt nötig ist. Das Heawood-Verfahren tauscht nur, wenn ein Knoten beim Einsetzen fünf gefärbte Nachbarn mit fünf verschiedenen Farben hat. Jede Kante zählt beim später eingesetzten Endknoten als „schon gefärbter Nachbar“; die Zahlen der bereits gefärbten Nachbarn summieren sich also zu \(m\), im Mittel zu weniger als 3 je Knoten. Fünf liegen weit darüber. Warum auf Karten null Ketten gemessen wurden, erklärt diese Rechnung nicht; sie nennt nur die Bedingung. Auf Karten mit 30 und 300 Knoten stammen die gezählten Ketten daher alle aus der Kempe-Reduktion.

Nichtplanare Beispiele. \(K_5\) hat \(m=10\) Kanten, aber \(3n-6=9\): Die Schranke ist verletzt, \(K_5\) ist nicht planar. Alle fünf Knoten sind paarweise benachbart, also gilt \(\chi(K_5)=5\). Der Petersen-Graph ist nicht planar und kommt dennoch mit drei Farben aus. \(K_5\) zeigt, dass die Voraussetzung „planar“ nötig ist; der Petersen-Graph zeigt, dass ein nichtplanarer Graph mit wenigen Farben auskommen kann.

Durchgerechnet: der Ikosaeder

Rechnung dieser Seite, soweit nicht als Messung der Demo gekennzeichnet.

• Größe: Grad 5 überall ergibt \(5n=2m\). Sind alle Flächen Dreiecke, gilt \(m=3n-6\). Zusammen folgt \(5n=6n-12\), also \(n=12\) Knoten und \(m=30\) Kanten. Allgemein gilt bei Mindestgrad 5 \(5n\le 2m\le 6n-12\), also \(n\ge 12\): Der Ikosaeder ist der kleinste planare Graph mit Mindestgrad 5 und der einzige Lehrbuch-Graph der Demo mit Grad 5 überall.
• Untere Schranke: Die fünf Nachbarn eines Knotens bilden einen Kreis aus fünf Knoten. Ein ungerader Kreis braucht drei Farben, der Knoten in der Mitte eine vierte; also gilt \(\chi\ge 4\). Die exakte Entscheidung der Demo liefert \(\chi=4\).
• Verfahren (Messung): Greedy, DSATUR und das Heawood-Verfahren enden bei fünf Farben, das Heawood-Verfahren mit Kempe-Reduktion bei vier.
• Warum hier eine Kette nötig sein kann: In jeder Einsetzreihenfolge hat der zuletzt eingesetzte Knoten alle fünf Nachbarn schon gefärbt. Tragen sie fünf verschiedene Farben, ist eine Kette nötig. Gemessen wurde das bei zufälliger Reihenfolge und zufälliger Farbwahl in 8 von 30 Reihenfolgen; mit der kleinsten freien Farbe wird die Kette seltener gebraucht (Nachzählung für dieselben 30 Reihenfolgen, keine Messung der Demo).

Befunde

Alle Zahlen stammen aus den Messreihen der Demo. „Volle Karten“ sind Delaunay-Karten mit der Dichte 100 %; je Größe werden 20 feste Karten gefärbt. Die Anteile sind als Näherung zu lesen, weil sich Zufallsziehungen zwischen Softwareversionen verschieben können.

Frage	Befund
Finden Greedy und DSATUR die Vier? (volle Karten, \(n = 30, 60, 100, 200, 300\))	DSATUR endet in 65 / 40 / 5 / 0 / 0 % der Karten auf vier Farben, Greedy in 75 / 15 / 0 / 0 / 0 %; die übrigen Karten enden bei fünf Farben. Bei \(n = 30\) liegt Greedy vor DSATUR; der Abstand sind zwei von 20 Karten (Rechnung dieser Seite), also im Rauschen der Stichprobe. Der Vierfarbensatz garantiert vier für alle.
Wie weit kommen die Ketten? (dieselben Karten)	Heawood-Verfahren mit anschließender Kempe-Reduktion: 100 / 95 / 95 / 90 / 90 % auf vier Farben; die übrigen bleiben bei fünf. Mittlere Zahl getauschter Ketten je Karte (Heawood-Verfahren und Reduktion zusammen, siehe Herleitung zum Kettenbedarf): 0,5 bei \(n = 30\), rund 12 bei \(n = 300\).
Braucht das Heawood-Verfahren die Kette?	Auf Karten mit 30, 100 und 300 Knoten in 0 von 60 Läufen, mit kleinster wie mit zufälliger freier Farbe. Am Ikosaeder in 8 von 30 zufälligen Reihenfolgen mit zufälliger Farbwahl.
Exakte Entscheidung oder Ketten? (volle Karten, Budget 100.000 Verzweigungsknoten)	Bei \(n = 30\) beantwortet die Entscheidung alle 20 Karten (Median 31 Verzweigungsknoten), bei \(n = 100\) liegt der Median bei 116,5. Bei \(n = 200\) beantwortet sie nur 16 von 20 Karten im Budget (4 unentschieden); die Kempe-Reduktion bringt 18 von 20 auf vier Farben.
Hilft der Satz bei drei Farben? (verdünnte Karten, 55 % von \(3n-6\) Kanten)	Nein: Bei \(n = 60\) sind 19 von 20 Karten dreifärbbar (eine nicht), bei \(n = 100\) sind es 14 von 20 (4 nicht, 2 unentschieden). Vierfärbbar sind alle 20. Ob drei Farben reichen, ist auch für planare Graphen NP-vollständig (Garey, Johnson, Stockmeyer): Ein schnelles Verfahren für alle Fälle ist nicht bekannt.
Gilt der Satz für nichtplanare Graphen?	Nein: \(K_5\) braucht fünf Farben (exakt bestimmt); der Petersen-Graph kommt mit drei aus.

Grenzen: was die Messung zeigt und was nicht

• Was sie belegt: die Tendenz, dass Greedy und DSATUR mit der Kartengröße die Vier verlieren, und dass die Ketten einen großen Teil zurückholen. Jede Färbung wird mit einem unabhängigen Prüfer auf gleichfarbige Kanten kontrolliert.
• Kleine Stichprobe: 20 feste Karten je Größe. Rechnung dieser Seite: Bei einem Anteil von einhalb liegt die Standardabweichung bei gut einem Zehntel; eine Karte Unterschied (95 gegen 90 %) ist kein Befund.
• Die Kempe-Reduktion ist eine Heuristik. Sie bleibt bei 5 bis 10 % der Karten ab \(n = 60\) bei fünf Farben hängen, obwohl vier Farben nach dem Satz stets reichen. Eine frühere Vormessung mit einer anderen Schleife kam auf leicht abweichende Zahlen; die Tendenz galt, die Zahlen sind nicht vergleichbar.
• Die exakte Entscheidung ist kein Maßstab für große Karten. Im Budget bleibt sie ab \(n = 60\) gelegentlich stecken; „unentschieden“ heißt nicht „nein“.
• Kettenbedarf und Zufallskarten: „Null von 60“ gilt nur für diese Zufallskarten mit 30, 100 und 300 Knoten; auf anderen Netzen oder bei anderer Reihenfolge kann die Kette vorkommen, wie der Ikosaeder zeigt. Verwaltungsgrenzen oder Straßennetze verhalten sich vielleicht anders; das misst die Demo nicht.
• Planarität der Zeichnung: Das Heawood-Verfahren braucht eine geradlinige, kreuzungsfreie Zeichnung; bei \(K_5\) und dem Petersen-Graph ist es nicht anwendbar. Gebiete aus mehreren getrennten Stücken sind nicht Teil des Modells; für sie gilt der Vierfarbensatz nicht in dieser Form (allgemein bekannt, hier nicht geprüft).
• Keine Laufzeiten, kein Löservergleich: Verglichen werden Farbenzahlen und Anteile, keine Sekunden und keine allgemeinen Löser (SAT, ganzzahlige Optimierung). Was eine zusätzliche Farbe in der Praxis kostet (Frequenzen, Termine), misst die Demo nicht.
• Nicht umgesetzt: ein Beweis des Vierfarbensatzes, das Verfahren von Robertson und anderen für eine Vierfärbung in quadratischer Zeit und nichtplanare Zufallsverbindungen als Instanzen.

Erweiterungen und Verweise

Verwandte Demos dieser Website:

• Planarität prüfen: Die Planaritäts-Demo entscheidet, ob sich ein Netz ohne Überkreuzung zeichnen lässt, und belegt die Antwort.
• Färben beliebiger Graphen: Die Graphfärbung färbt beliebige Graphen mit Greedy, Welsh-Powell, DSATUR und exakt; planare Graphen sind dort kein Thema.

Quellen

• A. B. Kempe: On the geographical problem of the four colours. American Journal of Mathematics 2 (1879), 193–200.
• P. J. Heawood: Map-colour theorem. Quarterly Journal of Pure and Applied Mathematics 24 (1890), 332–338.
• K. Appel, W. Haken: Every planar map is four colorable, Part I: Discharging. Illinois Journal of Mathematics 21 (1977), 429–490; Teil II „Reducibility“ im selben Band.
• N. Robertson, D. Sanders, P. Seymour, R. Thomas: A new proof of the four-colour theorem. Electronic Research Announcements of the AMS 2 (1996), 17–25.
• M. R. Garey, D. S. Johnson, L. Stockmeyer: Some simplified NP-complete graph problems. Theoretical Computer Science 1 (1976), 237–267.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/planar-faerbung-demo.

Die Literaturangaben wurden für diese Seite nicht im Original gelesen; sie stammen aus der Dokumentation der Demo, die sie per Suche gegen Bibliografie-Einträge geprüft hat. Die Herleitungen und die Rechnung zum Ikosaeder sind Rechnungen dieser Seite und keine Messungen der Demo.