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