If $H$ has maximum vertex degree at most $3$ and is a minor of $G$, then $H$ is a topological minor of $G$.

1.8k Views Asked by At

If $H$ has maximum vertex degree at most $3$ (so $\Delta(H)\leq 3$) and $H$ is a minor of $G$, then $H$ is a topological minor of $G$.

The converse follows by definition. However, most sources state this proposition without a proof. Any help is greatly appreciated.

1

There are 1 best solutions below

5
On

If $H$ is a minor, then there is some sequence of edge/vertex deletions and edge contractions that will take us from $G$ to $H$.

On the other hand, to show that $H$ is a topological minor, we need to show that there is a subdivision of $H$ that is isomorphic to a subgraph of $G$. This means that $H$ can be obtained from $G$ by a sequence of edge/vertex deletions, and then contraction of edges, but only contracting edges of the form $(u,v)$ where one of the vertices $u$ or $v$ has degree exactly $2$.

When forming $H$ from $G$ as a (regular) minor, we can do this so as to perform all edge/vertex deletions first to obtain a graph $G^\prime$. Notice that while we might want to later contract an edge $(x,y)$ where one of $x$ and $y$ have degree $1$, we can convert this operation to just deleting that degree $1$ vertex, and so we do this here instead.

In other words, we can first construct a graph $G^\prime$ by vertex/edge deletions that contains $H$ as a minor, such that $H$ is obtained from $G^\prime$ by contracting edges $(u,v)$ where both $u,v$ have degree at least $2$.

If $G^\prime=H$, then we're done. Otherwise we need to perform some edge contractions. The key point here is that if $\Delta(H)\leq 3$, then we can never contract an edge of the form $(u,v)$ where both $u$ and $v$ have degree at least $3$. This is because otherwise we would create a vertex of degree at least $4$ at this step, and since we are only now contracting edges joining two vertices of degree at least $2$, $H$ would then have a vertex of degree $4$.

So in forming $H$ from $G^\prime$, we are only contracting edges joining two vertices with at least one of the two vertices having degree exactly $2$. Thus $H$ is a topological minor.