Questions with a (β) are each worth 1 bonus point for 453 students.
Show that for any π ≥ 3, if a tree π has fewer than π leaves, then the maximum degree Δ(π) among the vertices of π must satisfy Δ(π) < π. It can help to consider the summations
π ππ ; 2(π − 1) = total degree .
π=1 π=1
The phrase “π has fewer than π leaves” means π1 < π.
The two sums can be combined into the single sum
π
∑(2 − π)ππ = 2
π=1
It suffices to show that ππ = 0 for all π ≥ π.
Let (π, π) be a rooted tree. Recall that the level of a vertex π₯ is πΏ(π₯) = π·(π, π₯). Also, the height of a rooted tree π» is the maximum of the levels of its vertices. Show that if π is on the unique π’, π£-path, then π·(π’, π£) = πΏ(π’) +
πΏ(π£).
Show that if πΏ(π’) + πΏ(π£) = π·(π’, π£), then π must be on the unique π’, π£-path.
Show that for any two vertices π’ and π£, π·(π’, π£) ≤ 2π».
Show that if π·(π’, π£) = 2π», then π’ and π£ must be non-parents. Equivalently, you can show that if either π’ or π£ is a parent, then π·(π’, π£) < 2π».
Suppose (π, π) is a rooted π-ary tree where every parent has exactly π children; such a tree is said to be saturated.Show that π has ππ edges for some integer π.
Find a formula for the number of vertices of π in terms of π, π.
Find a formula for the number of non-parents in terms of π, π.
Suppose (π, π) is a rooted tree with exactly 1012 Recall that a lower bound or an upper bound on π» is tight if there exists an example π where that bound is attained.Find tight lower and upper bounds for π», the height of π.
Find tight lower and upper bounds for π» if π is a saturated rooted binary tree. Recall that saturated means every parent has the maximum allowed number of children; here, that number is 2.
