Determining if a graph is planar and if so draw or disprove with Kuratowski's Theorem

537 Views Asked by At

This is a practice exercise for in my text that even my professor was having trouble explaining to me. The instructions are in the title.

Here is an image of the graph: enter image description here

I believe this graph is not planar. My professor stated that it was impossible to know a graph is not planar unless you can find the subgraph K5 or K3,3. I think I can collapse g and c, but I still don't think that will give me the correct graph. Is there something I am missing or is it just planar?

1

There are 1 best solutions below

3
On

Vertices $b,c,f$ are all adjacent to $a,d,e$ except for $c$ to $a$, for which you can go via $g$, and $c$ to $d$, for which go via $h$. So the graph contains a subgraph which is homeomorphic to (I think this is the same as what you mean by "can be collapsed to") $K_{3,3}$, and so the graph is not planar.

If I was any good at posting diagrams this would be more clear, but I'm sure you can manage the diagrams for yourself.