How to find $ K_{3,3}$ or $ K_{5}$ in graph

112 Views Asked by At

Hey I am supposed to decide if the following graph is a planar graph. enter image description here

I know that necessary and sufficient condition for the graph not to be planar, is to find $ K_{3,3}$ or $K_{5}$. But somehow I am lost and I do not know, how to do it.

Can anyone please help me?

2

There are 2 best solutions below

5
On BEST ANSWER

This graph is not planar.

By contracting the edges $(a,b),(j,a),(e,f),(f,g)$ You get $K_{3,3}$ as a minor, where $A:= \{a,d,h\}, B:=\{c,f,i\}$ is a partition.

1
On

If you form cliques $A=(abj)$ and $F=(feg)$, then you can see that the following partition: $Adh,Fci$ is complete.

In other words, you can redraw it like this: enter image description here