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.