Ebener Graph/Fünf Farben/Fakt/Beweis/Aufgabe/Lösung

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Wir führen Induktion über die Anzahl der Knoten, wobei die Aussage bei höchstens Knoten unmittelbar klar ist. Es liege also ein ebener Graph mit Knoten vor und für jeden ebenen Graphen mit weniger als Knoten wissen wir, dass es eine zulässige Färbung mit höchstens Farben gibt. Nach Fakt  (2) gibt es einen Knoten mit höchstens Nachbarn. Es sei der Graph, der aus entsteht, wenn man und die an anliegenden Kanten herausnimmt. Nach Induktionsvoraussetzung besitzt eine zulässige Färbung mit höchstens fünf Farben. Wenn die Nachbarn von nur höchstens vier Farben verwenden, was insbesondere dann der Fall ist, wenn nur vier Nachbarn besitzt, so kann man unmittelbar eine zulässige Färbung von zu einer zulässigen Färbung von ausbauen, indem man eine Farbe gibt, die in seinen Nachbarn nicht vorkommt.

Der Punkt habe also genau Nachbarn mit verschiedenen Farben. Wir fixieren eine ebene Realisierung und wir bezeichnen die Nachbarn von mit im Uhrzeigersinn (ein kleiner Kreis um in , der keinen weiteren Knotenpunkt enthält, trifft jeden Verbindungsweg zu den Nachbarn in einem Punkt der Peripherie, dies legt die Reihenfolge fest). Es sei eine zulässige Färbung auf . Wie betrachten den induzierten Untergraphen

Wir machen nun eine Fallunterscheidung je nachdem, ob und in miteinander durch einen Weg verbunden sind oder nicht.

Fall 1. Sie sind nicht miteinander verbunden. Es sei die Zusammenhangskomponente von , die enthält. Dabei gilt . Wir legen jetzt auf eine neue Färbung fest, indem wir

festlegen. Für die Knoten aus werden also die beiden Farben und vertauscht, alle anderen Knoten behalten ihre Farben. Diese Färbung ist wieder zulässig. Dies ist klar für Kanten, die ganz außerhalb von oder ganz innerhalb von verlaufen. Bei und besitzt bei dieser Knoten eine von und verschiedene Farbe, und bei gibt es keine Kante.

Fall 2. Es gibt nun einen verbindenen Weg in von nach . Wenn es keinen verbindenden Weg von nach innerhalb des entsprechend definierten Untergraphen gibt, so sind wir aufgrund der Argumentation im ersten Fall fertig. Wir sind somit in der Situation, wo es einen Weg von nach in und einen Weg von nach in gibt. Wir ergänzen durch die Kanten und zu einem Zykel in , der in der ebenen Realisierung einem geschlossenen Weg entspricht (indem wir ohne Knotenwiederholungen wählen, können wir diesen geschlossenen Weg als überschneidungsfrei annehmen). Hierbei liegt einer der Punkte oder

im Inneren des durch den Weg begrenzten Gebietes und der andere außerhalb davon. Dann gibt es aber eine Überschneidung der beiden Wege, und diese muss in einem Knotenpunkt vorliegen. Dies ist aber ein Widerspruch, da die Farben alle verschieden sind.
Zur gelösten Aufgabe