Cayley's formula
From Wikipedia, the free encyclopedia
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
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 . We seek to show that
- | Tn | = nn − 2.
We begin by proving a lemma:
Claim: Let be positive integers such that . Let be the set of trees on the vertex set such that the degree of vi (denoted d(vi)) is di for . Then
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, such that dk = 1. Assume without loss of generality that dn = 1.
For let be the set of trees on the vertex set such that:
where d(v) is the degree of v.
Trees in correspond to trees in with the edge {vi,vn}, and if di = 1, then
Since vn must have been connected to some node in every tree in , we have that
Further, for a given i we can apply either the inductive assumption (if di > 1) or our previous note (if di = 1, then ) to find :
- for
Observing that
it becomes clear that, in either case,
So we have
And since dn = 1 and , we have:
which proves the lemma.
We have shown that given a particular list of positive integers 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:
If we reindex with ki = di − 1 for , we have:
Finally, we can apply the multinomial theorem to find:
- | Tn | = nn − 2
as expected.
[edit] Note
Prüfer sequences yield one of the many alternate proofs of Cayley's formula.