Cayley's formula

Not to be confused with Cayley's theorem.

In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer $n$, the number of trees on $n$ labeled vertices is $n^{n-2}$.

The complete list of all trees on 2,3,4 labeled vertices: $2^{2-2}=1$ tree with 2 vertices, $3^{3-2}=3$ trees with 3 vertices and $4^{4-2}=16$ trees with 4 vertices.

The formula equivalently counts the number of spanning trees of a complete graph with labeled vertices (sequence A000272 in the OEIS).

Proof

Many proofs of Cayley's tree formula are known. One classical proof of the formula uses Kirchhoff's matrix tree theorem, a formula for the number of spanning trees in an arbitrary graph involving the determinant of a matrix. 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 counts in two different ways the number of different sequences of directed edges that can be added to an empty graph on n vertices to form from it a rooted tree; see Double counting (proof technique) § Counting trees.

History

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.

Other properties

Cayley's formula immediately gives the number of labelled rooted forests on n vertices, namely (n + 1)^{n − 1}. Each labelled rooted forest can be turned into a labelled tree with one extra vertex, by adding a vertex with label n + 1 and connecting it to all roots of the trees in the forest.

There is a close connection with rooted forests and parking functions, since the number of parking functions on n cars is also (n + 1)^{n − 1}. A bijection between rooted forests and parking functions was given by M. P. Schützenberger in 1968.

Generalizations

The following generalizes Cayley's formula to labelled forests: Let T_n,k be the number of labelled forests on n vertices with k connected components, such that vertices 1, 2, ..., k all belong to different connected components. Then T_n,k = k n^{n − k − 1}.