Proving by induction on the number of vertices that: every acyclic simple graph is bipartite

Question

Prove that every acyclic simple graph is bipartite, by the use of induction.

I have quite some trouble with induction. Specifically, I know that acyclic graphs have at least one vertex that has a degree of one or lower (leaf if I can recall correctly) and that if you remove that vertex you will get a cyclic graph(?), but I have trouble proving this with induction somehow, I do not know where to start.

Answer 1

Hint Prove first the following Lemma:

Lemma: If $G$ is a graph where every vertex has degree at least 2, then $G$ contains a cycle.

This Lemma implies that your graph has a vertex of degree at most 1. Erase this vertex for the inductive step.