Planarer Graph/Eulersche Polyederformel/Fakt/Beweis/Aufgabe/Lösung

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$.

Zur gelösten Aufgabe