Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Cayley's formula

In mathematics, Cayley's formula is a result in graph theory. 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.

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

Note that trees in $\mathcal{B}_{i}$ correspond to trees with the edge ${v i, v n}$ and that 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 or our previous note 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. Note that, 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:

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

Categories: Graph theory

Last updated: 05-13-2005 00:10:58

Science Fair Project Encyclopedia Contents Page

10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects