In this question, a "graph" and a "subgraph" will always be a loop-free multigraph (finite, undirected, unweighted).

Motivation: Given a graph in which each vertex has even degree, we can find a cycle (possibly a 2-cycle). If we delete this subgraph, we preserve the vertex degrees modulo $2$. Thus, we can repeatedly use this process to decompose the graph into cycles.

I'm interested into whether or not a similar property is true for cubic (i.e. 3-regular) subgraphs.

Question: Does a graph with all vertex degrees divisible by 3 contain a cubic subgraph?

If it does, then we can use the same argument to show that any such graph decomposes into cubic subgraphs. If it doesn't, then we have a counter-example. So, this is the same question as:

Question: Does a graph with all vertex degrees divisible by 3 decompose into cubic subgraphs?

I find it hard to believe that nobody has considered this problem before. So my suspicion is that either the proof is hard, the proof is easy (and I've missed something obvious) or there's a folklore counter-example.

I found some related papers: Spanning cubic graph designs, by Peter Adams and others, and Cubic factorizations by Moshe Rosenfeld and Vũ Đình Hòa, but they restrict their attention to decomposing the complete graph.

  • 2
    $\begingroup$ As Kevin noted with the smallest example, any connected graph having all but one vertex of degree 3 and the other vertex of higher degree is a counterexample. But to kill this idea properly, counterexamples with arbitrarily high minimum degree would be nice. $\endgroup$ Nov 10, 2012 at 23:45

1 Answer 1



alt text http://www.freeimagehosting.net/newuploads/8m77r.png


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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