Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 26

Uff, das wär geschafft. Nicht nur Vorli braucht jetzt erstmal Urlaub. Irgendwas mit Bergen und Meer. Land egal.

Die Länder auf der Erde bilden zusammenhängende Gebiete (Exklaven werden ausgeschlossen), ihre Grenzen bilden kurvige Wege. Wir repräsentieren diese Situation durch einen Nachbarschaftsgraphen, wobei die Länder zu Knotenpunkten werden und zwei Knotenpunkte miteinander durch eine Kante verbunden werden, wenn die zugehörigen Länder eine Grenze gemeinsam haben, wobei wir Berührungen in einem einzigen Punkt ausschließen. Wenn man bei einer Karte jedem Land eine Farbe geben möchte derart, dass angrenzende Länder unterschiedliche Farben bekommen, so bedeutet dies, für den Graphen eine zulässige Färbung zu finden. Eine wichtige Frage der Graphentheorie ist, mit wie vielen Farben dies möglich ist. Da die Länder in der Ebene gegeben sind, ist der zugehörige Graph planar. Deshalb ist die Frage letztlich, was die chromatische Zahl eines ebenen Graphen ist. Wir werden hier den sogenannten Fünf-Farben-Satz beweisen, der besagt, dass man für jeden ebenen Graphen eine zulässige Färbung mit höchstens fünf Farben finden kann. Als Einstimmung beweisen wir zuerst den Sechs-Farben-Satz.

Wenn auch nur punktweise Berührungen zwischen Ländern als Grenzen denkbar sind, so lässt sich dies nicht durch einen planaren Graphen realisieren, da dann beliebig große vollständige Graphen auftreten können.

Satz

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens sechs Farben.

Beweis

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 Korollar 25.6  (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.

$\Box$

Satz

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens fünf Farben.

Beweis

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 Korollar 25.6  (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.

$\Box$

Es war ein lange offenes Problem der Graphentheorie, ob auch der Vier-Farben-Satz gilt, ob man also jeden planaren Graphen mit vier Farben zulässig färben kann. Dieser Satz wurde erst 1976 von Kenneth Appel und Wolfgang Haken bewiesen, der Beweis erforderte den Einsatz von Computern, um die vielen nötigen Fallunterscheidungen zu beherrschen. Bis heute gibt es keinen computerfreien Beweis.

Satz

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens vier Farben.

<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)