Cayley's formula

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

In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that if "n" is an integer bigger than 1, the number of trees on "n" labeled vertices is

:$n^\{n-2\}.,$

It is a particular case of Kirchhoff's theorem.

Proof of the formula

Let $T\_\{n\}$ be the set of trees possible on the vertex set $\{v\_\{1\},\; v\_\{2\},ldots,\; v\_\{n\}\}$. We seek to show that

:$|T\_\{n\}|\; =\; n^\{n-2\}$.

We begin by proving a lemma:

Claim: Let $d\_\{1\},\; d\_\{2\},\; ldots,\; d\_\{n\}$ be positive integers such that $sum\_\{i=1\}^\{n\}d\_\{i\}\; =\; 2n-2$. Let $mathcal\{A\}$ be the set of trees on the vertex set $\{v\_\{1\},\; v\_\{2\},ldots,\; v\_\{n\}\}$ such that the degree of $v\_\{i\}$ (denoted $mbox\{d\}(v\_\{i\})$) is $d\_\{i\}$ for $i\; =\; 1,\; 2,ldots,\; n$. Then

:$|mathcal\{A\}|\; =\; frac\{(n-2)!\}\{(d\_\{1\}-1)!(d\_\{2\}-1)!cdots(d\_\{n\}-1)!\}.$

Proof:We go by induction on $n$. For $n=1$ and $n=2$ the proposition holds trivially and is easy to verify. We move to the inductive step. Assume $n>2$ and that the claim holds for degree sequences on $n-1$ vertices. Since the $d\_\{i\}$ are all positive but their sum is less than $2n$, $exists\; kin\{1,2,ldots,n\}$ such that $d\_\{k\}\; =\; 1$. Assume without loss of generality that $d\_\{n\}\; =\; 1.$

For $i\; =\; 1,\; 2,\; ldots,\; n-1$ let $mathcal\{B\}\_\{i\}$ be the set of trees on the vertex set $\{v\_\{1\},\; v\_\{2\},\; ldots\; v\_\{n-1\}\; \}$ such that:

:

where $d(v)$ is the degree of $v$.

Trees in $mathcal\{B\}\_\{i\}$ correspond to trees in $mathcal\{A\}$ with the edge $\{v\_\{i\},\; v\_\{n\}\}$, and if $mbox\{d\}\_\{i\}\; =\; 1$, then $mathcal\{B\}\_\{i\}\; =\; emptyset.$

Since $v\_\{n\}$ must have been connected to some node in every tree in $mathcal\{A\}$, we have that

:$|mathcal\{A\}|\; =\; sum\_\{i=1\}^\{n-1\}|mathcal\{B\}\_\{i\}|.$

Further, for a given $i$ we can apply either the inductive assumption (if $mbox\{d\}\_\{i\}\; >\; 1$) or our previous note (if $mbox\{d\}\_\{i\}\; =\; 1$, then $mathcal\{B\}\_\{i\}\; =\; emptyset$) to find $|mathcal\{B\}\_\{i\}|$:

: for $i=1,2,ldots,n-1$

Observing that

:$frac\{(n-3)!\}\{(d\_\{1\}-1)!cdots(d\_\{i\}-2)!cdots(d\_\{n-1\}-1)!\}\; =\; frac\{(n-3)!(d\_\{i\}-1)\}\{(d\_\{1\}-1)!cdots(d\_\{n-1\}-1)!\}$
it becomes clear that, in either case, $|mathcal\{B\}\_\{i\}|\; =\; frac\{(n-3)!(d\_\{i\}-1)\}\{(d\_\{1\}-1)!cdots(d\_\{n-1\}-1)!\}.$

So we have

::$|mathcal\{A\}|\; =\; sum\_\{i=1\}^\{n-1\}|mathcal\{B\}\_\{i\}|$

:$=sum\_\{i=1\}^\{n-1\}frac\{(n-3)!(d\_\{i\}-1)\}\{(d\_\{1\}-1)!cdots(d\_\{n-1\}-1)!\}$

:$=frac\{(n-3)!\}\{(d\_\{1\}-1)!cdots(d\_\{n-1\}-1)!\}sum\_\{i=1\}^\{n-1\}(d\_\{i\}-1).$

And since $d\_\{n\}\; =\; 1$ and $sum\_\{i=1\}^\{n\}d\_\{i\}\; =\; 2n-2$, we have:

:$|mathcal\{A\}|\; =\; frac\{(n-3)!\}\{(d\_\{1\}-1)!cdots(d\_\{n\}-1)!\}(n-2)\; =\; frac\{(n-2)!\}\{(d\_\{1\}-1)!cdots(d\_\{n\}-1)!\}$

which proves the lemma.

We have shown that given a particular list of positive integers $d\_\{1\},\; d\_\{2\},\; ldots,\; d\_\{n\}$ such that the sum of these integers is $2n-2$, we can find the number of trees with labeled vertices of these degrees. Since every tree on $n$ vertices has $n-1$ edges, the sum of the degrees of the vertices in an $n$-vertex tree is always $2n-2$. To count the total number of trees on $n$ vertices, then, we simply sum over possible degree lists. Thus, we have:

:$|T\_\{n\}|\; =\; sum\_\{d\_\{1\}+d\_\{2\}+cdots+d\_\{n\}\; =\; 2n-2\}\; frac\{(n-2)!\}\{(d\_\{1\}-1)!cdots(d\_\{n\}-1)!\}.$

If we reindex with $k\_\{i\}=d\_\{i\}-1$ for $i=1,2,ldots,n$, we have:

:$|T\_\{n\}|\; =\; sum\_\{k\_\{1\}+k\_\{2\}+cdots+k\_\{n\}\; =\; n-2\}\; frac\{(n-2)!\}\{k\_\{1\}!cdots\; k\_\{n\}!\}.$

Finally, we can apply the multinomial theorem to find:

:$|T\_\{n\}|\; =\; n^\{n-2\}$

as expected. $Box$

Note

Prüfer sequences yield one of the many alternate proofs of Cayley's formula.