Showing non existence of topological minors in a graph

176 Views Asked by At

Recall that a subgraph $H$ of $G$ is called a topological minor if by only adding vertices, edges to $H$ and subdividing some edges of $H$ one can construct $G$. For small graphs, it is easy to show that $G$ has a given topological minor $H$. But how does one go to show non-existence of said minor?

A concrete example: Why does the $4\times 4$ lattice $G$ not have the complete bipartite $2,4$ graph $H$ as a topological minor? It is easy to see that the $5\times 5$ lattice does have $H$ as a special minor, but one runs out of space when restricted to the $4\times 4$ lattice. Is there a quick way to show non-existence, apart from running through every possible graph (and there are quite many of them) that can be constructed from $H$ given the previous operations?

A first elementary argument would be this: $H$ has 2 vertices of degree $4$ that do not connect, these vertices therefore must be in the diagonal of the $4\times 4$ lattice. This determines the location of the two vertices. But all the other vertices have degree $1$ and by adding edges this degree can be increased, so their location could be anything. How does one proceed then?

1

There are 1 best solutions below

0
On

The $4 \times 4$ lattice has $K_{2,4}$ as a topological minor. Suppose we label the vertices of $K_{2,4}$ as $\{x,y\}$ and $\{a,b,c,d\}$. The red edges of the drawing show a subdivision of $K_{2,4}$ as a subgraph of the $4 \times 4$ lattice.

enter image description here