Description
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
π = βππ
β
π=1
; total degree = βπππ
β
π=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 π?