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.

  • $\begingroup$ 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. $\endgroup$ – 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.)

  • $\begingroup$ +1 Very clean :-) The final inequality should be the other way around: $n \leq 4$. $\endgroup$ – tttppp Sep 22 '10 at 8:52
  • $\begingroup$ @tttppp: inequality corrected. Thanks! $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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