4
$\begingroup$

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.

  • 0
    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.2010-08-06

2 Answers 2

4

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

  • 0
    +1 Very clean :-) The final inequality should be the other way around: $n \leq 4$.2010-09-22
  • 0
    @tttppp: inequality corrected. Thanks!2011-05-17
6

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
    I think that this is precisely the kind of hint that we should be giving to homework questions2010-08-04