View source for 组合数学 (Spring 2016)/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 [http://en.wikipedia.org/wiki/Arthur_Cayley Cayley] in 1889. The theorem is often referred by the name [http://en.wikipedia.org/wiki/Cayley's_formula Cayley's formula].

{{Theorem|Cayley's formula for trees|
: There are <math>n^{n-2}</math> different trees on <math>n</math> distinct vertices.
}}

The theorem has several proofs, including the bijection which encodes a tree by a [http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence Prüfer code], through the [http://en.wikipedia.org/wiki/Kirchhoff's_matrix_tree_theorem Kirchhoff's matrix tree theorem], and by double counting.

=== Proof of Cayley's formula by double counting ===
We now present a double counting proof, which is considered by the [http://en.wikipedia.org/wiki/Proofs_from_THE_BOOK Proofs from THE BOOK] "the most beautiful of them all".
{{Prooftitle|Proof of Cayley's formula by double counting|
(Due to Pitman 1999)

Let <math>T_n</math> be the number of different trees defined on <math>n</math> distinct vertices.

A '''rooted tree''' is a tree with a special vertex. That is, one of the <math>n</math> vertices is marked as the "root" of the tree. A rooted tree defines a natural direction of all edges, such that an edge <math>uv</math> of the tree is directed from <math>u</math> to <math>v</math> if <math>u</math> is before <math>v</math> along the unique path from the root.

We count the number of different ''sequences'' of directed edges that can be added to an empty graph on <math>n</math> vertices to form from it a ''rooted'' tree. We note that such a sequence can be formed in two ways:
# Starting with an unrooted tree, choose one of its vertices as root, and fix an total order of edges to specify the order in which the edges are added.
# Starting from an empty graph, add the edges one by one in steps.

In the first method, we pick one of the <math>T_n</math> unrooted trees, choose one of the <math>n</math> vertices as the root, and pick one of the <math>(n-1)!</math> total orders of the <math>n-1</math> edges. This gives us <math>T_nn(n-1)!=T_nn!</math> ways.

In the second method, we consider the number of choices in one step, and multiply the numbers of choices in all steps. This is done as follows.

Given a sequence of ''adding'' <math>n-1</math> edges to an empty graph to form a rooted tree, we reverse this sequence and get a sequence of ''removing'' edges one by one from the final rooted tree until no edge left. We observe that:
* At first, we remove an edge from the rooted tree. Suppose that the root of the tree is <math>r</math>, and the removed directed edge is <math>(u,v)</math>.  After removing <math>(u,v)</math>, the original rooted tree is disconnected into two rooted trees, one rooted at <math>r</math> and the other rooted at <math>v</math>.
* After removing <math>k-1</math> edges, there are <math>k</math> rooted trees. In the <math>k</math>th step, a directed edge <math>(u,v)</math> in the current forest is removed and the tree containing <math>(u,v)</math> is disconnected into two trees, one rooted at the old root of that tree, and the other rooted at <math>v</math>.

We now again reverse the above procedure, and consider the sequence of adding directed edges to an empty graph to form a rooted tree.
* At first, we have <math>n</math> rooted trees, each of 0 edge (<math>n</math> isolated vertices).
* After adding <math>n-k</math> edges, there are <math>k</math> rooted trees. Denoting the directed edge added next as <math>(u,v)</math>. As observed above, <math>u</math> can be any one of the <math>n</math> vertices; but <math>v</math> must be the root of one of the <math>k</math> trees, except the tree which contains <math>u</math>. There are <math>n(k-1)</math> choices of such <math>(u,v)</math>.
Multiplying the numbers of choices in all steps, the number of sequences of adding directed edges to an empty graph to form a rooted tree is given by
:<math>\prod_{k=2}^nn(k-1)=n^{n-2}n!</math>.

By the principle of double counting, counting the same thing by different methods yield the same result.
:<math>T_nn!=n^{n-2}n!</math>,
which gives that <math>T_n=n^{n-2}</math>.
}}

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

=== Encoding  ===
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>T</math> of <math>n</math> vertices <math>1,2,\ldots,n</math>, to a tuple <math>(v_1,v_2,\ldots,v_{n-2})\in\{1,2,\ldots,n\}^{n-2}</math>.
{{Theorem| Prüfer code (encoder)|
:'''Input''': A tree <math>T</math> of <math>n</math> distinct vertices, labeled by <math>1,2,\ldots,n</math>.
:
:let <math>T_1=T</math>;
:for <math>i=1</math> to <math>n-1</math>, do
::let <math>u_i</math> be the leaf in <math>T_i</math> with the smallest label, and <math>v_i</math> be its neighbor;
::let <math>T_{i+1}</math> be the new tree obtained from deleting the leaf <math>u_i</math> from <math>T_i</math>;
:end
:return <math>(v_1,v_2,\ldots,v_{n-2})</math>;
}}

=== Decoding ===
It is trivial to observe the following lemma:
{{Theorem|Lemma 1|
:For each <math>1\le i\le n-1</math>, <math>T_i</math> is a tree of <math>n-i+1</math> vertices. In particular, the vertices of <math>T_i</math> are  <math>u_i,u_{i+1},\ldots,u_{n-1},v_{n-1}</math>, and the edges of <math>T_i</math> are precisely <math>\{u_j,v_j\}</math>, <math>i\le j\le n-1</math>.
}}

And there is a reason that we do not need to store <math>v_{n-1}</math> in the Prüfer code.
{{Theorem|Lemma 2|
:It always holds that <math>v_{n-1}=n</math>.
}}
{{Proof|
Every tree (of at least two vertices) has at least two leaves. The <math>u_i</math>, <math>1\le i\le n-1</math>, are the leaf of the smallest label in <math>T_i</math>, which can never be <math>n</math>, thus <math>n</math> is never deleted.
}}

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

{{Theorem|Lemma 3|
:For <math>i=1,2,\ldots,n-1</math>, <math>u_i</math> is the smallest element of <math>\{1,2,\ldots,n\}</math> not in <math>\{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\}</math>.
}}
{{Proof|
Note that <math>u_1,u_2,\ldots,u_{n-1},v_{n-1}</math> is a sequence of distinct vertices, because <math>u_1,u_2,\ldots,u_{n-1}</math> are deleted one by one from the tree, and <math>v_{n-1}=n</math> is never deleted. Thus, each vertex <math>v</math> appears among <math>u_1,u_2,\ldots,u_{n-1},v_{n-1}</math> exactly once. And each vertex <math>v</math> appears for <math>deg(v)</math> times among the edges <math>\{u_i,v_i\}</math>, <math>1\le i\le n-1</math>, where <math>deg(v)</math> denotes the degree of vertex <math>v</math> in the original tree <math>T</math>. Therefore, each vertex <math>v</math> appears among  <math>v_1,v_2,\ldots,v_{n-2}</math> for <math>deg(v)-1</math> times.

Similarly, each vertex <math>v</math> of <math>T_i</math> appears among <math>v_i,v_{i+1},\ldots,v_{n-2}</math> for <math>deg_i(v)-1</math> times, where <math>deg_i(v)</math> is the degree of vertex <math>v</math> in the tree <math>T_i</math>. In particular, the leaves of <math>T_i</math> are not among <math>\{v_i,v_{i+1},\ldots,v_{n-2}\}</math>. Recall that the vertices of <math>T_i</math> are <math>u_i,u_{i+1},\ldots,u_{n-1},v_{n-1}</math>. Then the leaves of <math>T_i</math> are the elements of <math>\{1,2,\ldots,n\}</math> not in <math>\{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\}</math>. By definition of Prüfer code, <math>u_i</math> is the leaf in <math>T_i</math> of smallest label, hence the smallest element of <math>\{1,2,\ldots,n\}</math> not in <math>\{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\}</math>.
}}

Applying Lemma 3, we have the following decoder for the Prüfer code:
{{Theorem| Prüfer code (decoder)|
:'''Input''': A tuple <math>(v_1,v_2,\ldots,v_{n-2})\in\{1,2,\ldots,n\}^{n-2}</math>.
:
:let <math>T</math> be empty graph, and <math>v_{n-1}=n</math>;
:for <math>i=1</math> to <math>n-1</math>, do
::let <math>u_i</math> be the smallest label not in <math>\{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\}</math>;
::add an edge <math>\{u_i,v_i\}</math> to <math>T</math>;
:end
:return <math>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>(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>n-1</math> edges on the <math>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).

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

== Kirchhoff's Matrix-Tree Theorem ==
Given an undirected graph <math>G([n],E)</math>, the '''adjacency matrix''' <math>A</math> of graph <math>G</math> is an <math>n\times n</math> matrix such that
:<math>A(i,j)=\begin{cases}
1 & \{i,j\}\in E,\\
0 & \{i,j\}\not\in E.
\end{cases}</math>

=== Graph Laplacian===
Let <math>D</math> be a <math>n\times n</math> diagonal matrix such that
:<math>D(i,j)=\begin{cases}
\text{deg}(i) & i=j,\\
0 & i\neq j,
\end{cases}</math>
where <math>\text{deg}(i)</math> denotes the degree of vertex <math>i</math>.

The '''Laplacian matrix''' <math>L</math> of graph <math>G</math> is defined as <math>L=D-A</math>, that is,
:<math>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>G([n],E)</math> has <math>m</math> edges. The '''incidence matrix''' <math>B</math> of graph <math>G</math> is an <math>n\times m</math> matrix such that
:<math>
\forall i\in[n], \forall e\in E,\quad B(i,e)=\begin{cases}
1 & e=\{i,j\}\text{ and } i<j,\\
-1 & e=\{i,j\}\text{ and } i>j,\\
0 & \text{otherwise}.
\end{cases}
</math>

The following proposition is easy to verify.
{{Theorem|Proposition|
:<math>L=BB^T</math>.
}}
{{Proof|
For any <math>i,j\in[n]</math>, we have
:<math>(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>
\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>L</math>.
}}

=== The Matrix-tree Theorem ===
The matrix-tree theorem of Kirchhoff states a striking fact: The number of spanning trees in any connected graph can be computed as the determinant of some appropriate graph matrix. 
{{Theorem|Kirchhoff's Matrix-Tree Theorem|
:For any connected graph <math>G</math> of <math>n</math> vertices, the number of spanning trees in <math>G</math> is <math>\det(L_{i,i})\,</math> for all <math>i\in[n]</math>, where <math>L_{i,i}\,</math> is the <math>(n-1)\times(n-1)</math> matrix resulting from the Laplacian matrix <math>L</math> of graph <math>G</math> by deleting the <math>i</math>-th row and the <math>i</math>-th column.
}}
The determinant can be computed as fast as matrix multiplication, thus is quite efficient, especially when compared to our task: counting the number of subgraphs satisfying certain nontrivial global constraint (e.g. spanning tree). Such efficient algorithm is rarely seen for counting problems, which are usually #P-hard to compute (e.g. number of matchings in a graph).

The key to prove the matrix-tree theorem is the Cauchy-Binet theorem in linear algebra, whose proof is beyond the scope of this class.
{{Theorem|Cauchy-Binet Theorem|
:Let <math>A</math> and <math>B</math> be, respectively, <math>n\times m</math> and <math>m\times n</math> matrix. For any <math>S\subseteq [m]</math> of size <math>n</math>, let <math>A_{[n], S}</math> and <math>B_{S,[n]}</math> denote, respectively, the <math>n\times n</math> submatrices of <math>A</math> and <math>B</math>, consisting of the columns of <math>A</math>, or the rows of <math>B</math>, indexed by elements of <math>S</math>. Then
::<math>\det(AB)=\sum_{S\in{[m]\choose n}}\det(A_{[n],S})\det(B_{S,[n]}).</math>
}}

Let <math>B</math> be the incidence matrix of graph <math>G</math>. Fix any vertex <math>i</math>, let <math>C</math> be the <math>(n-1)\times m</math> matrix resulting from <math>B</math> by deleting the <math>i</math>-th row. 

Recall that <math>L=BB^T</math>. It is easy to verify that
:<math>
L_{i,i}=CC^T.
</math>

Due to the Cauchy-Binet Theorem, we have
:<math>
\begin{align}
\det(L_{i,i})=\det(CC^T)
&=\sum_{S\in{[m]\choose n-1}}\det(C_{[n-1],S})\det(C^T_{S,[n-1]})\\
&=\sum_{S\in{[m]\choose n-1}}\det(C_{[n-1],S})^2.
\end{align}</math>

The next lemma gives a key observation to prove the matrix-tree theorem.
{{Theorem|Lemma|
:For any <math>S\subseteq [m]</math> of size <math>n-1</math>, the value of <math>\det(C_{[n-1],S})</math> is either 1, or -1, or 0. Moreover, <math>\det(C_{[n-1],S})=\pm1</math> if and only if <math>S</math> indicates a spanning tree in <math>G</math>.
}}
{{Proof|
We first show <math>\det(C_{[n-1],S})\in\{0,1,-1\}</math> by induction on <math>n</math>. 
Note that <math>C_{[n-1],S}</math> is an <math>(n-1)\times (n-1)</math> matrix such that each column contains at most one 1 and at most one -1, and all other entries are 0. For such matrix, when <math>n-1=1</math>, the induction hypothesis <math>\det(C_{[n-1],S})\in\{0,1,-1\}</math> is trivially true. And for general <math>n</math>, if every column has a 1 and a -1, then the sum of all rows is the zero vector, so the matrix is singular.  Otherwise, expand the determinant by a column with one nonzero entry to find it is <math>\pm1</math> times the determinant of a smaller matrix of the same property, which by induction hypothesis has value 0 or <math>\pm1</math>.

We then show that <math>\det(C_{[n-1],S})</math> is nonzero if and only if <math>S</math> is a spanning tree. 

Suppose the <math>n-1</math> edges corresponding to <math>S</math> is not a spanning tree of <math>G</math>. Then <math>S</math> must have more than one components, and there must be a component <math>R</math> not containing vertex <math>i</math>. The rows of <math>C_{[n-1],S}</math> corresponding to <math>R</math> add to 0, thus these rows are linearly dependent, and hence <math>\det(C_{[n-1],S})=0</math>.

Suppose the <math>n-1</math> edges corresponding to <math>S</math> is a spanning tree of <math>G</math>. Then there is a vertex <math>j_1\neq i</math> of degree 1 in <math>S</math>; let <math>e_1</math> be the edge in <math>S</math> incident to <math>j_1</math>. Deleting vertex <math>j_1</math> and edge <math>e_1</math> from <math>S</math>, we obtain a tree of <math>n-2</math> edges. Again there is a vertex <math>j_2\neq i</math> of degree 1 with incident edge <math>e_2</math>. Continue this we enumerate all vertices except <math>i</math> as <math>j_1,j_2,\ldots,j_{n-1}</math> and all edges in <math>S</math> as <math>e_1,e_2,\ldots,e_{n-1}</math>. Now permute the rows and columns of <math>C_{[n-1],S}</math> such that the <math>k</math>-th row corresponds to vertex <math>j_k</math> and the <math>k</math>-th column corresponds to <math>e_k</math>. By our construction the permuted <math>C_{[n-1],S}</math> is lower triangle with <math>\pm1</math> diagonal entries, since when each <math>j_k</math> is removed it is of degree 1 in the remaining tree and is incident to edge <math>e_k</math>. Therefore, <math>\det(C_{[n-1],S})=\pm1</math>.
}}

The matrix-tree theorem follows as consequence. Recall we show that
:<math>
\begin{align}
\det(L_{i,i})
&=\sum_{S\in{[m]\choose n-1}}\det(C_{[n-1],S})^2.
\end{align}</math>
The sum enumerates over all subgraphs <math>S</math> of <math>n-1</math> edges, and by the above lemma <math>\det(C_{[n-1],S})^2=1</math> if and only if <math>S</math> is a spanning tree in <math>G</math>. Therefore, <math>\det(L_{i,i})</math> gives the number of spanning trees in <math>G</math>.

=== Cayley's formula by the matrix-tree theorem ===
The number of trees of <math>n</math> distinct vertices equals the number of spanning trees in the complete graph <math>K_n</math>. For <math>G=K_n</math>, for any <math>i\in[n]</math> the <math>(n-1)\times (n-1)</math> matrix <math>L_{ii}</math> is given by
:<math>
L_{i,i}
=
\begin{bmatrix}
n-1 & -1 & \cdots & -1\\
-1 & n-1 & \cdots & -1\\
\vdots & \vdots & \ddots & -1\\
-1 & -1 & \cdots & n-1
\end{bmatrix},
</math>
whose determinant is <math>\det(L_{i,i})=n^{n-2}</math>.