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?
Any graph on $n$ vertices with $k$ automorphisms – ways its vertices can be mapped onto themselves to preserve the edges – has $\frac{n!}k$ labellings. Applying this to the trees on seven vertices (the image below taken from Peter Steinbach's Field Guide to Simple Graphs, available on the OEIS under the links at A000055):
we see that the trees from left to right have the following numbers of automorphisms:
$$2,2,1,6,8,2,6,4,12,24,720$$
Dividing $7!=5040$ by each number gives the number of labellings of each of these trees:
$$2520,2520,5040,840,630,2520,840,1260,420,210,7$$
As expected, they add up to $7^5=16807$.
Finding the order of the automorphism group of a tree
As an example, take the second tree from the left. There is only one order-3 vertex, so it must stay fixed in any automorphism. Three paths radiate from this vertex – one of length 4 that must also stay fixed, and two of length 1 that can be swapped. Multiplying the numbers together gives two automorphisms.
For the rightmost star, while the central hub must stay fixed, the six spokes can be permuted in any order, yielding $6!=720$ automorphisms.
Best Answer
The Prufer sequence approach would also work (except that your condition should be that a vertex appears exactly $n-3$ times*). You should be able to count the number of such sequences. All that matters is which vertex appears $n-3$ times, which other vertex appears, and which position the other vertex appears in - how many possibilities is this?
*Note that a vertex of degree $k$ appears exactly $k-1$ times in the Prufer sequence. This is because as you construct the sequence you remove leaves one by one. If a vertex $v$ has degree $k$, then $k-1$ of its neighbours must be removed before it becomes a leaf, and each time this happens $v$ is added to the sequence. Once $v$ becomes a leaf, either it is removed itself or $v$ and its remaining neighbour are the final two vertices. In neither case is it added to the sequence again.