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.
Best Answer
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:
Can you count the spanning trees now?