# Graph theory: minors vs topological minors

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.

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:
Then, $G$ is a minor of $H$ but not a topological minor.
• 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.
• 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. Commented Feb 22, 2015 at 13:03
• 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). Commented Feb 22, 2015 at 13:05
• @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. Commented Feb 1, 2017 at 5:13