Application of Kirchoff's Matrix Tree Theorem

Question

Calculate the number of spanning trees of the graph that you obtain by removing one edge from $K_n$.

(Hint: How many of the spanning trees of $K_n$ contain the edge?)

Can anyone please help me out here?

Answer 1

By Cayley's formula or Prufer encoding we have that the number of spanning trees of $K_n$ is $n^{n-2}$. By Kirchoff' theorem, the number of spanning trees in $K_n\setminus e$ is given by the determinant of the reduced Laplacian matrix of $K_n\setminus e$. The Laplacian matrix (in the $n=5$ case) has the following structure: $$ \begin{pmatrix} n-2 & -1 & -1 & -1 & 0 \\ -1 & n-1 & -1 & -1 & -1 \\ -1 & -1 & n-1 & -1 & -1 \\ -1 & -1 & -1 & n-1 & -1 \\ 0 & -1 & -1 & -1 & n-2 \end{pmatrix} $$ and a similar structure in the general case. By removing the last row&column, the problem boils down to computing the determinant of a $(n-1)\times(n-1)$ matrix with off-diagonal elements equal to $-1$ and diagonal elements equal to $n-2,n-1,\ldots,n-1$. By performing one step of Gaussian elimination and a Laplace expansion along the first row, the wanted number of spanning trees is so given by: $$ \det\begin{pmatrix}n-1 & -n & 0 & 0 \\ -1 & n-1 & -1 & -1 \\ -1& -1 & n-1 & -1 \\ -1 & -1 & -1 & n-1\end{pmatrix}$$ that is simple to compute from the fact that the determinant of o $(n-1)\times(n-1)$ matrix with diagonal elements equal to $(n-1)$ and off-diagonal elements equal to $-1$ is $n^{n-2}$.

On the other hand, by Grinberg's remark the answer is given by $$n^{n-2}-(n-1)n^{n-2}\binom{n}{2}^{-1}=\color{red}{(n-2)n^{n-3}}.$$