- Show that for any 𝑘 ≥ 3, any tree with a vertex of degree 𝑘 must have at least 𝑘 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
- Suppose 𝑇 is a binary tree of height 𝐻 with 𝑛
- As a function of 𝐻, what are the minimum and maximum possible values of 𝑛?
- Suppose every parent has exactly two children in 𝑇. Show that 𝑛 must be odd.
- Let (𝑇, 𝑟) be a rooted tree.
- Show that if 𝐷(𝑢, 𝑣) = 2𝐻 where 𝐻 is the height of 𝑇, then 𝑢 and 𝑣 are non-parents.
- Show that 𝐷(𝑢, 𝑣) is the sum of the levels of 𝑢 and 𝑣 if and only if 𝑟 is on the unique 𝑢, 𝑣-path.
- Suppose 𝐺 is a simple graph (no loops; no parallel edges) with 𝑛 = 14 vertices and 𝑚 = 7 What are the possible values for 𝑘, the number of components of 𝐺?
- Suppose 𝑇 is a binary tree with 109 What are the minimum and maximum possible values of 𝐻, the height of 𝑇?
