12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The book is available at diestel-graph-theory.com $\endgroup$ – Alexander Langer Jul 9 '11 at 16:27
  • $\begingroup$ 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? $\endgroup$ – Eli Jul 9 '11 at 19:43
  • 2
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Jul 10 '11 at 3:01
  • 1
    $\begingroup$ @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. $\endgroup$ – Eli Jul 10 '11 at 21:30
  • 1
    $\begingroup$ Actually, citation has already been discussed and resolved here: meta.cstheory.stackexchange.com/questions/352/… $\endgroup$ – Aaron Sterling Jul 11 '11 at 14:35
13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks. If you happen to stumble on a published citation for these results, I'd still like it, but this is stellar. $\endgroup$ – Eli Jul 11 '11 at 17:03
  • $\begingroup$ This answer is now featured on the community blog. $\endgroup$ – Aaron Sterling Jul 25 '11 at 12:57
  • $\begingroup$ 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. $\endgroup$ – RussellStewart Dec 29 '13 at 23:45
  • $\begingroup$ @user2237635: You're right, thanks. $\endgroup$ – Robin Kothari Jan 8 '14 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.