Ebener Graph/Sechs Farben/Fakt/Beweis/Aufgabe/Lösung

Wir führen Induktion über die Anzahl der Knoten, wobei die Aussage bei höchstens ${}6$ 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 ${}6$ 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 sechs Farben. Die ${}5$ Nachbarn von ${}u$ verwenden höchstens ${}5$ Farben davon und daher kann man für ${}u$ eine sechste Farbe wählen, was insgesamt eine zulässige Färbung von ${}G$ mit ${}6$ Farben ergibt.

Zur gelösten Aufgabe