4 Spanning Trees 4 Spanning Trees 4.2 ***Spanning Trees and Forests***

4.1 Trees and Cayley’s theorem

Definition 4.1 (Trees ).

A graph with no cycles is called a forest. A connected forest is called a tree.

Exercise(A) 4.2.

Show that TFAE¹¹ 1 the following are equivalent for a graph $G$ on $n$ vertices.

1.

$G$ is a forest.
2.

$G$ has $n-\beta_{0}(G)$ edges.

Exercise 4.3.

Show that a graph $G$ is a tree iff it is connected and has $n-1$ edges.

Exercise 4.4.

Prove that there exists two vertices of degree $1$ in a tree.

A labelled tree on $[n]$ is a tree with vertex set $[n]$ . Note that two labelled trees are equal only if their edge sets are equal. Thus isomorphic labelled trees are not necessarily equal for us. A spanning subgraph $T\subset G$ is said to be a spanning tree of $G$ if $T$ is a tree. Now it is easy to observe that a labelled tree on $[n]$ is nothing but a spanning tree of $K_{n}$ , the complete graph on $[n]$ .

Theorem 4.5 (Cayley’s formula ).

The number of labelled trees on $n$ (or number of spanning trees of $K_{n}$ ) vertices is $n^{n-2}$

Proof via Prufer code (H. Prufer (1918)) ..

We shall construct a bijection

P:\mathcal{S}(n):=\{\mbox{labelled trees on $[n]$}\}\to[n]^{n-2}.

Given a tree $T$ on $[n]$ , we generate a sequence of trees $T_{1},\ldots,T_{n-1}$ inductively as follows : Set $T_{1}=T$ . Given tree $T_{i}$ on $n-i+1$ vertices, let $x_{i}$ be the least labelled vertex of degree 1 and delete the edge incident on $x_{i}$ to obtain $T_{i+1}$ . Denote by $y_{i}$ , the neighbour of $x_{i}$ . Observe that $T_{n-1}$ is $K_{2}$ and the process terminates at $T_{n}$ when the tree has only one vertex. Now define $P$ as

P(T)=(y_{1},\ldots,y_{n-2}).

Clearly $P$ is a map from $\mathcal{S}(n)$ to $[n]^{n-2}$ . We shall prove that it is a bijection by constructing $P^{-1}$ using induction. For $n=2$ , $P$ is trivially a bijection.

Some observations : (i) $(y_{2},\ldots,y_{n-2})$ is the Prufer code of $T_{2}$ . (ii) The degree
$d_{i}:=\sum_{j=1}^{n-2}\mathbf{1}[y_{j}=i]+1$ (Try to prove this yourself by induction on $n$ and then see the proof below). (iii) As a consequence we have that
$x_{k}:=\min\{i:i\notin\{x_{1},\ldots,x_{k-1},y_{k},\ldots,y_{n-2}\}\}$ (again prove by induction on $k$ using (ii)).

Suppose $P$ is a bijection for $n-1$ and let $a=(a_{1},\ldots,a_{n-2})\in[n]^{n-2}$ . Now, let $x=\min\{i:i\notin(a_{1},\ldots,a_{n-2})\}$ . Consider $a^{\prime}=(a_{2},\ldots,a_{n-2})$ and by induction assumption $a^{\prime}$ is the unique Prufer code of a tree $T^{\prime}$ on $[n]\setminus\{x\}$ since $P$ is a bijection on $[n]\setminus\{x\}$ by induction assumption. Define $T:=T^{\prime}\cup\{x,a_{1}\}.$ Clearly, $T$ is a tree as $x\notin V(T^{\prime})$ and $P(T)=a$ . If $T^{\prime\prime}$ is a tree such that $P(T^{\prime\prime})=a$ , then by the property (ii) of Prufer code, $[n]\setminus\{a_{1},\ldots,a_{n-2}\}$ is nothing but vertices of degree 1. By definition of $x$ , it has the least label among such vertices and thus by construction $(x_{1},y_{1})=(x,a_{1})$ . Hence, $P(T^{\prime\prime}_{2})=a^{\prime}$ . By uniqueness of $T^{\prime}$ , we have that $T^{\prime\prime}_{2}=T^{\prime}$ and hence $T^{\prime\prime}=T.$ So $P^{-1}$ is well-defined on $[n]^{n-2}$ and $P$ is $1-1$ and onto. Thus $P$ is a bijection.

Trivially (ii) holds for $n=2$ . Assume that it holds for all trees on $n-1$ vertices. Let $T$ be a tree on $[n]$ . By (i) and induction hypothesis, for $i\neq x_{1}$ , we have that $d_{i}(T_{2})=\sum_{j=2}^{n-2}\mathbf{1}[y_{j}=i]+1$ . Since $d_{i}(T_{2})=d_{i}(T)$ for all $i\neq x_{1},y_{1}$ and $d_{x_{1}}(T)=1$ , $d_{y_{1}}(T)=d_{y_{1}}(T_{2})+1$ , (ii) holds for $T$ as well. ∎

Theorem 4.6 (Tree counting theorem ).

The number of labelled spanning trees on $n$ vertices with degree sequence $d_{1},\ldots,d_{n}$ is $\binom{n-2}{d_{1}-1,\ldots d_{n}-1}=\frac{(n-2)!}{\prod_{i=1}^{n}(d_{i}-1)!}$ for $n\geq 3$ .

Exercise 4.7.

Show that Cayley’s theorem follows as a corollary of the tree counting theorem.

Proof.

Denote by $t(n;d_{1},\ldots,d_{n})$ the number of trees with degree sequence $d_{1},\ldots,d_{n}$ . The theorem holds for $n=3$ . Assume that it is true for $n-1$ . Assume that $d_{j}=1$ .

Suppose $j$ is joined to $i$ in a tree $T$ , then $T-(i,j)$ is a tree on $[n]-j$ with degree sequence $d_{1},\ldots,d_{i}-1,\ldots,d_{n}$ . Thus we get that

t(n;d_{1},\ldots,d_{n})=\sum_{i=1,i\neq j}^{n}t(n-1;d_{1},\ldots,d_{i}-1,\hat{% d_{j}},\ldots,d_{n}),

where $\hat{d_{j}}$ means $d_{j}$ is absent. Note that it is not possible that $d_{i}=1$ and for $d_{i}=1$ , $t(n-1;d_{1},\ldots,d_{i}-1,\ldots,d_{n})=0$ . Now check inductively that $t(n;d_{1},\ldots,d_{n})=\binom{n-2}{d_{1}-1,\ldots d_{n}-1}.$ ∎

Exercise(A) 4.8.

Give an alternative proof of tree counting theorem using Prufer codes.

Remark 4.9 (More proofs of tree counting theorem).

As with any such a fundamental result, there are multiple proofs.

1.

We shall see a more powerful tree counting argument (known as Kirchoff’s matrix tree theorem) using matrix theory later.
2.

There is another proof via bijection due to Joyal and a recent double counting argument due to Pitman.

All these five proofs can be found in [Aigner et al. 2010, Chapter 30].