Anwendungen der Polyederformel
Wir zeigen zunächst einige nützliche Abschätzungen für planare Graphen.
Satz (Größenabschätzungen für planare Graphen)
Sei G = (E, K) planar mit k ≥ 3. Dann gilt 3f ≤ 2k und k ≤ 3(e − 2). Grenzen allgemeiner an jede Fläche von G mindestens m Kanten, so gilt mf ≤ 2k und (m − 2) k ≤ m(e − 2).
Beweis
Wir betrachten eine planare Darstellung von G und ordnen jeder Fläche drei Kanten zu, die an diese Fläche grenzen. Da jede Kante höchstens an zwei Flächen grenzt, wird jede Kante höchstens zweimal verwendet. Damit ist 3f ≤ 2k. Aus der Eulerschen Polyederformel ergibt sich
k = f + e − c − 1 ≤ f + e − 2 ≤ 2/3 k + e − 2,
sodass k ≤ 3(e − 2). Die zweite Aussage ergibt sich analog mit m statt 3 an jede Fläche angrenzenden Kanten.
Die verallgemeinerte Abschätzung gilt für ein m > 3, falls k ≥ m und G keine Kreise mit weniger als m Ecken enthält. Insbesondere ist 2k ≤ 4(e − 2), falls k ≥ 4 und G keine Dreiecke enthält.
Mit Hilfe der Größenabschätzungen lässt sich manchmal nachweisen, dass ein bestimmter Graphen nicht planar ist. Die Graphen K5 und K3, 3 sind geeignet:
Korollar (Nichtplanarität des K5 und K3, 3)
Die Graphen K5 und K3, 3 sind nicht planar.
Beweis
Der K5 ist nicht planar, da sonst 15 = k ≤ 3(e − 2) = 9.
Für den K3, 3 gilt die Abschätzung mit m = 4, da K3, 3 keine Dreiecke enthält. Damit ist der K3, 3 nicht planar, da sonst 18 = 2k ≤ 4(e − 2) = 16.
Eine überraschende und wichtige Konsequenz der Größenabschätzung ist:
Korollar (Grad-Fünf-Eigenschaft planarer Graphen)
Sei G = (E, K) ein planarer Graph. Dann existiert ein a ∈ E mit d(a) ≤ 5.
Beweis
Nach der Gradformel und der Größenabschätzung gilt
(+) ∑a ∈ E d(a) = 2k = 6(e − 2) < 6e.
Damit muss es mindestens eine Ecke geben, deren Grad kleiner als 6 ist.
Das Ergebnis ist optimal in dem Sinne, dass es einen planaren Graphen gibt, dessen Grade alle gleich 5 sind: Der Ikosaedergraph ist ein Beispiel. Genauer zeigt die Abschätzung (+), dass der Durchschnittsgrad (∑a ∈ E d(a))/n eines planaren Graphen kleiner als 6 ist. Ecken mit einem großen Grad werden in einem planaren Graphen durch Ecken mit einem kleinen Grad ausgeglichen.
Mit Hilfe der Polyederformel können wir zeigen, dass es außer den fünf Platonischen Körpern keine weiteren regelmäßigen konvexen Polyeder gibt. Das wunderschöne Argument ist ein Klassiker der Mathematik.
Satz (Klassifikation regelmäßiger Polyeder)
Sei P ein regelmäßiges Polyeder mit e Ecken, k Kanten und f Flächen. Es gelte e − k + f = 2. Weiter seien n ≥ 3 die Anzahl der Kanten einer Fläche und d ≥ 3 der gemeinsame Grad der Ecken. Dann gilt:
(a) | nf = 2k, de = 2k. |
(b) | 1/n + 1/d = 1/2 + 1/k. |
(c) | Aufgefasst als Gleichung in den Variablen n, d, k hat (b) genau die folgenden Lösungen in den natürlichen Zahlen mit n, d ≥ 3: (3, 3, 6), (3, 4, 12), (3, 5, 30), (4, 3, 12), (5, 3, 30). |
Beweis
Jede Kante ist an genau zwei Flächen beteiligt, sodass nf = 2k. Ebenso ist jede Kante an genau zwei Ecken beteiligt, sodass de = 2k (vgl. die Gradformel). Nach der Polyederformel gilt f + e = k + 2, sodass
2kn + 2kd = k + 2.
Division durch 2k zeigt (b). Seien nun n, d, k natürliche Zahlen mit n, d ≥ 3 derart, dass (b) erfüllt ist. Dann gilt n = 3 oder d = 3, da andernfalls
1n + 1d ≤ 14 + 14 < 12 + 1k.
Ist n = 3, so ist d ≤ 5, da andernfalls
1n + 1d ≤ 13 + 16 < 12 + 1k.
Analog folgt aus d = 3, dass n ≤ 5. Damit ergeben sich für (n, d) die fünf Möglichkeiten (3, 3), (3, 4), (3, 5), (4, 3), (5, 3). Da k durch die beiden Werte n und d eindeutig bestimmt ist, gibt es also höchstens fünf Lösungen. Einsetzen zeigt, dass die fünf Tripel tatsächlich Lösungen sind.
Die Lösungen entsprechen in der angegebenen Reihenfolge dem Tetraeder, Oktaeder, Ikosaeder, Kubus und Dodekaeder.