Csdrhrt

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?

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.)

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_nsetminus e$ is given by the determinant of the reduced Laplacian matrix of $K_nsetminus 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:
$$ detbegin{pmatrix}n-1 & -n & 0 & 0 \ -1 & n-1 & -1 & -1 \ -1& -1 & n-1 & -1 \ -1 & -1 & -1 & n-1end{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}}.$$

Recall the combinatorial class $mathcal{T}$ of rooted labeled trees
with equation

$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{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-2choose 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_{qge 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 $nge 2$)

and extract coefficients from $T(z)^2$ using the Cauchy Coefficient
Formula:

$$frac{Q_n}{(n-1)!} =
[z^{n-1}] left(T(z)^2right)'
= [z^{n-1}] 2 T(z) T'(z)
\ = frac{1}{2pi 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=wexp(-w)$
to obtain

$$frac{1}{2pi i}
int_{|w|=gamma} frac{2exp(nw)}{w^n} w ; dw
= frac{1}{2pi i}
int_{|w|=gamma} frac{2exp(nw)}{w^{n-1}} ; dw
= 2frac{n^{n-2}}{(n-2)!}.$$

We thus have

$$Q_n = (n-1)! times 2frac{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.