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

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?

## marked as duplicate by José Carlos Santos, GNUSupporter 8964民主女神 地下教會, Vinyl_cape_jawa, supinf, SongMar 1 at 16:33

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$$.
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}$$