1. Show that for any ≥ 3, any tree with a vertex of degree must have at least leaves. The proof that uses summations of the result that a tree always has two leaves is probably easiest to adapt here. You will want to
assume ≥ 1 in the summations
∞ ∞
= ∑ ; total degree = ∑ .
=1
=1
2. Suppose is a binary tree of height with vertices.
A. As a function of , what are the minimum and maximum possible values of ?
B. Suppose every parent has exactly two children in . Show that must be odd.
3. Let ( , ) be a rooted tree.
A. Show that if ( , ) = 2 where is the height of , then and are non-parents.
B. Show that ( , ) is the sum of the levels of and if and only if is on the unique , -path.
4. Suppose is a simple graph (no loops; no parallel edges) with = 14 vertices and = 7 edges. What are the possible values for , the number of components of ?
5. Suppose is a binary tree with 109 vertices. What are the minimum and maximum possible values of , the height of ?
6.
