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

<math>n^{n-2}\,<math>.

It is a particular case of Kirchhoff's theorem.

Proof of the formula

Let <math>T_{n}<math> be the set of trees possible on the vertex set <math>\{v_{1}, v_{2},\ldots, v_{n}\}<math>. We seek to show that <math>|T_{n}| = n^{n-2}<math>.

We begin by proving a lemma:

Claim: Let <math> d_{1}, d_{2}, \ldots, d_{n} <math> be positive integers such that <math> \sum_{i=1}^{n}d_{i} = 2n-2 <math>. Let <math>\mathcal{A}<math> be the set of trees on the vertex set <math>\{v_{1}, v_{2},\ldots, v_{n}\}<math> such that the degree of <math>v_{i}<math> (denoted <math>\mbox{d}(v_{i})<math>) is <math>d_{i}<math> for <math>i = 1, 2,\ldots, n<math>. Then

<math>|\mathcal{A}| = \frac{(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots(d_{n}-1)!}.<math>

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

For <math>i = 1, 2, \ldots, n-1<math> let <math>\mathcal{B}_{i}<math> be the set of trees on the vertex set <math>\{v_{1}, v_{2}, \ldots v_{n-1} \}<math> such that:

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

Note that trees in <math>\mathcal{B}_{i}<math> correspond to trees with the edge <math>\{v_{i}, v_{n}\}<math> and that if <math>\mbox{d}_{i} = 1<math>, then <math>\mathcal{B}_{i} = \phi.<math>

Since <math>v_{n}<math> must have been connected to some node in every tree in <math>\mathcal{A}<math>, we have that

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

Further, for a given <math>i<math> we can apply either the inductive assumption or our previous note to find <math>|\mathcal{B}_{i}|<math>:

<math>|\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}<math>      for <math>i=1,2,\ldots,n-1<math>

Observing that

<math>\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)}<math>

it becomes clear that, in either case, <math>|\mathcal{B}_{i}| = \frac{(n-3)!(d_{i}-1)}{(d_{1}-1)!\cdots(d_{n-1}-1)}.<math>

So we have

<math>|\mathcal{A}| = \sum_{i=1}^{n-1}|\mathcal{B}_{i}|<math>

<math>=\sum_{i=1}^{n-1}\frac{(n-3)!(d_{i}-1)}{(d_{1}-1)!\cdots(d_{n-1}-1)!} <math>

<math>=\frac{(n-3)!}{(d_{1}-1)!\cdots(d_{n-1}-1)!}\sum_{i=1}^{n-1}(d_{i}-1).<math>

And since <math>d_{n} = 1<math> and <math>\sum_{i=1}^{n}d_{i} = 2n-2<math>, we have:

<math>|\mathcal{A}| = \frac{(n-3)!}{(d_{1}-1)!\cdots(d_{n}-1)!}(n-2) = \frac{(n-2)!}{(d_{1}-1)!\cdots(d_{n}-1)!}<math>

which proves the lemma.

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

<math>|T_{n}| = \sum_{d_{1}+d_{2}+\cdots+d_{n} = 2n-2} \frac{(n-2)!}{(d_{1}-1)!\cdots(d_{n}-1)!}.<math>

If we reindex with <math>k_{i}=d_{i}-1<math> for <math>i=1,2,\ldots,n<math>, we have:

<math>|T_{n}| = \sum_{k_{1}+k_{2}+\cdots+k_{n} = n-2} \frac{(n-2)!}{k_{1}!\cdots k_{n}!}.<math>

Finally, we can apply the multinomial theorem to find:

<math>|T_{n}| = n^{n-2}<math>

as expected. <math>\Box<math>

Note

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