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
    You really ought to label the vertices.2011-11-12
  • 0
    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}$.2011-11-12
  • 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
    Very nice. Thanks. I understand the reasoning behind finding the last subgraph (the one with cycle), but what about the first one?2011-11-13
  • 0
    Does it suffice for just one of the collapsable subgraphs to look like the last subgraph you drew?2011-11-13
  • 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 existing 4 connections, which is easy to collapse to a single degree-3 node in a topological minor.2011-11-13