How to find number of spanning tree?

Question

Suppose $G$ is a $k$-regular graph with $n$ vertices and with eigenvalues $k = λ_1 > λ_2 ≥ \cdots ≥ λ_n.$

Find the number of spanning trees in $G$.

Answer 1

You can use Kirchoff's Theorem, which states that number of spanning trees,

$$ t(G) = \frac{1}{n} \lambda_1 ' \lambda_2 '... \lambda_{n-1} '$$

Notice that only $n-1$ eigenvalues are taken in the formula. The eigenvalue which is missing is the smallest eigenvalue. All eigenvalues must be real since it is a symmetric matrix.

Here the eigenvalues are of the Laplacian Matrix that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a $(0,1)$-matrix with $1$'s at places corresponding to entries where the vertices are adjacent and $0$'s otherwise).

Since this is a $k$ regular graph, the degree matrix is basically $kI$ where $I$ is the identity matrix. Now we have to figure out how eigenvalues change when (i) they are multiplied by $-1$ (scalar) and (ii) when a constant is added to each diagonal element. You can try to answer this yourself. The answers are (i) unchanged except for their sign which flips and (ii) eigenvalues are increased by same constant. After this the correct answer should be evident,

$$ \boxed{ t(G) = \frac{1}{n} (\lambda_2 + k) (\lambda_3+k) ... (\lambda_n+k)}$$

But here the missing eigenvalue is the largest among the given eigenvalues of the graph, since the signs flipped when multiplying by $-1$.