Graph Theory - Application of Kirchoff's Matrix Tree Theorem 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?
 A: 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.)
A: 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}}.$$
A: Recall the combinatorial class $\mathcal{T}$ of rooted labeled trees
with equation
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} =
\mathcal{Z} \times \textsc{SET}(\mathcal{T})$$
which gives the functional equation
$$T(z) = z \exp T(z).$$
Place the mandantory edge $\{1,2\}$ in the center, and attach two sets
of rooted trees by choosing $q$ labels from the remaining $n-2$ labels
for the trees  attached to node $1$  and using the rest  for the trees
attached to node  $2.$ Replicate the ordering of the  nodes in the two
sets of trees using the chosen labels. We get
$$\sum_{q=0}^{n-2} {n-2\choose q}
\left(q! [z^q] \exp T(z)\right)
\left((n-2-q)! [z^{n-2-q}] \exp T(z)\right)
= (n-2)! [z^{n-2}] (\exp(T(z))^2
= (n-2)! [z^{n-2}] \frac{T(z)^2}{z^2}
= (n-2)! [z^{n}] T(z)^2.$$
Introducing
$$T(z)^2 = \sum_{q\ge 0} Q_n \frac{z^n}{n!}$$
we therefore seek $P_n = (n-2)! \frac{Q_n}{n!} = \frac{Q_n}{n(n-1)}$
(here $Q_0 = Q_1 = 0$ and we take $n\ge 2$)
and extract  coefficients from  $T(z)^2$ using the  Cauchy Coefficient
Formula:
$$\frac{Q_n}{(n-1)!} =
[z^{n-1}] \left(T(z)^2\right)'
= [z^{n-1}] 2 T(z) T'(z)
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{2}{z^n} T(z) T'(z) \; dz.$$
Using the functional equation we put $w = T(z)$ so that $z=w\exp(-w)$
to obtain
$$\frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{2\exp(nw)}{w^n} w \; dw
= \frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{2\exp(nw)}{w^{n-1}} \; dw
= 2\frac{n^{n-2}}{(n-2)!}.$$
We thus have
$$Q_n = (n-1)! \times 2\frac{n^{n-2}}{(n-2)!} =
(n-1) \times 2 n^{n-2}$$
and therefore
$$\bbox[5px,border:2px solid #00A000]{
P_n = 2 n^{n-3}.}$$
Remark. The initial construction may be simplfied by recognizing
that we require the combinatorial class
$$\textsc{SET}(\mathcal{T}) \times \textsc{SET}(\mathcal{T})$$
where the trees  in the first set  are attached by their  roots to the
node $1$ and the ones in the  second to the node $2$. We have absorbed
the  step with  the  binomial  coefficient and  may  then continue  as
before.
