Ytukyg

I know that if you take the determinant of the Laplacian Matrix, then you can get the number of spanning trees. However is that also the case for when you have either the Adjacency Matrix or the Degree Matrix?

If not, what would you have to do to find the amount of spanning trees if you were only provided the adjacency matrix (or degree matrix)?

It does not work with the adjancency matrix nor the degree matrix. To see this, let's look at $K_4$, which we know has $4^{4 - 2}$ spanning trees. (There's nothing special about $K_4$, it's just the first graph I picked.)

$K_4$ has $4$ vertices each of degree $3$. Applying Kirchoff rule to the degree matrix gives $3^3$ spanning trees (incorrect). Applying it to the adjacency matrix gives
$$ left| begin{array}{ccc} 0 & 1 & 1 \ 1 & 0 & 1 \ 1 & 1 & 0 end{array} right| = 2$$
(also incorrect).

To understand why you need the Laplacian, it is helpful to understand a proof of Kirchoff's theorem. Here is one outline.

Theorem 1. (Binet-Cauchy) If $A$ is $m times n$ and $B$ is $n times m$ then
$$ det(AB) = sum_S det(A[S]) det(B[S]) $$
where the sum is over all $m$-element sets of columns of $A$ and rows of $B$. Here $A[S]$ means we keep only the columns from $S$ and $B[S]$ means we keep only the rows from $S$.

Lemma 2. Let $G$ be a connected graph with no loops (but multiple edges are allowed). Arbitrarily orient $G$ and let $D$ be the signed incidence matrix:

$$ D_{ve} = begin{cases} 1 & v text{ is the head of } e \
-1 & v text{ is the tail of } e \
0 & text{otherwise} end{cases} $$

(Rows are indexed by vertices and columns by edges.) Then $DD^T = L$, the Laplacian of $G$.

Lemma 3. Let $G$ be a connected graph with no loops, oriented arbitrarily. Let $D$ be the signed incidence matrix. If $v in V(G)$ and $S subseteq E(G)$ then $D(v,S)$ denotes the matrix with row $v$ deleted and keeping only the columns belonging to $S$. (So our sets $S$ have $|V(G)| - 1$ elements.)

Then $det D(v,S) = pm 1$ if $(V,S)$ is a spanning tree and $det(v,S) = 0$ if $(V,S)$ is not (i.e. it contains a cycle).

There are of course other proofs of Kirchoff's Theorem. What we can see here is that Lemma 3 is the tool that connects spanning trees to determinants and it is a result about the signed incidence matrix. From Lemma 2 and Binet-Cauchy, we remove the issue with having a sign of $pm 1$ by squaring and we sum over all sets $S$ to count the total number of trees.

Now, if you are given the adjacency matrix, it is easy enough to construct the degrees of each vertex and hence construct the number of spanning trees. On the other hand, if you only have the degrees, you don't know enough about the graph structure to count spanning trees. As an exercise, find two graphs with the same degree sequence but different numbers of spanning trees (remember you can use multiple edges).