Folgerungen aus dem Eulerschen Polyedersatz & Der Fünffarbensatz

Aus dem Eulerschen Polyedersatz für planare Graphen erhält man die

Folgerung

Sei $G = (V,E)$ ein planarer zusammenhängender Graph mit $|V| \geq 4$. Dann gilt:

1. $|E| \leq 3 |V| - 6$.
2. $G$ hat mindestens einen Knoten vom Grad (Anzahl der Nachbarn) kleiner gleich $5$.

Bemerkung: Aus Teil 1 der obigen Folgerungen kann man unmittelbar erkennen, dass $K5$ ($5$ Knoten, $10$ Kanten - PlanarityBox nicht planar sein kann.

Beweis

Zu 1: Jedes Gebiet braucht mindestens drei berandende Kanten, jede Kante berandet höchstens zwei Gebiete. Daraus folgt, dass $3 |R| \leq 2 |E|$. Dies impliziert unter Ausnützung der Eulerschen Polyedersatz für planare Graphen ($|V| + |R| - |E| = 2$), dass

\[ \frac{2}{3} |E| \geq |R| = 2 - |V| + |E|, \]

also $|V| - 2 \geq \frac{1}{3} |E|$, was zu zeigen war. Zu 2: Wir beweisen die Behauptung durch eine Widerspruchsannahme. Angenommen, alle Knoten $v \in V$ würden einen Knotengrad größer gleich $6$ haben. Dann wäre

\[ 2 |E| = \sum_{v \in V} \deg(v) \geq 6 |V|, \]

also $|E| \geq 3 |V|$, was aber im Widerspruch zur Aussage 1 steht.

Der Fünffarbensatz & Applet

Es folgt also aus dem Eulerschen Polyedersatz für planare Graphen, dass jeder planare zusammenhängende Graph mindestens einen Knoten vom Kantengrad kleiner gleich als fünf besitzen muss. Die Planaritätseigenschaft und diese Aussage sind hierbei die “Hauptzutaten”, welche der nachfolgende Algorithmus (bzw. konstruktiver Beweis der Fünffäbrbarkeit eines beliebigen planaren Graphen $G$) ausnutzen wird. Ein Beweis/Konstruktionsbeschreibung findet sich auf Wikipedia.

Zur Bedienung des Applets:

• Analog zum Applet auf Was ist ein Graph?.
• Über den weiß/grauen Slider kann man die Konstruktion mitverfolgen.

FiveColoring.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)