Is graph Planar?

571 Views Asked by At

Hello i have the following graph:

diagram

I'm trying to figure out if it's planar or not. I think it is not planar but i can't find a subgraph that is a subdivision of K3,3 or K5 , to use the kuratowski theorem.

p.s. i can only redraw the graph to show that it is planar or prove that its not planar with kuratowski theorem. NO other methods allowed.

3

There are 3 best solutions below

3
On BEST ANSWER

Delete the edges $\{EG\}$ and $\{FH\}$. Then you can do the following:

enter image description here

0
On

Try $K_{3,3}$ with BHI as one of the sides.

6
On

Does the following regrouping help:

enter image description here

Yes it does! If the original graph were planar, you could collapse any two connected vertices into one and still the graph would remain planar. But this way you would get that the above grouped graph, which is $K_{3,3}$, is planar: a contradiction.