Named after Arthur Cayley, the formula says that the number of labeled spanning trees of a complete simple graph with n vertices is nn-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 nn-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.

Log in or register to write something here or to contact authors.