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](http://dx.doi.org/10.1016/j.disc.2008.07.031), by Peter Adams and others, and [Cubic factorizations](http://dx.doi.org/10.1016/j.disc.2012.05.001) by Moshe Rosenfeld and Vũ Đình Hòa, but they restrict their attention to decomposing the complete graph.



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


[alt text http://www.freeimagehosting.net/newuploads/8m77r.png](http://www.freeimagehosting.net/newuploads/8m77r.png)


