Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Brendan McKay Nov 10 '12 at 23:45
add comment

1 Answer

up vote 14 down vote accepted

Counterexample:

alt text

share|improve this answer
    
Thanks for that! –  Douglas S. Stones Nov 11 '12 at 0:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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