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

646 Views Asked by At

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:

G

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

1

There are 1 best solutions below

3
On BEST ANSWER

Label your vertices as

    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---
     |                     |   |
     |                     |   |