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 π?
