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

enter image description here

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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.