Determinar si un gráfico es plano y, en caso afirmativo, dibujar o refutar con el Teorema de Kuratowski

Question

Se trata de un ejercicio práctico de mi texto que incluso mi profesor tenía problemas para explicarme. Las instrucciones están en el título.

Aquí hay una imagen del gráfico:

Creo que este gráfico no es planar. Mi profesor dijo que era imposible saber que un gráfico no es plano a menos que puedas encontrar el subgrafo K5 o K3,3. Creo que puedo colapsar g y c, pero todavía no creo que eso me dé el gráfico correcto. ¿Hay algo que se me escapa o es simplemente planar?

Answer 1

Vértices $b,c,f$ son todos adyacentes a $a,d,e$ excepto en el caso de $c$ a $a$ para lo cual puede ir a través de $g$ y $c$ a $d$ para lo cual hay que pasar por $h$ . Así que el gráfico contiene un subgrafo que es homeomorfo a (Creo que esto es lo mismo que lo que quieres decir con "se puede colapsar a") $K_{3,3}$ y, por tanto, el gráfico no es plano.

Si fuera bueno publicando diagramas esto sería más claro, pero estoy seguro de que puedes manejar los diagramas por ti mismo.