mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, Cayley's formula is a result in

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

named after

Arthur Cayley Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics. As a child, C ...

. It states that for every

positive integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...

n

, the number of

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...

n

labeled vertices is

n^

. The formula equivalently counts the number of

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

s of a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

with labeled vertices .

Proof

Many proofs of Cayley's tree formula are known. One classical proof of the formula uses

Kirchhoff's matrix tree theorem In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time ...

, a formula for the number of spanning trees in an arbitrary graph involving the

determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...

of a

matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

Prüfer sequence In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on ''n'' vertices has length ''n'' − 2, and can be ...

s yield a

bijective proof In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other ...

of Cayley's formula. Another bijective proof, by

André Joyal André Joyal (; born 1943) is a professor of mathematics at the Université du Québec à Montréal who works on category theory. He was a member of the School of Mathematics at the Institute for Advanced Study in 2013, where he was invited to jo ...

, finds a one-to-one transformation between ''n''-node trees with two distinguished nodes and maximal directed

pseudoforest In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every connected component has at most one cycle. Tha ...

s. 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 .

History

The formula was first discovered by

Carl Wilhelm Borchardt Carl Wilhelm Borchardt (22 February 1817 – 27 June 1880) was a German mathematician. Borchardt was born to a Jewish family in Berlin. His father, Moritz, was a respected merchant, and his mother was Emma Heilborn. Borchardt studied under ...

in 1860, and proved via a

. 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 A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...

on ''n'' vertices, namely . Each labelled rooted forest can be turned into a labelled tree with one extra vertex, by adding a vertex with label 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 . 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 .

References

{{reflist Trees (graph theory)