Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.)

share|cite|improve this answer
+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.

share|cite|improve this answer
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

Your Answer


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.