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.