Minimum spanning trees given adjacency matrix of a graph Consider the graph $G$ given by following adjacency matrix $A=\begin{pmatrix} 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 \\ 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\ 0 &amp; 1 &amp; 0 &amp;1 &amp;0 \\ 0 &amp;1 &amp;1 &amp;0 &amp; 1\\ 1&amp;1 &amp;0&amp;1&amp;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.
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.
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.