4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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$
    – Brendan McKay
    Commented Nov 10, 2012 at 23:45

1 Answer 1

Reset to default
14
$\begingroup$

Counterexample:

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

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .