Minimum spanning trees given adjacency matrix of a graph

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.