Skip to main content

Chapter 28 Graph Exercises

Exercises Exercises

1.

.

  1. There are 3 different unlabeled trees on 5 vertices. Draw them all.

  2. Verify Cayley's Theorem for \(n=5\) by counting the number of distinct labelings of each of the 3 trees in part (a). Your numbers should add to \(5^3=125\text{.}\)

  3. There are 6 different unlabeled trees on 6 vertices. Draw them all.

  4. Verify Cayley's Theorem for \(n=6\) by counting the number of distinct labelings of each of the 6 trees in part (c). Your numbers should add to \(6^4=1296\)

2.

A tree on vertices \(0,1,2,\ldots, n-1\) rooted at vertex \(0\) is ascending when the label of each child is larger than the label of its parent. For example, there are two ascending trees on 3 vertices:

Use induction on \(n\) to prove that the number of ascending trees is \((n-1)!\text{.}\)

3.

Find a closed formula for the number of trees on \(n\) vertices with exactly \(k\) leaves.

4.

Let \(\mathcal{A}_n\) be the set of labeled trees whose internal (non-leaf) vertices all have degree 3. Prove that \(n\) must be even, and then find a simple formula for \(|\mathcal{A}_n|= |\mathcal{A}_{2k}|\text{.}\)

5.

Use inclusion-exclusion to find the number of rooted forests on \([n]\) that contain no isolated vertices.

6.

Let \(\mathcal{Z}_n\) be the family of rooted forests such that each rooted component is either (1) an isolated vertex, or (2) a path rooted at one of its endpoints. Prove that

\begin{equation*} |\mathcal{Z}_n| = \sum_{k=0}^{n-1} {n \choose k} (n-1)_k. \end{equation*}
7.

Let \(T(x) = \sum_{n=1}^{\infty} t_n \frac{x^n}{n!}\) be the exponential generating function for labeled trees on \([n]\text{,}\) where \(t_0=0\text{.}\) Let \(F(x) = \sum_{n=1}^{\infty} f_n \frac{x^n}{n!}\) where \(f_0=1\) be the exponential generating function for lableled forests on \([n]\text{.}\)

  1. Give a combinatorial proof of your recurrence relation in part (b). Use the following interpretation: how many ways are there to make a forest with one distinguished vertex (maybe there is a squirrel living there)?