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?)
I know the number is $(n-2)n^{n-3}$ and that Kirchoff's matrix tree theorem applies but how do I show this?
On
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 (For each edge $e$ of $K_n$, the number of spanning trees of $K_n$ containing $e$ does not depend on $e$ (to prove this, pick any two edges $e$ and $f$ of $K_n$, and set up a bijection between the spanning trees containing $e$ and the spanning trees containing $f$). But the sum of these numbers is $n−1$ times the number of all spanning trees of $K_n$) the answer is given by $$n^{n-2}-(n-1)n^{n-2}\binom{n}{2}^{-1}=\color{red}{(n-2)n^{n-3}}.$$
All edges of $K_n$ are identical. So if there are $n^{n-2}$ spanning trees of $K_n$, and each includes $n-1$ edges out of $\binom n2$, then each edge is included in $$\frac{n-1}{\binom n2} \cdot n^{n-2} = \frac2n \cdot n^{n-2} = 2n^{n-3}$$ spanning trees.
(Normally, this would be "included in an average of $2n^{n-3}$ spanning trees", but because all edges of $K_n$ are identical, all of them are contained in exactly the average number.)