# Number of spanning trees in cycle graphs joined together

Two cycle graphs $C_{n}$ and $C_{m}$ are joined together:

1. with a vertex,
2. with an edge.

What is the number of spanning trees in the new graph?

I think I've worked out the answer to question 1, as there are $n$ possible edges to be removed from $C_{n}$, $m$ to be removed form $C_{m}$ and the rest form a unique spanning tree, so the answer is $n \cdot m$. But I'd appreciate any help with question 2.

• If you remove the common edge, you have an $(m+n-1)$-cycle. What must you do now to get a spanning tree?
• In the first case I have to remove one of the edges, which makes the number of possibilities $m+n-2$. And in the second case I have to calculate the total number of ways I can mix $(m-1)$ egdes with $(n-1)$ edges, that's $(m-1) \cdot (n-1)$. Summing up, $m \cdot n - 1$ spanning trees. Thank you a lot! – Theta Oct 24 '16 at 20:32
• @Theta: Almost: in the first case there are $m+n-1$ possible edges to remove, not $m+n-2$. You’re welcome! – Brian M. Scott Oct 24 '16 at 20:33
• Hmm, are you qsure? I'm inclined to think that the common edge is included both in $C_{n}$ and $C_{m}$, shouldn't it be subtracted twice? – Theta Oct 24 '16 at 20:39