# $K_5$ minor implies $K_5$ or $K_{3,3}$ topological minor

Problem. Let $G$ be a graph with a $K_5$ minor. Prove that $G$ contains either a $K_5$ or a $K_{3,3}$ topological minor.

I'm having a hard time believing this result. Consider the graph $G$ obtained from $K_5$ by replacing one of its vertices with a cycle of length 4:

Where is the $K_5$ or $K_{3,3}$ topological minor?

-
You really ought to label the vertices. – Will Jagy Nov 12 '11 at 23:36
I can see it. Take the top left node as the $1$ node, and the two bottom right nodes as $2$ and $3$. Take the top right node as $4$ and the two bottom left nodes $5$ and $6$. Take the node below $1$ and merge it with $1$. Do the same with the node below $4$. Then $1$, $2$ and $3$ are all having an edge going to $4$, $5$ and $6$, thus giving you a subgraph isomorphic to $K_{3,3}$. – Patrick Da Silva Nov 12 '11 at 23:41
I must admit I'm not familiar with the definitions of topological minor and graph theory stuff, but I thought that if I helped you "see" a $K_{3,3}$ in there that would be helpful. – Patrick Da Silva Nov 12 '11 at 23:45

    A----X
/|    |\
/ Y----B \
P__|____|__Q
|\_|_  _|_/|
\  |_><_|  /
\_C____Z_/


Then $(\{A,B,C\},\{X,Y,Z\})$ is $K_{3,3}$ with the two indirect edges $XQC$ and $APZ$.

Later: But Patrick's suggestion (in comments) of $(\{X,P,C\},\{A,Q,Z\})$ is better because it doesn't use the $YB$ edge. Then all you have to prove for the main problem is prove that each of the subgraphs that collapse to one of the vertices in $K_5$ (as a minor) must have one of the following as a topological minor (aka homeomorphic subgraph):

     |
|
-----O-----       or    ---O---O---
|                     |   |
|                     |   |

-
Very nice. Thanks. I understand the reasoning behind finding the last subgraph (the one with cycle), but what about the first one? – echoone Nov 13 '11 at 1:31
Does it suffice for just one of the collapsable subgraphs to look like the last subgraph you drew? – echoone Nov 13 '11 at 1:36
Note that my answer was in error when you first commented. I have corrected it. If all of the 5 components can reduce to a degree-4 node, you have $K_5$ as topological minor. Otherwise, at least one of them must have a topological minor of the second for I show. Let that be >A--X<, and use (XPC,AQZ) as $K_{3,3}$. Each of the nodes PQCZ will then need only three of their existing 4 connections, which is easy to collapse to a single degree-3 node in a topological minor. – Henning Makholm Nov 13 '11 at 1:37