<p>$\mathcal{Z}(H)$ is the set of graphs obtained from $H$ by splitting vertices of degree $&gt;3$ (the reverse operation to contracting an edge between two vertices, both of degree $\ge 3$, and where the contracted edge is not in any triangle). So (at least when all graphs are assumed to be finite) $\mathcal{Z}(H)=\{H\}$ iff $H$ has maximum degree 3.</p>

CC BY-SA 3.0
2017-09-13T20:57:30.727Z
2017-09-13T20:57:30.727Z
David Eppstein
<p>It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$.</p>

<p>Moreover, a graph $G$ has one of $K_{3,3}$ or $K_5$ as minor if and only if it has one of $K_{3,3}$ or $K_5$ as topological minor.</p>

<p>Furthermore, in a <a href="http://cgm.cs.mcgill.ca/~breed/COMP599/shell.pdf" rel="noreferrer">writeup</a> by Bruce Reed i saw the following theorem.</p>

<p>Theorem: For any graph $H$, there is a finite set $\mathcal{Z}(H)$ of graphs such that $G$ has $H$ as a minor if and only if $G$ contains a subdivision of some element of $\mathcal{Z}(H)$.</p>

<p>So, my question is under what condition $\mathcal{Z}(H)=\{H\}$ or in other words, what properties must $H$ have so that $\mathcal{Z}(H)=\{H\}$ ?</p>

CC BY-SA 3.0
2017-09-13T10:42:57.447Z
This is the Robertson-Seymour theorem; maybe better understanding of the (very long) proof may help to answer.
Mikhail Tikhomirov
<graph-theory><graph-minor>
Minor and subdivision
Dibyayan
# Minor and subdivision

(Asked by: username_0 on 2017-09-13)

It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$.

Moreover, a graph $G$ has one of $K\_{3,3}$ or $K\_5$ as minor if and only if it has one of $K\_{3,3}$ or $K\_5$ as topological minor.

Furthermore, in a [writeup](http://cgm.cs.mcgill.ca/~breed/COMP599/shell.pdf) by Bruce Reed i saw the following theorem.

Theorem: For any graph $H$, there is a finite set $\mathcal{Z}(H)$ of graphs such that $G$ has $H$ as a minor if and only if $G$ contains a subdivision of some element of $\mathcal{Z}(H)$.

So, my question is under what condition $\mathcal{Z}(H)=\{H\}$ or in other words, what properties must $H$ have so that $\mathcal{Z}(H)=\{H\}$ ?

**Tags:** graph-theory, graph-minor
> **Comments:**
> **username_1**: This is the Robertson-Seymour theorem; maybe better understanding of the (very long) proof may help to answer.  

---

## 1 answers

### Answer by username_2 on 2017-09-13. Score: 4 | Accepted answer

$\mathcal{Z}(H)$ is the set of graphs obtained from $H$ by splitting vertices of degree $>3$ (the reverse operation to contracting an edge between two vertices, both of degree $\ge 3$, and where the contracted edge is not in any triangle). So (at least when all graphs are assumed to be finite) $\mathcal{Z}(H)=\{H\}$ iff $H$ has maximum degree 3.


---

