Many remarkable proofs of Cayley's tree formula are known. One classical proof of the formula uses Kirchhoff's matrix tree theorem. Prüfer sequences yield a bijective proof of Cayley's formula. Another bijective proof, by André Joyal, finds a one-to-one transformation between n-node trees with two distinguished nodes and maximal directed pseudoforests. A proof by double counting due to Jim Pitman applies to trees.
The formula was first discovered by Carl Wilhelm Borchardt in 1860, and proved via a determinant. In a short 1889 note, Cayley extended the formula in several directions, by taking into account the degrees of the vertices. Although he referred to Borchardt's original paper, the name "Cayley's formula" became standard in the field.
- Kirchhoff's theorem, a formula for the number of spanning trees in an arbitrary graph involving the determinant of a matrix.
- Aigner, Martin; Ziegler, Günter M. (1998). Proofs from THE BOOK. Springer-Verlag. pp. 141–146.
- Borchardt, C. W. (1860). "Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung". Math. Abh. der Akademie der Wissenschaften zu Berlin: 1–20.
- Cayley, A. (1889). "A theorem on trees". Quart. J. Math 23: 376–378.