Show that the number of spanning trees of the complete graph $K_n$ is $n^{n−2}$

Question

Let's suppose that $n$ is a natural number representing the number of vertices in a graph. How would we show that the number of spanning trees of the complete graph $K_n$ is $n^{n−2}$? I tested out a few values on $n$ and it makes sense logically, but how would we prove this?

Answer 1

Label the vertices of the complete graph uniquely. Then the spanning trees of $K_n$ are in bijection with the labelled trees on $n$ vertices, as may easily be seen by adding and removing edges.

Cayley's formula gives $n^{n-2}$ as the number of $n$-vertex labelled trees, so this must also be the number of spanning trees of $K_n$.

Answer 2

Easiest answer for me would be to use the matrix tree theorem. For any graph wih laplacian eigenvalues $\mu_i$, the theorem states that the number of spanning tree is $$T = \frac{1}{n} \mu_2 \ldots \mu_n $$

Given the laplacian spectrum of the complete graph $\{n^{n-1},0^1\}$ this direct gives $T=n^{n-2}$