Eulerscher Satz

Äquivalenz von Graphen / ebene Graphen

Ein zusammenhängender Graph heißt eben, falls sich keine Kanten kreuzen.

Zwei Graphen $G=\left(E,K\right)$ und $G'=\left(E',K'\right)$ heißen äquivalent, falls es eine bijektive Abbildung $\varphi:E\rightarrow E'$ gibt, so dass $\left\{ v,w\right\}$ eine Kante von $G$ ist, genau dann wenn $\left\{ \varphi\left(v\right),\varphi\left(w\right)\right\}$ eine Kante von $G'$ ist.

Ein Graph, der zu einem ebenen Graphen äquivalent ist, heißt plättbar.

Eulerscher Satz

In einem Graphen mit $e$ Ecken, $k$ Kanten und $f$ Flächen (von den Kanten abgetrennt) gilt stets

$$e-k+f=2$$

• Maximale Kantenanzahl bei einem plättbaren Graphen mit $n$ ($\geq3$) Ecken.
  $$k\left(n\right)=3\left(n-2\right)$$

Satz von Kuratowski

Ein Graph ist genau dann nicht plättbar, wenn er $V_{5}$ oder $GEW$ als Teilgraphen enthält.

• Der $GEW$-Graph (der vollständige bipartite $3$-Graph, $G_{3,3}$) ist nicht plättbar
  • Problem 3 Häuser mit 3 Versorgern (Gaß, Elektrizität, Wasser) kreuzungsfrei zu verbinden.
• $V_{5}$ ist nicht plättbar