1
$\begingroup$

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?

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.