6. Reichen bereits vier Farben?
Ich verrate euch noch etwas: Eine Landkarte, in der von jeder Ecke (Knoten) genau
drei Grenzen (Kanten) ausgehen, lässt sich dann und nur dann mit drei Farben färben,
wenn die Anzahl der Ecken (Knoten) jedes Landes gerade ist.
Zum Beispiel kann man diesen Graph mit nur drei Farben füllen, weil von jeden seiner
Knoten immer drei Kanten ausgehen (z.B. von A geht 1, 2 und
3 aus). Außerdem hat jedes Land vier Ecken (eine gerade Zahl), das am
nördlichsten liegende Land hat zum Beispiel die Eckpunkte A, B,
C und D.
Also sind auch nur spezielle Landkarten mit drei Farben färbbar. Allgemein reichen
fünf, was aber ist mit vier Farben?
Dieses Problem bewegte lange Zeit die Mathematiker. Erstmals erwähnt wurde die
Vermutung, dass stets vier Farben reichen könnten, 1852 in einem Brief von A. DE
MORGAN, den der Student F. GUTHRIE mit dieser Frage konfrontiert hatte. Schnell
musste man erkennen, dass dieses einfach erscheinende Problem komplizierte mathematische
Überlegungen erforderte. Erst 1890 zeigte P. HEAWOOD, dass fünf Farben immer ausreichen.
1975 wusste man, dass sich Karten mit höchstens 96 Ländern stets mit nur vier
Farben färben lassen. Die Forschungen nach einem Beweis oder einer Widerlegung der
Vierfarbenvermutung produzierten eine Unmenge von Erkenntnissen über ebene Graphen.
Einige Male glaubte man auch schon, Beweise gefunden zu haben, doch stellten sie
sich stets als fehlerhaft heraus. Erst 1976 zeigten K. APPEI und W. HAKEN, dass
jede Ebene Landkarte (in der sich keine Linien kreuzen) mit nur vier Farben färbbar
ist. Auch sie verwendeten einen Induktionsbeweis und wiesen mit Hilfe von Computerprogrammen
nach, dass jede Landkarte eine von 1936 Reduktionsfiguren enthält. (zum Beispiel diese:)
Die im Zusammenhang mit dem Vierfarbensatz erhaltenen Forschungsergebnisse sind
heute fester Bestandteil der Graphentheorie und finden Anwendung bis hin zum Entwurf
gedruckter Schaltungen und integrierter elektronischer Bauelemente.
Induktionsbeweis
Fünf Farben reichen immer
Zurück zur Gliederung
