The number of distinct labeled trees on n vertices is n raised to the power n minus 2. First proved by Carl Wilhelm Borchardt in 1860 and extended by Arthur Cayley in a short 1889 note, whose name became attached to the result, it is one of the cleanest exact counting formulas in combinatorics, distinct from the same mathematician's Cayley's theorem in group theory.
Facts
StatementThe number of distinct labeled trees on n vertices equals n to the power of (n minus 2); equivalently, this is the number of spanning trees of the complete graph on n labeled vertices. 1 Proof YearFirst proved by Carl Wilhelm Borchardt in 1860 via a determinant identity; Arthur Cayley extended the result in a short 1889 note that gave the formula its common name, though he credited Borchardt's original paper. Classification
Statement Form Connections
In Branch
Named After
Derived from the theorem's own name (unambiguous possessive-token match to exactly one live mathematician entity, w-bfill-g5-0924 browse backfill)
Proved By
Sources
1. Cayley's Formula (Wikipedia)
Wikimedia FoundationHistory section
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.
History section, first sentence
The formula was first discovered by Carl Wilhelm Borchardt in 1860, and proved via a determinant.
History section, first two sentences
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.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.