2
$\begingroup$

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?

  • 0
    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.2011-11-12

1 Answers 1

3

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---      |                     |   |      |                     |   | 
  • 0
    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 e$x$isting 4 connections, which is easy to collapse to a single degree-3 node in a topological minor.2011-11-13