组合数学 (Spring 2013)/Cayley's formula

Cayley's Formula

We now present a theorem of the number of labeled trees on a fixed number of vertices. It is due to Cayley in 1889. The theorem is often referred by the name Cayley's formula.

Cayley's formula for trees

There are [math]\displaystyle{ n^{n-2} }[/math] different trees on [math]\displaystyle{ n }[/math] distinct vertices.

The theorem has several proofs. Classical methods include the bijection which encodes a tree by a Prüfer code, through the Kirchhoff's matrix tree theorem, and by double counting.

Prüfer code

The Prüfer code encodes a labeled tree to a sequence of labels. This gives a bijections between trees and tuples.

In a tree, the vertices of degree 1 are called leaves. It is easy to see that:

• each tree has at least two leaves; and
• after removing a leaf (along with the edge adjacent to it) from a tree, the resulting graph is still a tree.

The following algorithm transforms a tree [math]\displaystyle{ T }[/math] of [math]\displaystyle{ n }[/math] vertices [math]\displaystyle{ 1,2,\ldots,n }[/math], to a tuple [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2})\in\{1,2,\ldots,n\}^{n-2} }[/math].

Prüfer code (encoder)

Input: A tree [math]\displaystyle{ T }[/math] of [math]\displaystyle{ n }[/math] distinct vertices, labeled by [math]\displaystyle{ 1,2,\ldots,n }[/math]. let [math]\displaystyle{ T_1=T }[/math]; for [math]\displaystyle{ i=1 }[/math] to [math]\displaystyle{ n-1 }[/math], do let [math]\displaystyle{ u_i }[/math] be the leaf in [math]\displaystyle{ T_i }[/math] with the smallest label, and [math]\displaystyle{ v_i }[/math] be its neighbor; let [math]\displaystyle{ T_{i+1} }[/math] be the new tree obtained from deleting the leaf [math]\displaystyle{ u_i }[/math] from [math]\displaystyle{ T_i }[/math]; end return [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2}) }[/math];

It is trivial to observe the following lemma:

Lemma 1

For each [math]\displaystyle{ 1\le i\le n-1 }[/math], [math]\displaystyle{ T_i }[/math] is a tree of [math]\displaystyle{ n-i+1 }[/math] vertices. In particular, the vertices of [math]\displaystyle{ T_i }[/math] are [math]\displaystyle{ u_i,u_{i+1},\ldots,u_{n-1},v_{n-1} }[/math], and the edges of [math]\displaystyle{ T_i }[/math] are precisely [math]\displaystyle{ \{u_j,v_j\} }[/math], [math]\displaystyle{ i\le j\le n-1 }[/math].

And there is a reason that we do not need to store [math]\displaystyle{ v_{n-1} }[/math] in the Prüfer code.

Lemma 2

It always holds that [math]\displaystyle{ v_{n-1}=n }[/math].

Proof. Every tree (of at least two vertices) has at least two leaves. The [math]\displaystyle{ u_i }[/math], [math]\displaystyle{ 1\le i\le n-1 }[/math], are the leaf of the smallest label in [math]\displaystyle{ T_i }[/math], which can never be [math]\displaystyle{ n }[/math], thus [math]\displaystyle{ n }[/math] is never deleted. [math]\displaystyle{ \square }[/math]

Lemma 1 and 2 together imply that given a Prüfer code [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2}) }[/math], the only remaining task to reconstruct the tree [math]\displaystyle{ T }[/math] is to figure out those [math]\displaystyle{ u_i }[/math], [math]\displaystyle{ 1\le i\le n-1 }[/math]. The following lemma state how to obtain [math]\displaystyle{ u_i }[/math], [math]\displaystyle{ 1\le i\le n-1 }[/math], from a Prüfer code [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2}) }[/math].

Lemma 3

For [math]\displaystyle{ i=1,2,\ldots,n-1 }[/math], [math]\displaystyle{ u_i }[/math] is the smallest element of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] not in [math]\displaystyle{ \{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\} }[/math].

Proof. Note that [math]\displaystyle{ u_1,u_2,\ldots,u_{n-1},v_{n-1} }[/math] is a sequence of distinct vertices, because [math]\displaystyle{ u_1,u_2,\ldots,u_{n-1} }[/math] are deleted one by one from the tree, and [math]\displaystyle{ v_{n-1}=n }[/math] is never deleted. Thus, each vertex [math]\displaystyle{ v }[/math] appears among [math]\displaystyle{ u_1,u_2,\ldots,u_{n-1},v_{n-1} }[/math] exactly once. And each vertex [math]\displaystyle{ v }[/math] appears for [math]\displaystyle{ deg(v) }[/math] times among the edges [math]\displaystyle{ \{u_i,v_i\} }[/math], [math]\displaystyle{ 1\le i\le n-1 }[/math], where [math]\displaystyle{ deg(v) }[/math] denotes the degree of vertex [math]\displaystyle{ v }[/math] in the original tree [math]\displaystyle{ T }[/math]. Therefore, each vertex [math]\displaystyle{ v }[/math] appears among [math]\displaystyle{ v_1,v_2,\ldots,v_{n-2} }[/math] for [math]\displaystyle{ deg(v)-1 }[/math] times. Similarly, each vertex [math]\displaystyle{ v }[/math] of [math]\displaystyle{ T_i }[/math] appears among [math]\displaystyle{ v_i,v_{i+1},\ldots,v_{n-2} }[/math] for [math]\displaystyle{ deg_i(v)-1 }[/math] times, where [math]\displaystyle{ deg_i(v) }[/math] is the degree of vertex [math]\displaystyle{ v }[/math] in the tree [math]\displaystyle{ T_i }[/math]. In particular, the leaves of [math]\displaystyle{ T_i }[/math] are not among [math]\displaystyle{ \{v_i,v_{i+1},\ldots,v_{n-2}\} }[/math]. Recall that the vertices of [math]\displaystyle{ T_i }[/math] are [math]\displaystyle{ u_i,u_{i+1},\ldots,u_{n-1},v_{n-1} }[/math]. Then the leaves of [math]\displaystyle{ T_i }[/math] are the elements of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] not in [math]\displaystyle{ \{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\} }[/math]. By definition of Prüfer code, [math]\displaystyle{ u_i }[/math] is the leaf in [math]\displaystyle{ T_i }[/math] of smallest label, hence the smallest element of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] not in [math]\displaystyle{ \{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\} }[/math]. [math]\displaystyle{ \square }[/math]

Applying Lemma 3, we have the following decoder for the Prüfer code:

Prüfer code (decoder)

Input: A tuple [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2})\in\{1,2,\ldots,n\}^{n-2} }[/math]. let [math]\displaystyle{ T }[/math] be empty graph, and [math]\displaystyle{ v_{n-1}=n }[/math]; for [math]\displaystyle{ i=1 }[/math] to [math]\displaystyle{ n-1 }[/math], do let [math]\displaystyle{ u_i }[/math] be the smallest label not in [math]\displaystyle{ \{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\} }[/math]; add an edge [math]\displaystyle{ \{u_i,v_i\} }[/math] to [math]\displaystyle{ T }[/math]; end return [math]\displaystyle{ T }[/math];

In other words, the encoding of trees to tuples by the Prüfer code is reversible, thus the mapping is injective (1-1). To see it is also surjective, we need to show that for every possible [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2})\in\{1,2,\ldots,n\}^{n-2} }[/math], the above decoder recovers a tree from it.

It is easy to see that the decoder always returns a graph of [math]\displaystyle{ n-1 }[/math] edges on the [math]\displaystyle{ n }[/math] vertices. The only thing remaining to verify is that the returned graph has no cycle in it, which can be easily proved by a timeline argument (left as an exercise).

Therefore, the Prüfer code establishes a bijection between the set of trees on [math]\displaystyle{ n }[/math] distinct vertices and the tuples from [math]\displaystyle{ \{1,2,\ldots,n\}^{n-2} }[/math]. This proves Cayley's formula.

Kirchhoff's Matrix-Tree Theorem

Given an undirected graph [math]\displaystyle{ G([n],E) }[/math], the adjacency matrix [math]\displaystyle{ A }[/math] of graph [math]\displaystyle{ G }[/math] is an [math]\displaystyle{ n\times n }[/math] matrix such that

[math]\displaystyle{ A(i,j)=\begin{cases} 1 & \{i,j\}\in E,\\ 0 & \{i,j\}\not\in E. \end{cases} }[/math]

Let [math]\displaystyle{ D }[/math] be a [math]\displaystyle{ n\times n }[/math] diagonal matrix such that

[math]\displaystyle{ D(i,j)=\begin{cases} \text{deg}(i) & i=j,\\ 0 & i\neq j, \end{cases} }[/math]

where [math]\displaystyle{ \text{deg}(i) }[/math] denotes the degree of vertex [math]\displaystyle{ i }[/math].

The Laplacian matrix [math]\displaystyle{ L }[/math] of graph [math]\displaystyle{ G }[/math] is defined as [math]\displaystyle{ L=D-A }[/math], that is,

[math]\displaystyle{ L(i,j)=\begin{cases} \text{deg}(i) & i=j,\\ -1 & i\neq j\text{ and } \{i,j\}\in E,\\ 0 & \text{otherwise}. \end{cases} }[/math]

Suppose [math]\displaystyle{ G([n],E) }[/math] has [math]\displaystyle{ m }[/math] edges. The incidence matrix [math]\displaystyle{ B }[/math] of graph [math]\displaystyle{ G }[/math] is an [math]\displaystyle{ n\times m }[/math] matrix such that

[math]\displaystyle{ \forall i\in[n], \forall e\in E,\quad B(i,e)=\begin{cases} 1 & e=\{i,j\}\text{ and } i\lt j,\\ -1 & e=\{i,j\}\text{ and } i\gt j,\\ 0 & \text{otherwise}. \end{cases} }[/math]

The following proposition is easy to verify.

Proposition

[math]\displaystyle{ L=BB^T }[/math].

Proof. For any [math]\displaystyle{ i,j\in[n] }[/math], we have [math]\displaystyle{ (BB^T)(i,j)=\sum_{e\in E}B(i,e)B^T(e,j)=\sum_{e\in E}B(i,e)B(j,e) }[/math]. It is easy to verify that [math]\displaystyle{ \sum_{e\in E}B(i,e)B(j,e)= \begin{cases} \text{deg}(i) & i=j,\\ -1 & i\neq j\text{ and } \{i,j\}\in E,\\ 0 & \text{otherwise}, \end{cases} }[/math] which is equal to the definition of [math]\displaystyle{ L }[/math]. [math]\displaystyle{ \square }[/math]