Question on completeness of graphs in Cayley's Formula

Question

In my textbook, Cayley's Formula is presented as follows:

There are $n^{n-2}$ distinct labeled trees of order $n$.

However, this statement says nothing about whether or not this formula applies to complete graphs only, which it does. I'm certain that the textbook isn't incorrect, so why is it that the theorem is presented in this way? What am I missing here?

Answer 1

The version of the theorem that applies to complete graphs only is

There are are $n^{n-2}$ spanning trees of the complete graph on $n$ vertices.

Indeed, if you replace the complete graph with any other graph, the number will change.

But the version of the theorem that states

There are $n^{n-2}$ labeled trees on $n$ vertices.

isn't making a claim about spanning trees at all. It is simply counting connected, acyclic graphs on a fixed vertex set of size $n$.

Of course, it's not hard to see that the two statements are equivalent: any spanning tree of $K_n$ has $n$ vertices, and any tree on $n$ vertices is a spanning tree of $K_n$.

Answer 2

Yes, this works for counting spanning subtrees of $K_n$.

If you want to count spanning subtrees of any graph $G$ you can use Kirchoffs theorem, Cayleys theorem is a particular case as the laplacian of $K_n$ has spectra $[n-1]^{n-1},[0]^1$