Number of spanning trees in cycle graphs joined together

Question

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.

Answer 1

HINT: You’re right about the first problem. For the second you have to consider two possibilities:

• If you remove the common edge, you have an $(m+n-1)$-cycle. What must you do now to get a spanning tree?
• If you keep the common edge, you have to break each of the two cycles by removing one of its other edges.

Count the spanning trees in each case and add the results to get the final answer.

Answer 2

Don't know if you are still interested, but generally speaking the number of spanning trees of a connected graph (else we speak of spanning forests) is given by the order of the jacobian group of the graph. It can be computed by putting the reduced laplacian of the graph in Smith normal form and then multiplying the diagonal entries. In the case of 2 graphs joined by a vertex, the jacobian group is the direct product of the individual groups. When joined by an edge I think the order is $m\cdot n -1$ if $m$ and $n$ are the size of the 2 cycles. More generally, if the two cycles are joined by $k$ different and consecutive edges, this order is $n\cdot m - k^2$ (to be verified)