# Showing a non-planar graph has a $K_5$ or $K_{3,3}$ subdivision

[This is exam review] I have the following graph:

Question: I need to prove it is not planar by showing a subdivision of $$K_5$$ or $$K_{3,3}$$ exists in the graph (to use Kuratowski’s Theorem). I understand the concept of a subdivision (ie. adding some vertices between two vertices to make new edges), but I have no idea how to apply it to get a subdivision of $$K_5$$ or $$K_{3,3}$$.

The definition of a subdivision from my textbook: An edge subdivision of a graph G is obtained by applying the following operation, independently, to each edge of G: replace the edge by a path of length 1 or more; if the path has length $$m > 1$$, then there are $$m − 1$$ new vertices and $$m − 1$$ new edges created; if the path has length $$m = 1$$, then the edge is unchanged.

A subdivision of $$K_5$$ will have $$5$$ vertices of degree $$4$$, which you don't have, so you're looking for a subdivision of $$K_{3,3}$$. Get rid of the vertices of degree $$2$$, replacing the edges $$ef,fg$$ with $$eg$$ and $$ha,ab$$ with $$hb$$. Finally, remove the edge $$bd$$. You now have a $$K_{3,3}$$ with $$b,d,g$$ on one side and $$c,e,h$$ on the other side. If we call your original graph $$G$$, then the subgraph $$G-bd$$ is a subdivision of this $$K_{3,3}$$.