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

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

Der Punkt ${}u$ habe also genau ${}5$ Nachbarn mit ${}5$ verschiedenen Farben. Wir fixieren eine ebene Realisierung und wir bezeichnen die Nachbarn von ${}u$ mit ${}v_{1},v_{2},v_{3},v_{4},v_{5}$ im Uhrzeigersinn (ein kleiner Kreis um ${}u$ in ${}\mathbb {R} ^{2}$, der keinen weiteren Knotenpunkt enthält, trifft jeden Verbindungsweg zu den Nachbarn in einem Punkt der Peripherie, dies legt die Reihenfolge fest). Es sei ${}c$ eine zulässige Färbung auf ${}H$. Wie betrachten den induzierten Untergraphen

${}V_{13}={\left\{v\in H\mid c(v)=c(v_{1}){\text{ oder }}c(v)=c(v_{3})\right\}}\,.$

Wir machen nun eine Fallunterscheidung je nachdem, ob ${}v_{1}$ und ${}v_{3}$ in ${}V_{13}$ miteinander durch einen Weg verbunden sind oder nicht.

Fall 1. Sie sind nicht miteinander verbunden. Es sei ${}W_{13}$ die Zusammenhangskomponente von ${}V_{13}$, die ${}v_{1}$ enthält. Dabei gilt ${}v_{3}\notin W_{13}$. Wir legen jetzt auf ${}H$ eine neue Färbung ${}c'$ fest, indem wir

${}c'(v)={\begin{cases}c(v),\,{\text{ falls }}v\notin W_{13}\,,\\c(v_{3}),\,{\text{ falls }}v\in W_{13}{\text{ und }}c(v)=c(v_{1})\,,\\c(v_{1}),\,{\text{ falls }}v\in W_{13}{\text{ und }}c(v)=c(v_{3})\,.\end{cases}}\,$

festlegen. Für die Knoten aus ${}W_{13}$ werden also die beiden Farben ${}c(v_{1})$ und ${}c(v_{3})$ 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 ${}W_{13}$ oder ganz innerhalb von ${}W_{13}$ verlaufen. Bei ${}x\in W_{13}$ und ${}y\notin W_{13}$ besitzt bei ${}y\notin V_{13}$ dieser Knoten eine von ${}c(v_{1})$ und ${}c(v_{3})$ verschiedene Farbe, und bei ${}y\in V_{13}$ gibt es keine Kante.

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

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 ${}c(v_{1}),c(v_{2}),c(v_{3}),c(v_{4})$ alle verschieden sind.

Zur gelösten Aufgabe