I have some troubles with counting spanning trees, it seems completely abstract to me.

First one is cycle with $n$ vertices - it's just $n$, because we can move each number $n$ times like so: $1234$ $2341$ $3412$ $4123$ etc

Second graph of a tetrahedron, we can either have some vertex with degree $3$, and there are $4$ graphs like that because we simply put each number from $1$ to $4$ as this vertex and then we can have a tree with $\max(\deg(v_i)=2$ and this is where I fail.

How many isomorphic labelled trees with max degree $2$ are there? Is it $n!/2$ because $1, 2, ..., n-1,n$ is the same as $n, n-1, ..., 2, 1$?

Next, we have $2$ cycles, one with $n$ vertices and second with $m$ vertices, and we combine them so that they have:

a) $1$ common vertex, which is easy because it has just $nm$ spanning trees.

b) $1$ common edge, and here I fail, I have no idea where to even begin.


You’ve made a pretty good start. You’re right that an $n$-cycle has $n$ spanning trees. Another way to explain it is to notice that deleting one edge leaves $n$ vertices and $n-1$ edges, so you have a tree; clearly that tree spans the cycle, and there are $n$ possible edges to remove, so there are $n$ spanning trees.

With $K_4$, the tetrahedron, you got $4$ of the spanning trees, but as you said, there are more: any path of length $3$ is a spanning tree. Since every possible edge is available, any permutation of the $4$ vertices yields a spanning tree. However, this counts each path twice, once in each direction, so there are really only $\frac{4!}2=12$ such spanning trees, as you suspected. The total number of spanning trees is therefore $4+12=16$.

You’re right about the graph consisting of an $m$-cycle and an $n$-cycle that share only a vertex.

Now let $G$ be the graph consisting of an $m$-cycle and an $n$-cycle that share exactly one edge, $e$. $G$ has $m+n-2$ vertices, so a spanning tree for $G$ will have $m+n-3$ edges. $G$ itself has $m+n-1$ edges, so we need to remove $2$ edges to get a spanning tree. However, we can’t just remove any pair of edges: we have to make sure that what’s left is still connected. There are two different ways to do this:

  • remove $e$ and any other edge; or
  • remove one edge other than $e$ from each cycle.

Can you count the spanning trees now?

  • $\begingroup$ Thanks a lot, so it's (m-2+n-2)*1 + (m-2)*(n-2)? $\endgroup$ – LookingForKnowledge Apr 21 '15 at 19:54
  • $\begingroup$ @LookingForKnowledge: You’re welcome. You’re almost right, but you’ve made the same mistake in both counts: there are $m-1$ edges other than $e$ in the $m$-cycle, and $n-1$ edges other than $e$ in the $n$-cycle, so there are $m-1+n-1=m+n-2$ spanning trees of the first type and $(m-1)(n-1)$ of the second type. $\endgroup$ – Brian M. Scott Apr 21 '15 at 20:01
  • $\begingroup$ Ah yes, obviously, thanks :) $\endgroup$ – LookingForKnowledge Apr 21 '15 at 20:01
  • $\begingroup$ Do you mind looking at one last graph please? picresize.com/images/rsz_screenshot_from_2015-04-21_205206.png It has 2 4-cycles, and then 4 edges connecting them. My take on this is - 4 *4(number of spanning trees of each cycle) * 2 (you have to connect left cycle with one edge to the middle vertex and then the right one) * 2 = 16*4 = 64, is it correct? $\endgroup$ – LookingForKnowledge Apr 21 '15 at 20:20
  • $\begingroup$ @LookingForKnowledge: It's a little more complicated than that. You have two copies of a graph $G$ consisting of a $3$-cycle and a $4$-cycle sharing an edge, and these two copies share the central vertex. In the previous question you saw how to calculate the number of spanning trees in $G$, and in the one before that you dealt with two graphs sharing a vertex. Can you put those pieces together here? $\endgroup$ – Brian M. Scott Apr 21 '15 at 20:33

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.