Besitzt der folgende Graph eine planare Einbettung in die Ebene ℝ^{2}?

Question

Aufgabe:

Text erkannt:

Besitzt der folgende Graph eine planare Einbettung in die Ebene \( \mathbb{R}^{2} \) ?

Problem/Ansatz:

Ich bin mir nicht ganz sicher. Ich beziehe mich im folgenden auf die Eckenfärbung. Ich kann ihn zwar mit 4 Farben färben, sogar mit 3, und wenn der Graph planar ist, dann kann ich diesen mit maximal 4 Farben färben, aber ich finde keine Darstellung, wenn ich an ihm rumschiebe. Kann mir jemand helfen?

Comments

Der Graph enthält \( K_{3,3} \) als topologischen Minor und ist somit nach dem Satz von Kuratowski nicht planar.

---

Wie kommst du darauf?

---

Es gibt genau 6 Ecken mit Grad 3, das müssen wenn dann die Verzweigungsknoten sein. Kontrahiert man die restlichen Knoten, hat man direkt den K3,3

---

Ah vielen Dank. Das hat sehr geholfen

Answer 1

Der Graph enthält \(K_{3,3}\) als topologischen Minor und ist somit nach dem Satz von Kuratowski nicht planar.