Cayley's formula

From Wikipedia, the free encyclopedia

The complete list of all trees on 2,3,4 labeled verices:

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 a positive integer, the number of trees on n labeled vertices is

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

It is a particular case of Kirchhoff's theorem.

[edit] 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 $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 $2 n$ , $\exists k\in\{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:

$d(v_{j}) = \begin{cases} \mbox{d}_{j}, & \mbox{if }j \neq i \\ \mbox{d}_{j}-1, & \mbox{if }j=i \end{cases}$

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

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

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

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

$|\mathcal{B}_{i}| = \begin{cases} 0, & \mbox{if }d_{i}=1 \\ \frac{(n-3)!}{(d_{1}-1)!\cdots(d_{i}-2)!\cdots(d_{n-1}-1)!}, & \mbox{otherwise} \end{cases}$ 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 $2 n - 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 $2 n - 2$ . To count the total number of trees on $n$ vertices, then, we simply sum over possible degree lists. Thus, we have: