Exercise 9.

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

Hint.
in-context