4-Farben-Satz

Einleitung

Der vier Farben Satz beschreibt, dass man in jedem planaren Graphen die Knoten mit 4 Farben färben kann, ohne dass eine Kante an beiden Endknoten die gleiche Farbe hat.

Viel anschaulicher bedeutet das, dass man jede Landkarte, egal welche Form und Anordnung die Länder haben, mit 4 Farben färben kann, ohne dass zwei benachbarte Länder (also zwei Länder, die sich eine Grenze teilen) die gleiche Farbe haben.

//Bild einfügen

Planarer was?

Ein Graph besteht aus Knoten und Kanten. Eine Kante verbindet jeweils zwei Knoten. Man kann sich Knoten gut als Punkte und Kanten als Verbindungen (Linien) zwischen den Knoten vorstellen, aber Graphen können alles mögliche repräsentieren, beispielsweise können Knoten für Länder stehen und Kanten für Grenzen zwischen Ländern (sodass genau dann eine Kante zwischen zwei Ländern existiert, wenn diese benachbart sind).

Ein planarer Graph ist nun einfach ein Graph, der in einer 2-dimensionalen Ebene, mit Punkten als Knoten und Linien als Kanten, gezeichnet werden kann, ohne dass sich zwei Kanten schneiden. Dies ist für das Landkarten-Problem auf jeden Fall erfüllt, da man offensichtlich einfach die Länder durch Punkte und die Ländergrenzen durch Linien zwischen den Punkten ersetzten kann, sodass man einen Graphen erhält, wo sich keine Linien überschneiden müssen, da sich unterschiedliche Ländergrenzen auch nicht überschneiden können.

4-Farben-Satz

Der 4-Farben-Satz wurde 1852 erstmals von dem südafrikanischen Mathematiker Francis Guthrie als Vermutung aufgestellt. Bereits im 19. Jahrhundert wurden einige vermeintliche Beweise dieses Satzes aufgestellt, jedoch stellten sich alle Versuche im Nachhinein als inkorrekt heraus.

Erst 1976 verkündeten Kenneth Appel und Wolfgang Hagen der University of Illinois, dass es ihnen gelang, den Satz durch einen computergestützten Beweis zu zeigen. Der Beweis widerlegte, dass es eine minimale Anzahl an Flächen gibt, sodass der Graph nicht mehr vierfärbbar wäre, indem die unendliche Menge von Graphen auf 1834 (später auf 633) relevante Möglichkeiten vereinfacht wurde. Zu seine Zeit war dies der erste computergestützte Beweis seiner Art.