# Number of spanning trees for these 2 figures

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 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!

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.

• 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." – Arthur Nov 10 '14 at 14:07
• Really appreciate the clear answer, thanks Prof! :) – Faizal Ismaeel Nov 10 '14 at 14:48
• @Delvacode: You’re welcome! – Brian M. Scott Nov 10 '14 at 14:48
• @Arthur: Thanks for the clarification! – Faizal Ismaeel Nov 10 '14 at 14:56