[SOLVED] CPTS553-Assignment 6

Description

1. 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

2. Suppose 𝑇 is a binary tree of height 𝐻 with 𝑛
   1. As a function of 𝐻, what are the minimum and maximum possible values of 𝑛?
   2. Suppose every parent has exactly two children in 𝑇. Show that 𝑛 must be odd.

3. Let (𝑇, 𝑟) be a rooted tree.
   1. Show that if 𝐷(𝑢, 𝑣) = 2𝐻 where 𝐻 is the height of 𝑇, then 𝑢 and 𝑣 are non-parents.
   2. 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 What are the possible values for 𝑘, the number of components of 𝐺?

5. Suppose 𝑇 is a binary tree with 10⁹ What are the minimum and maximum possible values of 𝐻, the height of 𝑇?