CPTS 553: Graph Theory Assignment 6 solved

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 𝑇?