Citation showing minors are topological minors for subcubic graphs 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 briefly but lacks reference.
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&#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.

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.)

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.)

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$.


  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. 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.