Planarer Graph/Eulersche Polyederformel/Abschätzungen/Fakt

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.

Zum Beweis, Alternativen Beweis erstellen