Planarer Graph/Eulersche Polyederformel/Abschätzungen/Fakt/Beweis

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.

Zur bewiesenen Aussage