math lessons - 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

Mathematics Encyclopedia and Lessons

Lessons

Popular
Subjects

References

Cayley's formula

Proof of the formula

Note

Mathematics Encyclopedia and Lessons

Lessons

Popular Subjects

References

Cayley's formula

Proof of the formula

Note

Popular
Subjects