Is there a way to know how many non-isomorphic spanning trees there are for a graph?

Question

I have a big doubt: Is there a way to know how many non-isomorphic spanning trees there are for a graph?

In a Spanning Tree there are no cycles, one less thing to worry about.

Answer 1

If the graph is a complete graph with $n$ vertices, it then has $n^{(n-2)}$ spanning trees by Cayley's formula.

If the graph isn't a complete graph, you can use Kirchoff's theorem. Here's an example of it (I took the example from this video):

For the following graph, you first take the adjacency matrix:

\begin{pmatrix} 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1\\ 1 & 1 & 1 & 0 \end{pmatrix}

Next, you take the degree matrix:

\begin{pmatrix} 3 & 0 & 0 & 0\\ 0 & 2 & 0 & 0\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 3 \end{pmatrix}

And then you calculate the difference between the two matrices, which is:

\begin{pmatrix} 3 & -1 & -1 & -1\\ -1 & 2 & 0 & -1\\ -1 & 0 & 2 & -1\\ -1 & -1 & -1 & 3 \end{pmatrix}

Lastly, delete any row and any column from this resultant matrix, and then calculate the determinant. Here is the matrix which is the result of deleting the first row and first column:

\begin{pmatrix} 2 & 0 & -1\\ 0 & 2 & -1\\ -1 & -1 & 3 \end{pmatrix}

The determinant of this matrix is 8. This is the number of spanning trees for this graph.