Planar graph or not (Kuratowski's Theorem)

729 Views Asked by At

Graph planar or not

So the question is whether the graph given is planar or not. After some trial and error I think it is NOT planar, so I want to prove it using Kuratowski's Theorem but I couldn't break it down to $K_5$ or $K_{3,3}$. Would appreciate any help on this!

Also in general, is there any strategy that we can use when trying to apply Kuratowski's Theorem? Or any thing that can help to determine whether we should aim for $K_5$ or $K_{3,3}$? Or is it just purely trial and error? I got so frustrated when I could not figure it out.

1

There are 1 best solutions below

1
On BEST ANSWER

Remove the edge $BD$ and suppress vertices $B,D$. The original graph thus contains a subdivision of this resulting graph, which is isomorphic to $K_{3,3}$, so the original graph is not planar.