Ungerichteter Graph/Planar/Eulerscher Polyederformel/Textabschnitt

Satz

Es sei ${}G$ ein zusammenhängender planarer Graph mit ${}n$ Knotenpunkten, ${}m$ Kanten und ${}g$ Gebieten.

Dann gilt die eulersche Polyederformel

${}n-m+g=2\,.$

Beweis

Wir führen Induktion über die Anzahl ${}g$ der Gebiete. Bei ${}g=1$ liegt ein Baum vor und nach Fakt ist

${}n-m+1=n-(n-1)+1=2\,.$

Es sei die Aussage nun für einen jeden planaren Graphen mit ${}g$ Gebieten bewiesen und sei ${}G$ ein zusammenhängender planarer Graph mit ${}g+1$ Gebieten. Es ist dann ${}G$ kein Baum und besitzt daher einen Zykel und damit auch einen Kreis, sagen wir ${}v_{1}\sim v_{2}\sim \ldots \sim v_{r}$. Bei der Herausnahme der Kante ${}v_{1}v_{2}$ bleibt der Graph zusammenhängend und planar. Die Anzahl der Knoten bleibt gleich, die Anzahl der Kanten reduziert sich um ${}1$ und die beiden durch die Kante ${}v_{1}v_{2}$ begrenzten Gebiete werden zu einem Gebiet vereinigt, die anderen Gebiete ändern sich nicht. Insgesamt reduziert sich also die Anzahl der Gebiete um ${}1$. Da die Anzahl der Kanten und der Gebiete mit unterschiedlichem Vorzeichen in die Wechselsumme eingeht, ändert sich diese bei Herausnahme der Kante nicht. Nach Induktionsvoraussetzung ist die Wechselsumme des reduzierten Graphen gleich ${}2$, deshalb ist die Wechselsumme von ${}G$ ebenfalls gleich ${}2$.

$\Box$

Korollar

Zu einem zusammenhängenden planaren Graphen

ist die Anzahl der Gebiete unabhängig von der ebenen Realisierung.

Beweis

Dies folgt unmittelbar aus Fakt.

$\Box$

Korollar

Für einen zusammenhängenden planaren Graphen mit ${}n\geq 3$ Knoten und ${}m$ Kanten gelten die folgenden Gesetzmäßigkeiten.

1. Es ist

   ${}m\leq 3n-6\,$

2. ${}G$ besitzt einen Knoten, dessen Grad höchstens ${}5$ ist.

Beweis

(1). Es sei ${}g$ die Anzahl der Gebiete. Zu jedem Gebiet ${}G$ sei ${}E(G)$ die Menge der das Gebiet begrenzenden Kanten. Da jede Kante an maximal zwei Gebieten beteiligt ist und da jedes Gebiet (wegen der Voraussetzung, dass es zumindest drei Knoten und dann auch drei Kanten gibt) zumindest drei begrenzende Kanten besitzt, gilt

${}2m\geq \sum _{G{\text{ Gebiet}}}{\#\left(E(G)\right)}\geq 3g\,.$

Mit der eulerschen Polyederformel gilt daher

${}2m\geq 3(2-n+m)\,$

und somit

${}m\leq 3n-6\,.$

(2). Nehmen wir an, dass sämtliche Knoten einen Grad ${}\geq 6$ haben. Dann ist die Summe über alle Knotengrade zumindest ${}6n$. Nach Fakt ist daher ${}2m\geq 6n$, was der Eigenschaft (1) widerspricht.

$\Box$

Beispiel

Der vollständige Graph ${}K_{5}$ besitzt ${}5$ Knoten und ${}{\binom {5}{2}}=10$ Kanten. Nach der Abschätzung aus Fakt  (1) kann er also nicht planar sein.

Beispiel

Der vollständige bipartite Graph ${}K_{3,3}$ ist nicht planar. Er besitzt ${}6$ Knotenpunkte und ${}9$ Kanten. Wenn er planar wäre, so müsste es nach der eulerschen Polyederformel ${}5$ Gebiete geben. Jedes dieser Gebiete wird durch einen Kreis berandet, und diese haben nach Fakt eine gerade Länge. Deshalb liegen an jedes Gebiet zumindest ${}4$ Kanten an. Da jede Kante nur an ${}2$ Gebieten beteiligt ist, braucht man zumindest ${}10$ Kanten, ein Widerspruch.