Exercise 9. Give a careful proof by induction on the number of vertices, that every tree is bipartite. Hint.