Prove that $G$ contains a subdivision of $K_5$ or $K_{3,3}$ if and only if G contains a $K_5$ or $K_{3,3}$ minor

321 Views Asked by At

I'd like to try and prove the above theorem. It was covered during a class that I was not able to attend.

The forward direction is easy to prove I think.

Let's say that $G$ contains a subdivision of $K_5$. Let $\{a, b, c, d, e\}$ be the five branch vertices of $K_5$. Then along any path P from one branch vertex to another such that each internal vertex has a degree of 2, contract all but one of the edges. We are left with the $K_5$ graph, which is a minor of $K_5$.

A similar thing can be done if $G$ contains a subdivision of $K_{3,3}$.

So the forward direction is proven. I'm not sure how to prove the backwards direction. Would really appreciate the help. We have covered Wagner's theorem and Kuratowski's theorem.