Minimum spanning trees given adjacency matrix of a graph 
Consider the graph $G$ given by following adjacency matrix $A=\begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 &1 &0 \\ 0 &1 &1 &0 & 1\\ 1&1 &0&1&0 \end{pmatrix}$
Find the number of minimum spanning trees of the graph $G$

How do I find the number of minimum spanning trees? I can use Prim algorithm and find a minimum spanning tree but how do I know how many they are?
I draw the graph $G$ given its adjacency matrix:

Thanks in advance.
 A: You can use Kirchhoff's theorem. Let $D$ be the diagonal matrix whose entries are the degrees of the vertices of G. If you delete any row of $A-D$ (the Laplacian matrix) and its corresponding column, then the determinant of the resulting minor is the number of spanning trees for the graph.
A: We throw away the loop, since spanning trees don't have loops.  Also, since all edges have weight 1, a "minimum spanning tree" is just a "spanning tree".  A $n$-vertex spanning tree has $n-1$ edges; in this case that's $4$ edges.  There are $\binom{7}{4}=35$ subgraphs with $4$ edges (ignoring the loop), which I drew using a script below.
Now we count the ones without cycles, which are necessarily spanning trees: 21.

A: You can compute it recursively. Also, start from a node with minimum degree. For example, pick node 1. As it has 2 edges, you can compute different minimum spanning trees by 3 states.
First, remove $e_{12}$, and then compute MST for the other nodes ($k$).
Then, you can multiply $k$ by 2, as there is a similar situation for removing $e_{15}$.
Finally, suppose $e_{12}$ and $e_{15}$ exist in a MST. Now, compute MST between nodes $\{2, 3,4\}$ ($l$) and $\{3,4,5\}$ ($m$).
Hence, number of MST is $2k + l + m$ which comes from recursive existence of $e_{12}$, $e_{15}$ and both in the MST.
