# Counting spanning trees in labelled graphs

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?

• Thanks a lot, so it's (m-2+n-2)*1 + (m-2)*(n-2)? – LookingForKnowledge Apr 21 '15 at 19:54
• @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. – Brian M. Scott Apr 21 '15 at 20:01
• Ah yes, obviously, thanks :) – LookingForKnowledge Apr 21 '15 at 20:01
• 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? – LookingForKnowledge Apr 21 '15 at 20:20
• @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? – Brian M. Scott Apr 21 '15 at 20:33