Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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---
     |                     |   |
     |                     |   |
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.