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

\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 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

\mbox{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

2n-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

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

Prfer sequences yield one of the many alternate proofs of Cayley's formula.

<< Previous

Word Browser

Next >>

integrated facility for linux
tetratech
shelby county republican party
roman catholic archdiocese of denver
atlantic and st. lawrence railroad
klippel feil syndrome
julia davis
crystallization processes
west coast customs
united world college of the adriatic
list of christmas characters

dusty finish (professional wrestling)
st. lawrence and atlantic railroad
sender bielstein
jo ann robinson
anti bias curriculum
st. lawrence and atlantic railroad (qubec)
monty norman
sender scharteberg
forvie
proletcult theatre
kenneth montgomery keillor

english national cricket captains
tahir mirza
sands of forvie
jahrom
transmitter thurnau
rania siam
giorgio abetti
meikle
mark wilkinson
intelligent peripheral interface
yajnavalkya smriti

ipi
daskalogiannis
bodenseesender
david c. geary
the exorcist iii
thomas sanchez
meikle loch
amana colonies
amahl and the night visitors
paramotor
national organic program