Named after Arthur Cayley, the formula says that the number of labeled spanning trees of a complete simple graph with *n* vertices is **n**^{n-2}

The interesting thing about Cayley's formula is that there are numerous different proofs for it, and new ones come out often, even to this day. Many textbooks use the proof by Prüfer (perhaps because professors like the phrase "Prüfer's proof"). Prüfer links the fact that n^{n-2} is the number of ways to write down a string of length n-2 from a set S of n numbers.

The proof sets up a code (called Prüfer's code) that maps such strings to labeled spanning trees in a one-to-one correspondence. The actual proof, however, is left to a better noder than I to explain, as it requires some drawing and a lot of hand-waving.