Gibt es einen Baum, der kein planarer Graph ist?
Nein, Bäume sind planar. Das kann mit dem eulerschen Polyedersatz einsehen, denn Bäume sind (minimal) zusammenhängend. Es gibt in einem Baum mit \(n\) Knoten \(n-1\) Kanten und eine Fläche.
Der vollständige Graph K5 mit e = 5 Ecken hat k = 10 Kanten ist doch folglich nicht planar oder?
\(K_5\) ist zusammenhängend. Es müsste dann (das folgt aus dem eulerschen Poyledersatz) gelten, insofern \(K_5\) planar wäre, dass \(|E|\leq 3|V|-6\). Das ist aber mit \(|E|=10\) und \(|V|=5\) nicht erfüllt.
\(K_5\) und \(K_{3,3}\) sind in der Tat die mustergültigen nichtplanaren Graphen, die z. B. beim Satz von Kuratowski eine wichtige Rolle spielen.
