Formalisierung

Formal lässt sich das Problem am einfachsten mit Hilfe der Graphentheorie beschreiben. Man fragt ob die Knoten jedes planaren Graphen mit maximal vier Farben so gefärbt werden können, dass keine benachbarten Knoten die gleiche Farbe tragen. Oder kürzer: "Ist jeder planare Graph 4-färbbar?" Dabei wird jedem Land der Karte genau ein Knoten zugewiesen und zwei Knoten, deren Länder angrenzen, verbunden.

Ebenen aus. Allerdings spart der Beweis des Satzes von Ringel-Youngs den Spezialfall für Kugeloberflächen bzw. Das klassische Vier-Farben-Problem betrifft Landkarten, die auf einer Ebene oder Kugeloberfläche liegen.Das Vier-Farben-Problem ist ein Spezialfall der Heawood-Vermutung, die seit ihrem Beweis im Jahre 1968 "Satz von Ringel-Youngs" heißt. Die 'Heawood-Vermutung' stellt das analoge Problem für allgemeine Oberflächen, etwa die Kleinsche Flasche (6 Farben), das Möbiusband (6 Farben), die Projektive Ebene (6 Farben) und den Torus (7 Farben). Interessanterweise ist die Verallgemeinerung wesentlich leichter zu beweisen als der Vier-Farben-Satz und kommt ohne Computerhilfe aus. Der Vier-Farben-Satz wird also nicht durch diesen Beweis verifiziert, sondern muss gesondert behandelt werden.