Die Eulersche Polyederformel

Für die Platonischen Körper gilt:

Körper	Ecken	Kanten	Flächen
Tetraeder	4	6	4
Kubus	8	12	6
Oktaeder	6	12	8
Dodekaeder	20	30	12
Ikosaeder	12	30	20

In allen fünf Fällen ergibt sich:

Ecken − Kanten + Flächen = 2

Diese Eulersche Polyederformel gilt nicht nur für die Platonischen Körper, sondern für alle Polyeder, die sich durch einen planaren Graphen darstellen lassen. Sie erscheint letztendlich sogar als eine Eigenschaft planarer Graphen, sodass wir sie auch Eulersche Graphenformel nennen könnten. Hierzu müssen wir einen Flächenbegriff für planare Graphen einführen.

Eine planare Darstellung eines Graphen unterteilt die Ebene in Flächen oder Gebiete. Dabei zählen wir stets die äußere unbeschränkte Fläche mit. Somit hat zum Beispiel ein Dreieck und allgemeiner jeder planar dargestellte graphentheoretische Kreis genau zwei Flächen. Jeder Fläche können wir die Kanten und Ecken des Graphen zuordnen, die an diese Fläche grenzen. Diese Zuordnung hängt von der planaren Darstellung ab. Für jede planare Darstellung gilt aber:

Grenzflächen von Brücken und Kreiskanten

(a)	Eine Brücke hat genau eine angrenzende Fläche, nämlich die umgebende äußere Fläche.

(b)	Eine Kreiskante besitzt genau zwei angrenzende Flächen (eine innere und die äußere Fläche oder zwei innere Flächen).

Wir verwenden diese anschaulichen Eigenschaften hier ohne Beweis. Ein strenger Beweis ist recht aufwendig, da gezeigt werden muss, dass eine geschlossene stetige überschneidungsfreie Kurve − ein deformierter Kreis − die Ebene in genau zwei Gebiete zerlegt, deren gemeinsamer Rand die Kurve ist (Jordanscher Kurvensatz).

Der gezeigte Graph hat 10 Ecken, 13 Kanten und 5 Flächen (vier innere, eine äußere). Die Brücke 28 grenzt wie jede Brücke nur an die äußere Fläche. Die Kreiskante 45 grenzt an zwei innere Flächen, die Kreiskante 57 an eine innere sowie die äußere Fläche.

Die angrenzenden Ecken einer inneren Fläche gehören stets einer gemeinsamen Komponente an. Die äußere Fläche besitzt dagegen mindestens eine angrenzende Ecke in jeder Komponente des Graphen.

Nach diesen Vorbereitungen können wir formulieren und beweisen:

Satz (Eulersche Polyederformel für planare Graphen)

Sei G = (E, K) ein planarer Graph mit genau c Zusammenhangskomponenten. Weiter seien e = |E|, k = |K| und f die Anzahl der Flächen in irgendeiner planaren Darstellung des Graphen. Dann ist f die Anzahl der Flächen jeder planaren Darstellung von G und es gilt

e − k + f = c + 1.(Eulersche Polyederformel)

Ist G zusammenhängend, so gilt speziell e − k + f = 2.

Beweis

Wir zeigen die Aussage durch Induktion nach k ≥ 0.

Induktionsanfang k = 0:

In diesem Fall ist e = c und f = 1, sodass

e − k + f = c + 1.

Induktionsschritt von k nach k + 1:

Sei G ein planarer Graph mit k + 1 Kanten. Wir betrachten eine beliebige planare Darstellung von G. Sei nun a*b* eine beliebige Kante von G, und sei G′ der Teilgraph von G, der durch Streichen von a*b* entsteht. Nach Induktionsvoraussetzung gilt

e − k + f ′ = c′ + 1

in der durch das Streichen von a*b* entstehenden planaren Darstellung von G′, wobei f ′ die Zahl der Flächen dieser Darstellung und c′ die Zahl der Zusammenhangskomponenten von G′ bezeichnet.

1. Fall: a*b* ist eine Brücke in G

In diesem Fall grenzt die Kante a*b* an genau eine Fläche von G. Das Entfernen von a*b* lässt die Zahl der Flächen unverändert, erhöht aber die Zahl der Zusammenhangskomponenten um 1. Damit ist f ′ = f und c′ = c + 1. Hieraus ergibt sich

e − (k + 1) + f = e − k + f ′ − 1 = c′ + 1 − 1 = c′ = c + 1.

2. Fall: a*b* ist keine Brücke in G

In diesem Fall grenzt die Kante a*b* als Kreiskante von G an genau zwei Flächen, die durch das Entfernen von a*b* zu einer Fläche von G′ werden. Da a*b* keine Brücke ist, gilt c′ = c. Folglich ist

e − (k + 1) + f = e − k + f − 1 = e − k + f′ = c′ + 1 = c + 1.

Damit ist die Polyederformel für eine beliebige planare Darstellung von G bewiesen. Da die Größen e, k, c unabhängig von der Darstellung sind, ist f = c + 1 − e + k die Zahl der Flächen jeder planaren Darstellung.

Da jedes konvexe dreidimensionale Polyeder zu einem planaren Graphen führt, der mit dem Polyeder in den Größen e, k und f übereinstimmt, erhalten wir die namensgebende Version der Formel:

Korollar (Eulersche Polyederformel für Polyeder)

Für jedes konvexe Polyeder des dreidimensionalen Raumes gilt die Eulersche Polyederformel. Allgemeiner gilt die Formel für alle Polyeder, die durch einen planaren Graph dargestellt werden können.

Die Eulersche Polyederformel hat zahlreiche Anwendungen in der Graphentheorie und Geometrie. Wir betrachten einige davon.