- Cayley's formula
In
mathematics , Cayley's formula is a result ingraph theory named afterArthur 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 .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 mbox{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 2n, exists kin{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}) = egin{cases} mbox{d}_{j}, & mbox{if }j eq 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 v_{i}, v_{n}}, and if mbox{d}_{i} = 1, then mathcal{B}_{i} = emptyset.
Since v_{n} 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 mbox{d}_{i} > 1) or our previous note (if mbox{d}_{i} = 1, then mathcal{B}_{i} = emptyset) to find mathcal{B}_{i}|:
:mathcal{B}_{i}| = egin{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 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 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 sequence s yield one of the many alternate proofs of Cayley's formula.
Wikimedia Foundation. 2010.