nicht planaren graph zum planaren Graphen machen

Question

Der Graph K5 ist bekannt dafür, nicht planar zu sein. Zeige: Entfernt man eine beliebige Kante e aus dem K5, so ist der resultierende Graph K5 / {e} planar.

Ich weiß nicht wie ich da vorgehen soll :( würde mich um Hilfe seeehr freuen :)

Answer 1

Der Graph ist vollständig, also ist es gleich welche Kante entfernt wird. Zeichne den resultierenden Graphen so, dass sich keine Kante überschneidet.

Alternativ kannst du auch nachweisen, dass der resultierende Graph keinen Teilgraphen besitzt, der Unterteilungsgraph von K₅ oder K_3,3 ist. Ersteres kann wegen der Anzahl der Kanten nicht sein, letzteres nicht wegen Anzahl der Ecken. Nach dem Satz von Kuratowski ist der Graph dann planar.