Recall that a graph is bipartite if and only if it is possible to colour the vertices with two colours, such that any two adjacent vertices have different colours. In this question, we will prove that all trees are bipartite by induction on the number of vertices.
(a) Prove that a tree with one vertex is bipartite.
(b) State the inductive hypothesis.
(c) State what needs to be shown for the inductive step.
(d) Prove the inductive step. You may use the fact that every tree has a leaf (a vertex of degree 1).