Cayley formula

All designated trees of sizes 2, 3 and 4.

All 16 spanning trees of the complete graph with 4 nodes.

The Cayley formula (named after Arthur Cayley ), sometimes also called Cayley's theorem , is a theorem from combinatorial counting . It says that there are various labeled trees with knots. ${\displaystyle n^{n-2}}$ ${\displaystyle n}$

Formulations

• There are several labeled trees with knots. ${\displaystyle n^{n-2}}$ ${\displaystyle n}$
• The labeled full graph with nodes has different spanning trees . ${\displaystyle n}$ ${\displaystyle n^{n-2}}$

proofs

The evidence for Cayley's formula is abundant, some of which are considered particularly beautiful by many mathematicians. This is reflected, among other things, in the fact that a chapter in The Book of Evidence is dedicated to the Cayley formula . There are four types of evidence presented:

1. by means of a bijection of the set of all trees into a set that is easier to count (see checker code ),
2. using Kirchhoff's theorem ,
3. by means of recursion ,
4. by counting twice .

history

The formula was first published by Carl Wilhelm Borchardt (1860). In 1889 Cayley expanded the formula and formulated it in graph terminology, which is why it has been associated with his name ever since.

It is also worth mentioning that James Joseph Sylvester published an equivalent result as early as 1857.

literature

• Martin Aigner, Günter M. Ziegler : The book of evidence . Springer-Verlag, 2010, Chapter 30 - Cayley's formula for the number of trees , p. 227-233 .
• Borchardt, CW: About an interpolation formula for a kind of symmetrical functions and about their application . In: Math. Abh. Of the Academy of Sciences in Berlin . 1860, pp. 1-20.
• A. Cayley: A theorem on trees . In: Quart. J. Math . 23, 1889, pp. 376-378.