# 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}.$