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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

(1). Es sei die Anzahl der Gebiete. Zu jedem Gebiet sei 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

Mit der eulerschen Polyederformel gilt daher

und somit

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