CS453 -Graph Theory   - Assignment 6  - Solved

1.     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 𝑗 ≥ 𝑘.   

 

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

a.     Show that if 𝑟 is on the unique 𝑢, 𝑣-path, then 𝐷(𝑢, 𝑣) = 𝐿(𝑢) +

𝐿(𝑣).  

b.     Show that if 𝐿(𝑢) + 𝐿(𝑣) = 𝐷(𝑢, 𝑣), then 𝑟 must be on the unique 𝑢, 𝑣-path.

c.      Show that for any two vertices 𝑢 and 𝑣, 𝐷(𝑢, 𝑣) ≤ 2𝐻.

d.     Show that if 𝐷(𝑢, 𝑣) = 2𝐻, then 𝑢 and 𝑣 must be non-parents.  Equivalently, you can show that if either 𝑢 or 𝑣 is a parent, then 𝐷(𝑢, 𝑣) < 2𝐻.

 

3.     Suppose (𝑇, 𝑟) is a rooted 𝑞-ary tree where every parent has exactly 𝑞 children; such a tree is said to be saturated.

a.     Show that 𝑇 has 𝑏𝑞 edges for some integer 𝑏.

b.     Find a formula for the number of vertices of 𝑇 in terms of 𝑏, 𝑞.

c.      Find a formula for the number of non-parents in terms of 𝑏, 𝑞.

 

4.     Suppose (𝑇, 𝑟) is a rooted tree with exactly 1012 edges.  Recall that a lower bound or an upper bound on 𝐻 is tight if there exists an example 𝑇 where that bound is attained.

a.     Find tight lower and upper bounds for 𝐻, the height of 𝑇.   

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