<blockquote>
  <p>If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.</p>
</blockquote>

<p>Since $G$ is a minor of $H$, $G$ can be obtained from $H$ by deleting edges, isolated vertices and performing edge contractions. It's also easy to show that we can insist that the subgraph operations are done first, i.e., we can first perform all the edge and vertex deletions and then perform all the edge contractions. Moreover, let us restrict the definition of "edge contraction" to disallow contracting edges where one of the vertices has degree 1. Contracting such an edge is the same as deleting it, so this will not change the definition of graph minors.</p>

<p>Let $H&#39;$ be the graph obtained from $H$ by performing all the edge/vertex deletions first. $H&#39;$ still contains $G$ as a minor. If we show that $H&#39;$ contains $G$ as a topological minor then we're done, since the definition of topological minor also allows edge/vertex deletions.</p>

<p>Since $G$ can be obtained from $H&#39;$ by edge contraction only, $H&#39;$ and all intermediate graphs must have maximum degree 3 since there is no way to decrease the maximum degree of a graph by performing an edge contraction. (This would have been possible if we had allowed the contraction of edges incident on a vertex of degree 1.)</p>

<p>So consider any step in the conversion of $H&#39;$ to $G$. The only types of edges we can contract are those with both degree-2 vertices or one degree-2 vertex and one degree-3 vertex. (All other combinations don't work. For example, edges with two degree-3 vertices will give rise to a vertex of degree 4 when contracted.)</p>

<p>And now we're done, since if $H_1$ is obtained from $H_2$ by contracting an edge with two degree-2 vertices, then $H_2$ can be obtained from $H_1$ by performing edge subdivision on that edge. Similarly for an edge with one degree-3 vertex and one degree-2 vertex. Thus $H&#39;$ can be obtained from $G$ by performing edge subdivisions only, which means $G$ is a topological minor of $H&#39;$ and thus $H$.</p>

<blockquote>
  <p>If $G$ is a path or a subdivision of a claw and is a minor of $H$ then $G$ is a subgraph of $H$</p>
</blockquote>

<p>This is easy to show once we have the previous result. Since paths and subdivisions of claws have maximum degree 3, if $G$ is a minor of $H$ it is also a topological minor of $H$. This means there is a subgraph of $H$ that can be obtained from $G$ by only performing edge subdivisions. Now it's easy to show by induction that every edge subdivision of a path or subdivision of a claw leads to a graph which contains the original as a subgraph. For example, subdividing a path of length k leads to a path of length k+1, which contains the path of length k as a subgraph. Similarly for subdivisions of a claw.</p>

<p>We also needed this result for a paper once, so we included a short proof in our paper. You can find the result in <a href="http://arxiv.org/abs/1011.1443">Quantum query complexity of minor-closed graph properties</a>. It's mentioned on page 13. However, this fact is hidden away in the proof of something else and isn't stated explicitly as a theorem.</p>

<p>What's also interesting is that there is a converse to this theorem:</p>

<blockquote>
  <p>The only graphs $G$ for which containing $G$ as a minor is equivalent to containing $G$ as a subgraph are those in which each connected component is a path or a subdivision of a claw.</p>
</blockquote>

CC BY-SA 3.0
2011-07-11T17:03:56.293Z
Thanks. If you happen to stumble on a published citation for these results, I'd still like it, but this is stellar.
Eli
CC BY-SA 3.0
2011-07-25T12:57:50.543Z
This answer is now [featured](http://cstheory.blogoverflow.com/2011/07/an-original-proof-of-a-folk-theorem/) on the community blog.
Aaron Sterling
CC BY-SA 3.0
2013-12-29T23:45:50.190Z
Good answer, but I think that your technique of disallowing degree-1 contractions has a flaw. For example, consider G = K_4 minus any edge. Contracting along the two vertices of degree 3 in G will produce the path graph P_3, with maximal degree 2. Instead, if you disallow any contractions on an edge which would be equivalent to some deletion, the proof should go through. Formally, you forbid any contraction between vertex x and y if gamma(x) \ {y} = gamma(y) \ x. It is easily shown that any contraction not violating this constraint will result in a new vertex of non-decreased degree.
RussellStewart
CC BY-SA 3.0
2014-01-08T03:14:36.007Z
@user2237635: You're right, thanks.
Robin Kothari
CC BY-SA 3.0
2011-07-11T14:34:09.753Z
2011-07-12T00:56:11.180Z
2011-07-12T00:56:11.180Z
Robin Kothari
<p>If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.</p>

<p>Wikipedia cites this result from Diestel's "Graph Theory". It's listed as Prop 1.7.4 in the latest version of the book. The book lacks proof or citation.</p>

<p>Are the whereabouts known for an (original) proof of this?</p>

<p>Furthermore, is there a reference proving that if $G$ is a path or a subdivision of a claw and is a minor of $H$ then $G$ is a subgraph of $H$? It's mentioned <a href="https://mathoverflow.net/questions/34060/when-does-graph-minor-containment-imply-subgraph-containment">here</a> briefly but lacks reference.</p>

CC BY-SA 3.0
2011-07-09T16:27:50.303Z
The book is available at http://diestel-graph-theory.com/
Alexander Langer
CC BY-SA 3.0
2011-07-09T19:43:10.557Z
Thanks Alexander. That version of the book provides no reference or proof of the proposition, do you know if the full edition has it or another source for it?
Eli
CC BY-SA 3.0
2011-07-09T21:30:06.320Z
Do you want a proof or do you want to know what to cite if you need to use this theorem in a paper?
Robin Kothari
CC BY-SA 3.0
2011-07-09T22:57:15.013Z
@Robin: either, preferably something that's out there to cite.
Eli
CC BY-SA 3.0
2011-07-10T03:01:43.323Z
I remember having searched for a citation for the second fact you stated, but I didn't find anything. The best citation I know for the first statement is Diestel's book, which doesn't prove the statement. I'll wait to see if someone finds a citation. If not I'll post a proof as an answer.
Robin Kothari
CC BY-SA 3.0
2011-07-10T21:30:47.217Z
@Robin, at this point if you post a proof, that's good enough for me. Is there an appropriate way to attribute you should this result be used somewhere? I'm not familiar with stack exchange policy or standard practice.
Eli
CC BY-SA 3.0
2011-07-10T22:36:00.167Z
@Eli: I think it is advisable to ask questions regarding proper attribution at meta: http://meta.cstheory.stackexchange.com/
Hermann Gruber
CC BY-SA 3.0
2011-07-11T02:07:15.433Z
Thanks, Hermann. If it becomes an issue, I'll ask there.
Eli
CC BY-SA 3.0
2011-07-11T14:35:39.170Z
Actually, citation has already been discussed and resolved here: http://meta.cstheory.stackexchange.com/questions/352/how-will-you-cite-a-discussion-on-this-site-in-your-paper
Aaron Sterling
CC BY-SA 3.0
2011-07-12T01:25:43.763Z
You can also click on the link button below a question/answer and then select cite to get a automatically generated citation for it.
Kaveh
<reference-request><graph-theory><co.combinatorics><graph-minor>
Citation showing minors are topological minors for subcubic graphs
Eli
# Citation showing minors are topological minors for subcubic graphs

(Asked by: username_0 on 2011-07-09)

If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.

Wikipedia cites this result from Diestel's "Graph Theory". It's listed as Prop 1.7.4 in the latest version of the book. The book lacks proof or citation.

Are the whereabouts known for an (original) proof of this?

Furthermore, is there a reference proving that if $G$ is a path or a subdivision of a claw and is a minor of $H$ then $G$ is a subgraph of $H$? It's mentioned [here](https://mathoverflow.net/questions/34060/when-does-graph-minor-containment-imply-subgraph-containment) briefly but lacks reference.

**Tags:** reference-request, graph-theory, co.combinatorics, graph-minor
> **Comments:**
> **username_1**: The book is available at http://diestel-graph-theory.com/  
> **username_0**: Thanks Alexander. That version of the book provides no reference or proof of the proposition, do you know if the full edition has it or another source for it?  
> **username_2**: Do you want a proof or do you want to know what to cite if you need to use this theorem in a paper?  
> **username_0**: @Robin: either, preferably something that's out there to cite.  
> **username_2**: I remember having searched for a citation for the second fact you stated, but I didn't find anything. The best citation I know for the first statement is Diestel's book, which doesn't prove the statement. I'll wait to see if someone finds a citation. If not I'll post a proof as an answer.  
> **username_0**: @Robin, at this point if you post a proof, that's good enough for me. Is there an appropriate way to attribute you should this result be used somewhere? I'm not familiar with stack exchange policy or standard practice.  
> **username_3**: @Eli: I think it is advisable to ask questions regarding proper attribution at meta: http://meta.cstheory.stackexchange.com/  
> **username_0**: Thanks, Hermann. If it becomes an issue, I'll ask there.  
> **username_4**: Actually, citation has already been discussed and resolved here: http://meta.cstheory.stackexchange.com/questions/352/how-will-you-cite-a-discussion-on-this-site-in-your-paper  
> **username_5**: You can also click on the link button below a question/answer and then select cite to get a automatically generated citation for it.  

---

## 1 answers

### Answer by username_2 on 2011-07-11. Score: 13 | Accepted answer

> If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.

Since $G$ is a minor of $H$, $G$ can be obtained from $H$ by deleting edges, isolated vertices and performing edge contractions. It's also easy to show that we can insist that the subgraph operations are done first, i.e., we can first perform all the edge and vertex deletions and then perform all the edge contractions. Moreover, let us restrict the definition of "edge contraction" to disallow contracting edges where one of the vertices has degree 1. Contracting such an edge is the same as deleting it, so this will not change the definition of graph minors.

Let $H'$ be the graph obtained from $H$ by performing all the edge/vertex deletions first. $H'$ still contains $G$ as a minor. If we show that $H'$ contains $G$ as a topological minor then we're done, since the definition of topological minor also allows edge/vertex deletions.

Since $G$ can be obtained from $H'$ by edge contraction only, $H'$ and all intermediate graphs must have maximum degree 3 since there is no way to decrease the maximum degree of a graph by performing an edge contraction. (This would have been possible if we had allowed the contraction of edges incident on a vertex of degree 1.)

So consider any step in the conversion of $H'$ to $G$. The only types of edges we can contract are those with both degree-2 vertices or one degree-2 vertex and one degree-3 vertex. (All other combinations don't work. For example, edges with two degree-3 vertices will give rise to a vertex of degree 4 when contracted.)

And now we're done, since if $H\_1$ is obtained from $H\_2$ by contracting an edge with two degree-2 vertices, then $H\_2$ can be obtained from $H\_1$ by performing edge subdivision on that edge. Similarly for an edge with one degree-3 vertex and one degree-2 vertex. Thus $H'$ can be obtained from $G$ by performing edge subdivisions only, which means $G$ is a topological minor of $H'$ and thus $H$.

> If $G$ is a path or a subdivision of a claw and is a minor of $H$ then $G$ is a subgraph of $H$

This is easy to show once we have the previous result. Since paths and subdivisions of claws have maximum degree 3, if $G$ is a minor of $H$ it is also a topological minor of $H$. This means there is a subgraph of $H$ that can be obtained from $G$ by only performing edge subdivisions. Now it's easy to show by induction that every edge subdivision of a path or subdivision of a claw leads to a graph which contains the original as a subgraph. For example, subdividing a path of length k leads to a path of length k+1, which contains the path of length k as a subgraph. Similarly for subdivisions of a claw.

We also needed this result for a paper once, so we included a short proof in our paper. You can find the result in [Quantum query complexity of minor-closed graph properties](http://arxiv.org/abs/1011.1443). It's mentioned on page 13. However, this fact is hidden away in the proof of something else and isn't stated explicitly as a theorem.

What's also interesting is that there is a converse to this theorem:

> The only graphs $G$ for which containing $G$ as a minor is equivalent to containing $G$ as a subgraph are those in which each connected component is a path or a subdivision of a claw.

> **Comments:**
> **username_0**: Thanks. If you happen to stumble on a published citation for these results, I'd still like it, but this is stellar.  
> **username_4**: This answer is now [featured](http://cstheory.blogoverflow.com/2011/07/an-original-proof-of-a-folk-theorem/) on the community blog.  
> **username_6**: Good answer, but I think that your technique of disallowing degree-1 contractions has a flaw. For example, consider G = K_4 minus any edge. Contracting along the two vertices of degree 3 in G will produce the path graph P_3, with maximal degree 2. Instead, if you disallow any contractions on an edge which would be equivalent to some deletion, the proof should go through. Formally, you forbid any contraction between vertex x and y if gamma(x) \ {y} = gamma(y) \ x. It is easily shown that any contraction not violating this constraint will result in a new vertex of non-decreased degree.  
> **username_2**: @user2237635: You're right, thanks.  

---

