2 Trees

Theorem

The followings are equivalent.

• $G=(V,E)$ is a tree;
• any two vertices are connected by a unique path;
• $G$ is connective with $|V|-1=|E|$.

\begin{proof} iii)→i) $G$ has a spanning tree $T$, then $1=|V(G)|-|E(T)|=|V(G)|-|E(G)|$. Then $E(G)=E(T)$ and the proof is completed. \end{proof}

Corollary

Let $G$ be a forest. Then the number of connected components of $G$ is $|V(G)|-|E(G)|$.

Corollary

Let $T$ be a tree, and let $n=|V(T)|⩾2$ with degree sequence $(d_0,\cdots ,d_n)$. Then $\sum d_i=2n-2$.

Theorem

There are $n^{n-2}$ different labeled trees on $n$ vertices.

\begin{proof} We aim to find a bijection between trees on $[n]=\{1,\cdots ,n\}$ and $[n{]}^{n-2}$.

The first proof due to H. Prüfer (1918), uses an algorithm that associates to any tree $T$ a ‘name’ $\mathcal{P}(T)$ (called the Prüfer code) that characterizes the tree.

An example of Prüfer code.

For the tree in Fig. 2.1, where $n=10$, we have $\left(x_1,y_1\right)=(3,2)$, $\left(x_2,y_2\right)=(4,2),\left(x_3,y_3\right)=(2,1),\dots ,\left(x_9,y_9\right)=(9,10)$; these edges are the columns of the matrix below.

$$\left[\begin{array}{ccccccccc}3& 4& 2& 5& 6& 7& 1& 8& 9\\ 2& 2& 1& 1& 7& 1& 10& 10& 10\end{array}\right]$$

So $\mathcal{P}(T)=(2,2,1,1,7,1,10,10)$.

To understand why $\mathcal{P}$ is bijective, we first note some facts.

• The number of times a vertex $v$ occurs among $y_1,y_2,\dots ,y_{n-2}$ is ${\mathrm{deg}}_T(v)-1$.
• Similarly, the number of times a vertex $v$ of $T_k$ occurs among $y_k,y_{k+1},\dots ,y_{n-2}$ is its degree in the tree $T_k$ less 1 .
• The monovalent vertices of $T_k$ are those elements of $V$ not in

$$\left\{x_1,x_2,\dots ,x_{k-1}\right\}\cup \left\{y_k,y_{k+1},\dots ,y_{n-1}\right\},$$

In particular, $x_1$ is the least element of $V$ not in the name $\mathcal{P}(T)$, and we can uniquely determine $x_k$ from $\mathcal{P}(T)$ and $x_1,\dots ,x_{k-1}$. \end{proof}

Here is another proof.

\begin{proof} Let $t(n;d_1,\cdots ,d_n)$ be the number of trees with degrees $d_1,\cdots ,d_n$. Let ${\left(x_1+x_2+\cdots +x_k\right)}^n=\sum \left(\genfrac{}{}{0ex}{}{n}{r_1,\dots ,r_k}\right)x_1^{r_1}{x}_2^{r_2}\dots x_k^{r_k}$. Then we have

$$\left(\genfrac{}{}{0ex}{}{n}{r_1,\cdots ,r_k}\right)=\sum _{i=1}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{r_1,\cdots ,r_{i-1},r_i-1,r_{i+1},\cdots ,r_k}\right),$$

because $(x_1+\cdots +x_k{)}^n=(x_1+\cdots +x_k{)}^{n-1}(x_1+\cdots +x_k)$.

Since

$$t\left(n;d_1,\dots ,d_n\right)=\sum _{i=1}^{n-1}t\left(n-1;d_1,\dots ,d_i-1,\dots ,d_{n-1}\right)=\left(\genfrac{}{}{0ex}{}{n-2}{d_1-1,\cdots ,d_n-1}\right),$$

we have $n^{n-2}=\sum t\left(n;d_1,d_2,\dots ,d_n\right)$. \end{proof}

Another proof.

\begin{proof}

Kirchhoff’s Matrix Tree Theorem

Number of spanning trees of $G=\frac{1}{n}{\lambda }_1\cdots {\lambda }_n$, where ${\lambda }_1,\cdots ,{\lambda }_{n-1}$ are non-zero eigenvalues of $L(G)$, see ^snjg2a.

By Cauchy-Binct formula, $\det (AB)={\sum }_{\det A_{[n],s}{B}_{s,[m]}}$.

不知道咋算的反正算出来了 \end{proof}