Exercise 6.

Prove the chromatic number of any tree is two. Recall, a tree is a connected graph with no cycles.

1. Describe a procedure to color the tree below.

   

2. The chromatic number of \(C_n\) is two when \(n\) is even. What goes wrong when \(n\) is odd?

3. Prove that your procedure from part (a) always works for any tree.

4. Now, prove using induction that every tree has chromatic number 2.