5. Fünf Farben reichen immer

Überrascht dich das? Hattest du mit mehr gerechnet? Weil unser Vorstellungsvermögen auf diese ungewöhnliche Aufgabe kaum eingestellt ist, halten wir uns an die exakte mathematische Schlussweise hier in der Gestalt eines Induktionsbeweises über die Anzahl f der Länder. Fünf Farben reichen offenbar aus, wenn die Landkarte nicht mehr als fünf Länder enthält. Wir werden nun zeigen, dass alle Karten mit höchstens
        ( f + 1 )
      =( 5 + 1 )
      =( f = 6 ) Ländern
also:( f >= 5 ) mit nur fünf Farben
Karten mit maximal f Ländern möglich ist.
In dieser Abbildung sind 6 f Länder dargestellt mit 5 unterschiedlichen Farben.



Zunächst überlegen wir uns : In jeder Landkarte existiert ein Land S mit nicht mehr als fünf Grenzen! Denn wenn das Land S sechs Grenzen hätte, erhielten wir beim Zählen der k (Kanten) Grenzen (1 , 2, 3, ...) von den f (Flächen) Nachbarländern (l, ll, lll, ...) bzw. den e (Knoten) Ecken (A, B, C, ...) von den 7 Ländern:
                                                                                                                                                2k>=6f und 2k >= 3e
                                                                                                                                                2*12>=6f und 2*12 >= 3*6
                                                                                                                                                24 >= 6 und 24 >= 18

Jede Grenze wurde zweimal gezählt (2k ), weil eine Grenze immer zu zwei Ländern gehört (z. B. ist 7 Grenze von Land l und Vl ). Jeder Knoten wurde dreimal gezählt (3e) da eine Ecke immer zu 3 Ländern gehört (z. B. ist B Ecke von Land S , l und ll ). Es werden nur die sechs Nachbarländer gezählt (6f), das Land S bleibt erst einmal außen vor.



Mit Hilfe der Eulersche Polyederformel: - Für einen zusammenhängenden Graphen
(Seite "Die zänkischen Nachbarn")           mit Knotenanzahl e, Kantenzahl k und Flächenzahl f
                                                                        (bei "ebener" Darstellung; einschließlich der äußeren Fläche)
                                                                        gilt stets: e + f = k + 2.
würde dann 3k >= 3( e + f ) = 3( k + 2 ) folgen, eine falsche Aussage!

Denn:     3*12 >= 3( 6 + 6) = 3( 12 + 2 )
               36 >= 3*12 = 3*14
               36 >= 36 = 42 falsche Aussage!

Damit ist die Existenz von S gesichert.





Hat S vier oder weniger Nachbarn, so vereinigen wir es mit einem von ihnen (hier l). Dann färben wir die entstehende Karte mit höchstens f Ländern und vergeben dann an S jene Farbe, die bei seinen Nachbarn nicht auftritt.





Besitzt S fünf Nachbarländer, so gibt es unter diesen zwei Länder, die nicht benachbart sind(z. B. Land l und ll). Anderenfalls erhielte man nämlich - die fünf Hauptstädte paarweise durch sich gegenseitig nicht kreuzende Eisenbahnlinien verbunden - den Graph der fünf zänkischen Nachbarn, der aber bekanntlich nicht eben ist. Wir können S mit diesen beiden Nachbarländern vereinigen (l + S + ll ), die entstehende Karte mit höchstens ( f - 1 ) Ländern mit fünf Farben färben und anschließend an S jene Farbe vergeben, die unter seinen mit vier Farben gefärbten fünf Nachbarn nicht vorkommt.

Wenn ihr wissen wollt, ob es auch Lösungen mit weniger Farben gibt, dann schaut doch einfach mal auf die Seite: "Reichen bereits vier Farben?"



Ein Seeungeheuer staunt
Zurück zur Gliederung