# Connected simple cubic graph

I am trying to understand this problem and yes this is from my assignment and I should be doing it myself, but I have been staring at it for 2 hours and not getting anywhere, so decided to post it here.

Let G be a connected cubic simple graph that contains 2 edge-disjoint spanning trees show that |G| = 4.

• Thanks for all the answers guys! When I was reading the problem, I was understanding "2 edge-disjoint spanning tree" as two trees with all edges same but only two different and thats why I had hard time in visualizing but as soon as I realized that it was 2 "edge-disjoint spanning trees", it all started making sense. – user634 Aug 6 '10 at 14:36

Let $G$ be a simple cubic graph, with two edge-disjoint spanning trees, that has $n$ vertices and $m$ edges. Since $G$ is regular of degree 3, we have

$3n = 2m.$

Now any spanning tree has $n-1$ edges, and $G$ has two disjoint spanning trees. So we have

$m \ge 2n - 2.$

Combining the first equation and the second inequality, we get

$n \le 4$.

Now there are no cubic simple graphs on 1, 2 or 3 vertices, so the result follows. (It is debatable whether there is one on 0 vertices.)

• +1 Very clean :-) The final inequality should be the other way around: $n \leq 4$. – tttppp Sep 22 '10 at 8:52
• @tttppp: inequality corrected. Thanks! – Emil May 17 '11 at 10:44

Express the number of edges in a connected cubic simple graph in terms of the number of vertices. Then do the same for a graph that contains 2 edge-disjoint spanning trees. Solve this equation for the number of vertices.

• I think that this is precisely the kind of hint that we should be giving to homework questions – Casebash Aug 4 '10 at 2:27