$K_5$ minor implies $K_{3,3}$ subdivision, given 3-connected.

819 Views Asked by At

The question is: Let $G$ be a 3-connected graph not isomorphic to $K_5$, and to prove if it has no subgraph isomorphic to a subdivision of $K_{3,3}$ then $G$ is planar.

We can use the conclusion that if a graph $G$ does not contain $K_5$ or $K_{3,3}$ minor then it is planar. Obviously $K_{3,3}$ subdivision implies $K_{3,3}$ minor. So the point is to show that there is no $K_5$ minor. Or equivalently to show a $K_5$ minor could implies a $K_{3,3}$ subdivision.

Since 3-connected is givien, I am thinking of builing a graph of 6 vertices that contains $K_5$ minor. So then the minimal construction should be a $K_4$ (ABCD) and two more vertices (EF) with EF connected, and WLOG E connected to A and B, F connected to C and D. ABCDEF contains a $K_{3,3}$ subdivision.

I am not sure if this is the right way to think of the problem, and whether my construction is the only case to discuss.