Planarer Graph/Eulersche Polyederformel/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Wir führen Induktion über die Anzahl der Gebiete. Bei liegt ein Baum vor und nach Fakt ist

Sei die Aussage nun für einen jeden planaren Graphen mit Gebieten bewiesen und sei ein zusammenhängender planarer Graph mit Gebieten. Es ist dann kein Baum und besitzt daher einen Zykel und damit auch einen Kreis, sagen wir . Bei der Herausnahme der Kante bleibt der Graph zusammenhängend und planar. Die Anzahl der Knoten bleibt gleich, die Anzahl der Kanten reduziert sich um und die beiden durch die Kante begrenzten Gebiete werden zu einem Gebiet vereinigt, die anderen Gebiete ändern sich nicht. Insgesamt reduziert sich also die Anzahl der Gebiete um . 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 , deshalb ist die Wechselsumme von ebenfalls gleich .