Eulersche Polyedersatz für planare Graphen

Die Eulersche Polyederformel sagt für den Fall eines zusammenhängenden planaren Graphen $G = (V,E)$ aus, dass

\[ |V| + |R| - |E| = 2. \]

Hierbei ist $|V|$ die Anzahl der Knoten (Ecken), $|R|$ die Anzahl der Gebiete (Flächen/regions) und $|E|$ die Anzahl der Kanten von $G$. Falls $G$ “nur” planar ist (also aus mehreren Zusammenhangskomponenten besteht) lässt sich die obige Gleichung zu

\[ |V| + |R| - |E| = 1 + k \]

erweitern, wobei $k$ gleich der Anzahl der Zusammenhangskomponenten von $G$ ist.

Einen Beweis dieser Aussagen erhält man wie folgt: Sei $G$ ein planarer Graph. Betrachten wir zunächst den Fall, dass $G$ zusammenhängend ist. Wir werden $G$ nun, beginnend von einem beliebigen Startknoten aus (gesehen als Subgraph von $G$), anhand der nachfolgenden zwei Schritte rekonstruieren:

1. Hinzufügen eines Knotens der über eine neue Kante mit dem “alten” (Sub-)Graphen verbunden ist: In diesem Fall erhöht sich die Anzahl der Knoten und der Kanten jeweils um eins, und da $G$ planar ist, verändert sich die Anzahl der Gebiete nicht.
2. Hinzufügen einer neuen Kanten zwischen zwei bestehenden Ecken des “alten” (Sub-)Graphen: In diesem Fall erhöht sich die Anzahl der Kanten und der Gebiete um eins. Die Anzahl der Knoten bleibt gleich. Im Startfall besteht der konstruierte Subgraph von $G$ nur aus einem Knoten, wonach die erste Gleichung ($1$ Ecke plus $1$ Fläche (äußeres Gebiet) minus $0$ Kanten) offenbar erfüllt ist. Des Weiteren erhalten die obigen beiden Konstruktionsschritte die Gültigkeit der ersten Gleichung, womit die Aussage für zusammenhängende und planare $G$ bewiesen ist.

Falls $G$ aus mehreren Zusammenhangskomponenten besteht erhöht Schritt 1 beim Übergang zu einer neuen Zusammenhangskomponente die Anzahl der Ecken und die Anzahl der Zusammenhansgkomponenten um eins. Exakt dies wird von der zweiten Gleichung zusätzlich berücksichtigt.

Applet

Im nachfolgenden Applet kann man den konstruktiven Beweis am Beispiel eines (beliebigen) planaren Graphen mitverfolgen (Z.K. = Zusammenhangskomponente(n)).

Zur Bedienung des Applets:

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

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