Importance of max degree at most 3 in graph minors/topological minors

Question

I am looking at Lemma 1.2 in https://kam.mff.cuni.cz/~fiala/tw.pdf

So it's a well-known theorem that if $H$ is a minor of $G$ and $H$ has max degree at most 3 then $H$ is also a topological minor of $G$.

But I'm reading the proof now and I keep getting confused about when we actually use that the max degree is $\le 3$. I can think of a counterexample (take cube graph and contract an entire "face") but I don't get where it breaks the proof

Please can someone write out the proof of this theorem and highlight the part where we require the max degree be at most three?

Answer 1

In this proof, the overall idea of finding a subdivision (or topological minor) of $H$ in $G$, given that $H$ is a minor of $G$ is as follows:

1. Replace $G$ by the subgraph of $G$ from which we can get $H$ simply by contractions.
2. In this subgraph, for every vertex $u \in V(H)$, identify the set $f(u) \subseteq V(G)$ that "gets contracted to $u$". Each $f(u)$ is connected, and for every edge $uv \in E(H)$, there is an edge in $G$ between some vertex in $f(u)$ and $f(v)$.
3. For each edge $uv \in E(H)$, choose a particular edge between $f(u)$ and $f(v)$; mark that edge (which we call $f'(uv)$) and its endpoints for inclusion in what will become our subdivision of $H$.
4. In each $f(u)$, since it is connected, pick a minimal tree that connects all the marked vertices of $f(u)$.
5. Let $F$ be the subgraph of $G$ consisting of every tree picked in step 4 and every marked edge $f'(uv)$.

All of this can be done whether or not $H$ has maximum degree $3$. The place where the proof breaks down (which isn't spelled out in the source we're referencing) is the step where we look $F$, and declare that it's a subdivision of $H$!

Why is this the case? Well, I claim that if $H$ has maximum degree $3$, the minimal tree we find inside $f(u)$ in step $4$ will always contain a "central vertex" $u^*$ such that the paths from $u^*$ to the marked vertices do not intersect except at $u^*$. This is something we can think about case by case:

• If there are no marked vertices in $f(u)$ (which can happen when $u$ is an isolated vertex of $H$) then the minimal tree will just consist of a single vertex, which we call $u^*$.
• If there is only one marked vertex in $f(u)$, we call that vertex $u^*$ and call it a day.
• If there are two marked vertices in $f(u)$, our tree needs to contain a path between those two marked vertices, but by minimality it should just be that path. Usually, any vertex along the path can be chosen to be $u^*$. However, if one of the endpoints is "a marked vertex twice" (that is, it is an endpoint of $f'(uv)$ and $f'(uw)$ for different $uv, uw \in E(H)$) then we choose it to be $u^*$, so that we have two (trivial) paths from $u^*$ to $f'(uv)$ and $f'(uw)$ that do not intersect except at $u^*$.
• If there are three marked vertices in $f(u)$, then the minimal tree we find should have at most three leaves (any leaf that's not a marked vertex can be deleted). If it has two leaves, then choose the marked vertex that's not a leaf to be $u^*$. If it has three leaves, then it must have a vertex of degree $3$, and we choose that vertex to be $u^*$.

Now, for every edge $uv \in H$, $F$ will have a path from $u^*$ to the endpoint of $f'(uv)$ in $f(u)$ and a path from $v^*$ to the endpoint of $f'(uv)$ in $f(v)$. Together with $f'(uv)$ itself, we get a $u^* - v^*$ path in $F$. These paths are all internally vertex-disjoint, and so together, they form a subdivision of $H$.

---

So what if $H$ had a vertex $u$ with $\deg(u)>3$? In that case, the minimal tree we find in $f(u)$ might not have the right shape. We would like that minimal tree to be a "spider", consisting of a central vertex $u^*$ and paths radiating out to the marked vertex. But for trees with $4$ or more leaves, it's possible to have alternate shapes where this does not happen. For example, the minimal tree we find inside $f(u)$ could look like this (where 1, 2, 3, 4 are the marked vertices):

1          2
 \        /
  \      /
   *----*
  /      \
 /        \
3          4

Here, we cannot choose any central vertex to be $u^*$ and have four different paths to vertices 1 through 4, so the subgraph $F$ we construct is not a subdivision of $H$.