1
$\begingroup$

The solution to the number of spanning trees of the graph below is given by $6$ and $4 \times 4 - 1$ for Graph A and B respectively. I'm not sure how to get this. Please assist. I did ask a similar question a while ago but I'm still not able to figure out for these 2 figures. Thanks!

Graph A :

Graph A

Graph B :

Graph B

What I know:

1) Number of spanning trees of a cycle with n vertices is, $\tau(C_n) = n$ 2) I know how to solve the above using the contraction deletion theorem but I'm interested in other methods, thanks!

$\endgroup$
5
$\begingroup$

Remember that a tree always has one more vertex than it has edges. Graph A has $7$ vertices and $7$ edges, so you’ll be able to remove only one edge and still have a tree. Clearly you have to keep the edge $GF$: removing it disconnects the graph. However, you can remove any of the other $6$ and have a spanning tree.

Graph B has $6$ vertices and $7$ edges, so you have to remove $2$ edges to get a spanning tree. I would look at two cases.

  • Suppose first that we remove the edge $CD$; that leaves a $6$-cycle, and we can remove any of its $6$ edges to get a spanning tree.

  • Now suppose that we keep the edge $CD$. We have to break the $4$-cycle $ABDC$, so we can remove any one of the $3$ edges $AB$, $BD$, and $AC$. We also have to break the $4$-cycle $CDFE$, and again we have a choice of $3$ edges to remove. These breakings are independent of each other, so there are $3\cdot3=9$ spanning trees that include the edge $CD$.

Combining cases gives us a total of $15$ spanning trees.

$\endgroup$
  • 2
    $\begingroup$ Just to clarify, in this answer it's more natural to write the number of spanning trees of $B$ as $6 + 3\cdot 3$ rather than $4 \cdot 4 - 1$. The answer is $15$ either way, but how you write it out hints to how you got to the answer. One way to count it if you want to get $4\cdot 4 - 1$ instead could be to say: "We need to delete one edge from the upper square, and one edge from the lower square. There's $4\cdot 4$ ways to choose the two edges, but we have to subtract the case where $CD$ is removed twice (it's part of both squares), since that's not really an option." $\endgroup$ – Arthur Nov 10 '14 at 14:07
  • $\begingroup$ Really appreciate the clear answer, thanks Prof! :) $\endgroup$ – Faizal Ismaeel Nov 10 '14 at 14:48
  • $\begingroup$ @Delvacode: You’re welcome! $\endgroup$ – Brian M. Scott Nov 10 '14 at 14:48
  • $\begingroup$ @Arthur: Thanks for the clarification! $\endgroup$ – Faizal Ismaeel Nov 10 '14 at 14:56

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.