Cayley's formula

From Wikipedia, the free encyclopedia

The complete list of all trees on 2,3,4 labeled vertices: 22 − 2 = 1 tree with 2 vertices, 33 − 2 = 3 trees with 3 vertices and 44 − 2 = 16 trees with 4 vertices.
The complete list of all trees on 2,3,4 labeled vertices: 22 − 2 = 1 tree with 2 vertices, 33 − 2 = 3 trees with 3 vertices and 44 − 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.

[edit] Proof of the formula

Let Tn be the set of trees possible on the vertex set \{v_{1}, v_{2},\ldots, v_{n}\}. We seek to show that

| Tn | = nn − 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 vi (denoted d(vi)) is di 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 di are all positive but their sum is less than 2n, \exists k\in\{1,2,\ldots,n\} such that dk = 1. Assume without loss of generality that dn = 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}

where d(v) is the degree of v.

Trees in \mathcal{B}_{i} correspond to trees in \mathcal{A} with the edge {vi,vn}, and if di = 1, then \mathcal{B}_{i} = \emptyset.

Since vn 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 di > 1) or our previous note (if di = 1, then \mathcal{B}_{i} = \emptyset) 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 dn = 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 ki = di − 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:

| Tn | = nn − 2

as expected. \Box

[edit] Note

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

Languages