Skip to main content

Chapter 26 Counting Trees and Forests

Exercises Practice Problems

1.

Let \(T\) be a tree on \(n\) vertices whose non-leaf vertices all have degree 3.

  1. Prove that \(T\) has \(\frac{1}{2}(n-2)\) vertices of degree 3.

  2. Find a formula for the number of such trees.

2.

Let \(T(n,k)\) be the number of labeled forests on \([n]\) with \(k\) components such that the vertices in \([k]\) are all in different tree components.

  1. Show that \(T(4,2)=8\) by enumerating all the forests on 4 vertices with 2 trees in which vertex 1 and vertex 2 are in different trees.

  2. Prove the recurrence relation

    \begin{equation*} T(n,k) = \sum_{i=0}^{n-k} {n - k \choose i} T(n-1, k-1+i) \qquad \mbox{where } 1 \leq k \leq n \end{equation*}

    where \(T(0,0)=1\) and \(T(n,0)=0\) for \(n\geq 1\text{.}\) (Hint: treat vertex 1 as special.)

3.

We obtain the ordered degree sequence of a graph by arranging the degrees in non-increasing order (from largest to smallest). In this problem, you will find the number of possible ordered degree sequences for a tree.

  1. Let \(d_1 \geq d_2 \geq \cdots \geq d_n\) be an ordered degree sequence of a tree.

    1. Prove that \(\sum_{i=0}^{n-1} d_i = 2n-2\text{.}\)

    2. Prove that \(d_{n-2} = d_{n-1}= 1\) by contradiction. That is, prove that if one of these numbers is greater than 1, then part (i) does not hold.

  2. We can use induction on \(n \geq 2\) to prove that if (i) and (ii) hold, then there is a tree with the given ordered degree sequence.

    • Base Case. The statement is true for \(n=2\text{.}\)

    • Inductive Hypothesis. Assume it is true for all such sequences of length \(n-1\text{.}\)

    • Inductive Step. Consider a sequence \(d_1 \geq d_2 \geq \cdots \geq d_n\) satisfying (i) and (ii). Find the last \(d_i > 1\text{.}\) Remove \(d_n\) from the sequence and replace \(d_i\) with \(d_i-1\text{.}\)

      • Explain why (i) and (ii) hold for the resulting sequence of length \(n-1\text{.}\)

      • Use this fact to create a tree with degree sequence \(d_1 \geq d_2 \geq \cdots \geq d_n\text{.}\)

  3. Given our characterization (i) and (ii) for ordered degree sequences for trees, how many are there?

    We give three different (but equivalent) formulas.