Der Fünffarbensatz
Von: Fabi
Datum: Mo. 23. Februar 2004 15:03:48
Thema: Mathematik



Viele von euch haben bestimmt schon mal vom Vierfarbensatz gehört:

Jede Landkarte lässt sich mit 4 Farben färben, so dass benachbarte Länder verschiedene Farben haben.

Der Beweis dieses Satzes ist äußerst schwer und wurde erst 1977, 125 Jahre, nachdem die Vermutung aufgestellt worden war, bewiesen, und auch dieser Beweis war umstritten – er baute zum Großteil auf den Rechungen eines Computers auf, die man per Hand nicht nachvollziehen konnte.

Umso erstaunlicher ist es, dass man den Satz in einer leichten Abschwächung ohne besondere Kenntnisse beweisen kann:

Jede Landkarte lässt sich mit 5 Farben färben, so dass benachbarte Länder verschiedene Farben haben.



Da das Problem in seiner Formulierung mit den Landkarten begrifflich schwer zu handhaben ist, modelliert man die Karte als Graph: Die Länder sind die Ecken, und zwei Ecken sind genau dann durch eine Kante verbunden, wenn die beiden entsprechenden Länder eine gemeinsame Grenze haben.
Ein Beispiel:
Eine Landkarte mit rot darübergelegtem Graphen:

Bild

Graphen, die so aus Landkarten entstehen, sind aber nicht irgendwelche x-beliebigen Graphen, sondern recht spezielle.

Die wichtigste Eigenschaft, die solche Graphen haben: Man kann sie in einer Ebene zeichnen, ohne dass sich ihre Kanten schneiden. Soche Graphen nennt man ebene Graphen.

Die Behauptung, die wir jetzt beweisen wollen, lautet also:

Die Knoten eines jeden ebenen Graphen lassen sich so mit 5 Farben färben, dass je zwei durch eine Kante verbundene Knoten verschiedene Farben haben.

Oder kürzer ausgedrückt:

Jeder ebene Graph ist 5-färbbar.

Vor dem eigentlichen Beweis brauchen wir aber noch eine Eigenschaft ebener Graphen.

Bezeichnet man die Anzahl der Ecken eines ebenen Graphen mit e, die der Kanten mit k und die Anzahl der Flächen, in die die Ebene durch den Graphen eingeteilt wird (dabei zählt das Außengebiet mit), mit f, so gilt:

e+f-k = 2

Diese Formel nennt man die Eulersche Polyederformel (siehe in diesem Artikel). Man kann sie leicht per Induktion beweisen.

In einem ebenen Graphen wird eine Fläche durch mindestens 3 Kanten begrenzt, andererseits liegt eine Kante an zwei verschiedenen Flächen. Auf 2 Flächen kommen also mindestens 3 Kanten. Es ist also




Mit der Eulerformel kann man daraus eine Abschätzung für die Anzahl der Kanten in einem ebenem Graphen gewinnen:





Es gibt in einem ebenen Graphen mit e Ecken also höchstens 3e-6 Kanten.

Als letzten Begriff benötigen wir den Durchschnittsgrad d eines Graphen. Das ist einfach die durchschnittliche Anzahl der an eine Ecke grenzende Kanten.
Hat man z.B. in einem Graphen 4 Ecken, an die je 2 Kanten grenzen, und 2 weitere Ecken, an die je 3 Kanten grenzen, so ist der Durchschnittsgrad dieser 6 Ecken


Da jede Kante an genau zwei Ecken angrenzt und somit zweimal in den Durchschnitt miteinbezogen wird, gilt


Für ebene Graphen gilt insbesondere



Der Durchschnittsgrad eines ebenen Graphen ist daher immer kleiner als 6, es gibt also immer Ecken, an denen 5 oder weniger Kanten liegen. Das ist die Eigenschaft ebener Graphen, auf denen der Beweis des Fünffarbensatzes aufbaut.

Jetzt kann der Beweis endlich begonnen werden:

Für Graphen mit 1, 2, 3, 4, 5 Ecken ist die Behauptung trivial.

Sei G nun ein ebener Graph mit e > 5 Ecken, und sei die Behauptung richtig für alle Graphen mit weniger Ecken.

G enthält eine Ecke v, an der höchstens 5 Kanten anliegen und damit auch höchstens 5 Nachbarn hat.
Löscht man diese Ecke und alle anliegenden Kanten, so bleibt ein ebener Graph G’ mit e-1 Ecken übrig. Dieser ist nach Induktionsvoraussetzung fünffärbbar.

Sei G’ nun fünfgefärbt. Hat v 4 oder weniger Nachbarn, so haben die an v angrenzenden Ecken nur höchstens 4 verschiedene Farben, man kann v also einfach mit der fünften Farbe färben und hat eine Fünffärbung von G. Man kann also annehmen, dass v tatsächlich 5 Nachbarn hat und diese sogar alle verschieden gefärbt sind, sonst wäre ja wieder eine Farbe nicht unter den Nachbarn von v vertreten und man färbt v einfach in dieser Farbe.

Das ganze sieht also mit den 5 Fraben rot,grün,blau, gelb und orange so aus:

Bild


Wir wollen nun versuchen, durch geschicktes Umfärben einzelner Ecken zu erreichen, dass eine Farbe für v frei wird.

Betrachten wir mal in der Zeichnung die rote und die blaue Ecke. Könnten wir die rote Ecke r blau färben, so ließe sich v rot färben. Wann geht das?
Färben wir r blau, müssen wir natürlich auch alle an r angrenzenden blauen Ecken umfärben, sonst hätten wir ja zwei benachbarte blaue Ecken. Färben wir all diese blauen Ecken einfach mal rot.
Dann müssen wir auch wieder alle an diese umgefärbten Ecken angrenzenden roten Ecken umfärben, sagen wir mal in blau.

Setzen wir dieses Verfahren fort, so tauschen wir die Farben rot und blau auf all den Ecken, die mit r durch einen Kantenzug verbunden sind, auf dem nur rote und blaue Ecken liegen (einem rot-blau-Weg) – andere rote und blaue Ecken sind ja von r durch orange, grüne oder gelbe Ecken abgegrenzt, müssen also auch nicht umgefärbt werden.

Es ist also die Frage, ob die an v angrenzende blaue Ecke b mit einem rot-blau-Weg mit r verbunden ist. Wenn nicht, können wir r blau färben, ohne b umfärben zu müssen, und können v rot färben; wenn doch, dann müssten wir leider auch b rot färben, um nicht zwei blaugefärbte Ecken nebeneinander zu haben, und haben nichts gewonnen – immer noch grenzen alle 5 Farben an v an und wir können v nicht färben.

Die Existenz dieses rot-blau-Weges zwischen r und b liefert jetzt aber eine zusätzliche Strukturaussage über den Graphen, die wir nutzen können.

Bild

W ist der rot-blau-Weg zwischen r und b.

Nun können wir dasselbe Spielchen mit der orangen Ecke o und der grünen Ecke g machen: Gibt es keinen orange-grün-Weg zwischen den beiden, könnte man die orangene Ecke grün färben, in allen mit o durch einen orange-grün-Weg verbundenen Ecken orange und grün austauschen und dann v orange färben. Gibt es einen, haben wir leider immer noch nichts gewonnen.
Kann es aber überhaupt einen geben? Sieht man sich die Zeichnung an, so erkennt man, dass, egal wie man W einzeichnet, ein Weg von o nach g irgendwo W kreuzen muss (der Weg kann ja nicht eine der an v angrenzenden Kanten durchschneiden, weil der Graph eben ist).

Wo kann denn diese Kreuzung sein? Wegen der Ebenheit des Graphen muss diese Kreuzung eine Ecke sein, die auf W liegt. Diese Ecke liegt also auf dem rot-blau-Weg W, ist damit selbst entweder rot oder blau. Einen orange-grün-Weg von o nach g kann es damit nicht geben, weil er eine rote oder blaue Ecke enthalten müsste. Und damit können wir entsprechend umfärben, so dass man auch v gültig färben kann. Damit ist auch G fünfgefärbt. q.e.d.

Man kann also auch jede Landkarte mit 5 Farben färben.

Gruß
Fabi
 


Dieser Artikel kommt von Matroids Matheplanet
https://matheplanet.de

Die Url für diesen Artikel ist:
https://matheplanet.de/default3.html?article=568