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.


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.

  • $\begingroup$ 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! $\endgroup$ – Theta Oct 24 '16 at 20:32
  • 1
    $\begingroup$ @Theta: Almost: in the first case there are $m+n-1$ possible edges to remove, not $m+n-2$. You’re welcome! $\endgroup$ – Brian M. Scott Oct 24 '16 at 20:33
  • $\begingroup$ 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? $\endgroup$ – Theta Oct 24 '16 at 20:39
  • 1
    $\begingroup$ @Theta: You’re right: I was inadvertently counting the edges in the whole graph. My apologies! $\endgroup$ – Brian M. Scott Oct 24 '16 at 20:42
  • 1
    $\begingroup$ @Theta: My pleasure. $\endgroup$ – Brian M. Scott Oct 24 '16 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.