1. Consider the graph above. Give an ordering of the vertices so when you apply the greedy algorithm to color the tree when each new vertex
is colored it is connected to exactly one vertex that was colored previously.
2. What number of colors does the greedy algorithm use when applied to the
ordering from Part 1?
3. Give an ordering of the vertices of the graph above, so that applying the
greedy algorithm uses more colors than in Part 2. What is the first vertex
in your ordering which uses a color that was not used in Part 2?
4. Let T be an arbitrary tree. Prove that there is an ordering on the vertices
as in Part 1.