Die Euler-Formel für Planare Graphen
Ein planarer Graph ist ein Graph der so in die Ebene gezeichnet werden kann, dass sich keine zwei Kanten überschneiden. Die Kanten dürfen dabei durchaus beliebige Jordankurven sein. Neben den Knoten und Kanten, die den Graphen definieren, lässt sich für planare Graphen auch der Begriff der Facette definieren. Eine Facette ist ein durch Kanten begrenztes Gebiet in der Zeichnung des Graphen. Der Bereich außerhalb des Graphen zählt auch als Facette, und wird meist als äußere Facette bezeichnet. Beispielsweise lässt sich der dreidimensionale Würfel so in die Ebene einbetten, dass sich keine Kanten überkreuzen.
Man zählt 8 Knoten, 12 Kanten und 6 Facetten.
Die Eulersche Formel bringt nun für beliebige planare Graphen die Anzahl der Facetten, Kanten und Knoten in eine mathematische Beziehung. Sie besagt, dass für einen planaren und zusammenhängenden Graphen mit Knoten, Kanten und Facetten gilt:
Für diese schlichte Formel gibt es einen äußerst eleganten und kurzen Beweis, der im Gegensatz zum kanonischen Beweis, ganz ohne Induktion auskommt!
Beweis
Wir betrachten eine beliebige Einbettung des Graphen in der Ebene. Ist zusammenhängend, so gilt das auch für den dualen Graphen . Nach dem Satz von Jordan, induziert eine Menge von Kreisen in einen Schnitt in und umgekehrt ein Schnitt in eine Menge von Kreisen in .
Wir betrachten nun einen aufspannenden Baum in , sowie den dualen Graphen , also zu dem durch die Nichtbaumkanten induzierten Subgraph in . Natürlich ist ein Subgraph von . Weiterhin entspricht jede Kante in einer Nichtbaumkante in , so dass gilt. Aus dem Satz von Jordan lässt sich außerdem folgern, dass sogar ein aufspannender Baum in ist, was gleichbedeutend mit ist.
Da ein Baum mit Knoten genau Kanten enthält, folgt aus den obigen Beobachtungen
Fertig!