5. Cayley's Formula

Counting Trees

How many different trees can be formed from \( n \) distinct trees?

Cayley's Formula: there are \( n^{n-2} \) trees on \( n \) distinct vertices.

Prufer Code

By removing a leaf from a tree \( T \), \( T' \) is still a tree.

Repeatedly remove \( u_i \) from tree \( T_i \) to get \( T_{i+1} \), where \( u_i \) is the smallest leaf in \( T_i \). \( u_i \) has only one edge \( (u_i, v_i) \), we get Prufer code for \( T \) with all \( v_i \)s.

2       5
|      /
4--3--1
   |   \
   6    7

u: 2,4,5,6,3,1
v: 4,3,1,3,1,7

E.g. the tree above has prufer code \( (4,3,1,3,1,7) \).

For each vertex \( v \) in \( T \):

  • # of occurrences in \( u_1, \dots, u_{n-1} \) and \( v_{n-1} \) is \( 1 \),
  • # of occurrences in edges \( (u_i, v_i) \) id \( \deg v \),
  • # of occurrences in \( v_1, \dots, v_{n-2} \) is \( \deg v - 1 \).

For each \( i \), the edge \( (u_i, v_i) \) can be determined because \( u_i \) is the smallest number not in \( \lbrace u_1, \dots, u_{i-1} \rbrace \cup \lbrace v_i, \dots, v_{n-1} \rbrace \).

Since the last digit of Prufer code must be \( n \), there are \( n^{n-2} \) Prufer code of \( n \) elements.

Each Prufer code is decodable to a tree, thus there are \( n^{n-2} \) trees on \( n \) distinct vertices.

Double Counting

What is the # of sequences of adding directed edges to an empty graph to form a rooted tree?

From a tree:

  • pick a root (\( n \) vertices)
  • pick an order of edges (\( n-1 \) edges in total)

# of sequences are \( T_n \times n \times (n-1)! = n!T_n \)

From an empty graph (all nodes are isolated):

  • add edges one by one, each edge eliminates a tree
  • after adding \( k \) edges, there are \( n-k \) isolated trees remaining
  • when adding the next edge, choose any vertex and the root of another tree: \( n \times (n-k-1) \) methods

Therefore, we have

\[ n!T_n = \prod_{k=0}^{n-2} n(n-k-1) = n^{n-2}n! \]

Thus we reach \( T_n = n^{n-2} \) again.

Graph Laplacian

Define adjacency matrix \( A \), where

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

and diagonal matrix \( D \), where

\[ D(i,j) = \begin{cases} \deg i, & i = j, \\ 0, & i \neq j. \end{cases} \]

then we define graph Laplacian \( L \) as \( L = D - A \).

\( L \) can be also defined as

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

Krichhoff's Matrix-Tree Theorem

Define \( L_{i,i} \) as the submatrix of \( L \) obtained by removing the \( i \)-th row and \( i \)-th column.

Denote \( t(G) \) as the number of spanning trees in \( G \).

Krichhoff's Matrix-Tree Theorem: \[ \forall i, t(G) = \det(L_{i,i}) \]

Cauchy-Binet Theorem: \[ \det(AB) = \sum_{S \in {[m] \choose n}} \det(A_{[n],S}) \det(B_{S,[n]}) \]

For all \( n \)-vertex trees: they are spanning trees of \( K_n \), thus

\( L_{i,i} = \begin{bmatrix} n-1 & -1 & \dots & -1 \\ -1 & n-1 & \dots -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \dots & n-1 \end{bmatrix} \)

thus we obtain Cayley Formula: \[ T_n = t(K_n) = \det(L_{i,i}) = n^{n-2}. \]