= Cayley's formula
{c}
{title2=$n^{n-2}$}
{wiki}
= Cayley formula
{c}
{synonym}
For an integer $n\geq2$, let $\mathcal T_n$ be the set of <labelled trees> with fixed <vertex set> $\{1,\ldots,n\}$. Each <tree> is a finite <simple graph>, with no distinguished <root of a tree>, and two <trees> are different exactly when their sets of <edges> differ. Then
$$
|\mathcal T_n|=n^{n-2}.
$$
Equivalently, this is the number of <spanning trees> of the <complete graph> $K_n$. The <labelled combinatorial structure> includes the fixed labels: drawings, positions, and the order in which <edges> are listed do not create extra <trees>. For $n=1$, the single <vertex> with no <edges> is the unique <tree>; count it separately, since the <Prüfer sequence> construction requires $n\geq2$. For $n=2$, the unique <tree> has <edge> $\{1,2\}$ and corresponds to the empty <Prüfer sequence>. https://users.math.msu.edu/users/magyarp/math481/[Peter Magyar, Michigan State University, Math 481: Cayley's theorem and inverse Prüfer transformations]{ref}
For four fixed labels, there are $4^2=16$ <labelled trees>, but only two <unlabelled trees>: the <star graph> and the <path graph>. There are four <star graphs>, one for each choice of centre. There are $4!/2=12$ <path graphs>: arrange the labels along a <graph path>, then identify each ordering with its reversal, which describes the same set of <edges>. Thus $4+12=16$. For instance, <star graphs> centred at $1$ and at $2$ have different sets of <edges> even though they have the same shape.
\Image[/labelled-trees-on-four-vertices.png]
{title=All sixteen <labelled trees> on four fixed <vertices>: four <star graphs> and twelve <path graphs>, each with its <Prüfer sequence>}
The striking point is that connectedness and the absence of a <graph cycle> are global restrictions on <edges>, yet the answer is a power with no correction factor. The <Prüfer sequence> supplies a <bijection> that turns those restrictions into $n-2$ freely chosen labels. The <rule of product> then gives $n^{n-2}$ immediately. The same representation makes <vertex degrees> easy to count and supports <uniform labelled tree generation> for simulations and algorithm experiments.
Arthur Cayley's 1889 paper "A theorem on trees", published in the Quarterly Journal of Pure and Applied Mathematics, volume 23, pages 376–378, treats the counting problem and its refinement by <vertex degrees>. It was reprinted as paper 895 in volume XIII of his Collected Mathematical Papers, pages 26–28. This publication is the historical context for the name <Cayley's formula>; the name alone is not a claim of priority. https://gdz.sub.uni-goettingen.de/id/PPN600494829_0023[Cayley, A theorem on trees (1889), original journal volume, pages 376–378]{ref} https://doi.org/10.1017/CBO9780511703799.010[Cayley, A theorem on trees, collected-paper reprint and publisher's first-page preview]{ref}
Back to article page
