# Minor and subdivision

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 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\}$ ?

• This is the Robertson-Seymour theorem; maybe better understanding of the (very long) proof may help to answer. Sep 13 '17 at 10:42

$\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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9308773,"math_prob":0.99995494,"size":686,"snap":"2021-43-2021-49","text_gpt3_token_len":224,"char_repetition_ratio":0.13929619,"word_repetition_ratio":0.064,"special_character_ratio":0.32798833,"punctuation_ratio":0.08974359,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000068,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-12-05T05:36:41Z\",\"WARC-Record-ID\":\"<urn:uuid:c064d880-7947-45e2-8eaa-1cf9e4068a86>\",\"Content-Length\":\"134496\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:8bd431be-ac6a-43e8-96b0-8e7f10643a75>\",\"WARC-Concurrent-To\":\"<urn:uuid:6c8240ec-bec0-4ad6-be89-5df6f9adfb70>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://cstheory.stackexchange.com/questions/39074/minor-and-subdivision\",\"WARC-Payload-Digest\":\"sha1:ZG24TIM7NPDUS2PTMI55DLHTISSULNB3\",\"WARC-Block-Digest\":\"sha1:QG4I7E5HJNUU6V4AKEQW5OGZ5OPSEEWM\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964363135.71_warc_CC-MAIN-20211205035505-20211205065505-00539.warc.gz\"}"}