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. Solution.

    If we sum the degrees, then we get twice the number of edges. Suppose that there are \(k\) vertices of degree 3. Then

    \begin{equation*} \begin{array}{rcl} 2(n-1) &=& 3 k + (n-k) \\ n -2 & = & 2k \\ \frac{n-2}{2} &=& k. \end{array} \end{equation*}

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

    We have \((n-2)/2\) vertices of degree 3 and \((n+2)/2\) vertices of degree 1. The degree 3 vertices appear in the Prufer code two times. So the total number of trees is

    \begin{equation*} {n \choose (n-2)/2} { n-2 \choose 2, 2, \ldots,2 } \end{equation*}

    because we must first choose the vertices of degree three, and then create the Prufer code.

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. Solution.

  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.) Solution.

    • Pick the degree \(i\) of vertex \(1\text{,}\) where \(0 \leq i \leq n-k\text{.}\)

    • Pick the neighbors of \(1\text{.}\) This can be done in \({n-k \choose i}\) ways.

    • Now these \(i\) neighbors cannot be in the same tree as \(2,3, \ldots, k\text{.}\) If we remove vertex 1, now we have \(k-1+i\) vertices that must be in separate trees. There are \(T(n-1, k-1+i)\) ways to do this.

    In end, we must sum over all possible values of \(i\text{.}\)

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{.}\) Solution.

      The handshaking lemma says that if we sum the degrees then we count every edge twice. So the sum of the degrees of a tree is \(2(n-1)\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. Solution.

      If \(d_{n-2} \geq 2\) then \(\sum_{i=0}^{n-1} d_i \geq 2(n-1) + 1 = 2n-1\text{,}\) a contradiction.

  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{.}\)

    Solution.

    After we remove \(d_n\) and replace \(d_i\) with \(d_i-1\text{,}\) It is clear that the degrees sum to \(2(n-2)=2n-4\text{.}\) As argued in part (ii) of (a), this forces the last two degrees to be at most 1. (Otherwise we get the same contradiction we encountered above). So our new sequence of length \(n-1\) satisfies properties (i) and (ii). Therefore, there is a tree on \(n-1\) vertices that realizes this degree sequence. We obtain a tree on \(n\) vertices that realizes the original sequence by adding a leaf to vertex \(i\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. Solution.

    • \(p(2n-2,n)\text{.}\) We need to partition the integer \(2n-2\) into exactly \(n\) parts.

    • Note that the two smallest parts must both be 1, So we could also write this as \(p(2n-4,n-2)\text{.}\)

    • But here is a much cleaner expression: \(p(n-2)\text{.}\) We partition \(n-2\) into any number of parts. Then we add this partition to the all-ones partition of length \(n\) to get the partition we desire.