Short-Facts:

•    Grundfrage: Wie viele Farben benötige ich um eine Landkarte einzufärben?
•    Erstes mathematisches Problem, das mit einem Computer gelöst wurde
•    Erst 126 Jahre nach Auftauchen des Problems wurde es mit Hilfe der Informatik gelöst

Theoretisch ist es möglich mit vier Farben jede planare Fläche so zu füllen, dass keine gleichen Farben unmittelbar aneinandergrenzen.

Erklärung:

Der Vier-Farben-Satz ist ein mathematischer Satz, welcher das erste große mathematische Problem beschreibt, das mithilfe von Computern gelöst wurde. Die zugrunde liegende Vermutung, dass eine beliebige Landkarte mit vier Farben färbbar sei, sodass keine aneinander grenzenden Länder die gleiche Farbe aufweisen, wurde bereits 1852 von Francis Guthrie aufgestellt. Mehrfach wurden danach Beweise und Gegenbeweise dazu aufgestellt, die jedoch alle widerlegt wurden. Sogar ein Computerbeweis wurde von Heinrich Heesch entworfen, doch in den 1960er und 1970er Jahren fehlte es dazu noch an Rechenzeit. Erst 1976 wurde dieser von Kenneth Appel und Wolfgang Haken an der University of Illinois so verbessert, dass er ausgeführt werden konnte. Dabei reduzierten sie das Problem auf 1936 Einzelfälle, die dann von einem ausreichend leistungsstarken Computer geprüft wurden.

Das Vier-Farben-Problem ist ein Spezialfall in der Graphentheorie. Das
klassische Vier-Farben-Problem betrifft Landkarten, die auf einer Ebene oder Kugeloberfläche liegen. In der Disziplin der Graphentheorie stellen sich Informatiker/innen  beispielsweise der Suche nach der kürzesten Route zwischen zwei Orten. In der Anwendung findet man diese Fragestellung dann z.B. in einem Navigationssystem wieder.

Wer den Vier-Farben-Satz einmal spielerisch ausprobieren möchte:
http://www.puzzlescript.net/play.html?p=8315260