Graph Theory
Assignment 6
1. Consider rooted trees with exactly 1012 non-parent vertices. Recall that we denote by 𝐻 the height
of such a tree.
A. Find a tight lower bound for 𝐻 among such trees.
B. Find a tight upper bound for 𝐻 among such trees.
C. Find a tight lower bound for 𝐻 among binary rooted trees with exactly 1012 non-parent vertices.
D. Find a tight lower bound for 𝐻 among 𝑛-ary rooted trees with exactly 1012 non-parent vertices.
Your formula should involve 𝑛.
2. Consider the binary rooted tree (𝑇, 𝑟) each of whose vertices is a finite string over {0,1}. We
construct our tree by the following rules:
The root is the vertex 0.
If 𝑣 is a string that ends in a 0, then the left child of 𝑣 is “𝑣0” and the right child is “𝑣1”.
If 𝑣 is a string that ends in a 1, then the only child of 𝑣 is “𝑣0”.
A. Draw Levels 0 through 4 of this tree, with the vertices labeled appropriately.
B. Make a conjecture of how to compute the number of vertices at a given level.
3. Show that the graph below cannot be 3-colored:
4. Find the chromatic polynomial of the graph below:
