5
$\begingroup$

This is related to a previous question, Robertson-Seymour fails for topological minor ordering? (I.e., subgraphs and subdivision), but is much simpler.

What is a simple example of two graphs $G$ and $H$ such that $G$ is a minor of $H$ but not a topological minor? This would help me understand the difference between the two concepts.

$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Consider the standard cube $Q^3$ on $8$ vertices as $H$. Choose as $G$ the wheel $W^4$ on $5$ vertices. See also the following picture:

enter image description here.

Then, $G$ is a minor of $H$ but not a topological minor.

$\endgroup$
4
  • $\begingroup$ Thanks! How do you see that $W^4$ is not a topological minor of $Q^3$? I can do it by case analysis but surely there is a shortcut ah-ah! way. $\endgroup$
    – phs
    Feb 22, 2015 at 12:52
  • 4
    $\begingroup$ When you move from a graph to its topological minor you suppress only vertices of degree $2$. Since the cube is $3$-regular (i.e. has only vertices of degree $3$), it follows that you cannot suppress any vertices and so cannot create any topological minor of it. $\endgroup$
    – Moritz
    Feb 22, 2015 at 13:03
  • $\begingroup$ Consider any cycle of more than $3$ vertices. Every cycle is $2$-regular, that is, you can suppress almost all vertices. This implies that the triangle $K^3$ is topological minor of every other cycle (I disregard loops and parallel edges which can be seen as cycles of length $1$ and $2$, respectively). $\endgroup$
    – Moritz
    Feb 22, 2015 at 13:05
  • 1
    $\begingroup$ @phs You can see that any subdivision of $W^4$ will contain a vertex of degree 4 (the central vertex). But you cannot find a subgraph of $Q^3$ that contains a vertex of degree 4. $\endgroup$
    – Picasso
    Feb 1, 2017 at 5:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .