I'm asked to prove using induction on the vertices of a graph that if it has no cycles of odd length it is bipartite. I'm aware of the usual contradiction proof, but I'm trying to accomplish it by induction.
Here's what I've done until now.
Base case: When $|V(G)| = 2$ it is easy to see there's no cycles of odd length and is bipartite.
Hypothesis: A graph $G$ without cycles of odd length and with $|V(G)| < L$ is bipartite.
Inductive step: Let G be a graph with $|V(G)| = L$, if G has no cycle with odd length, we can remove any vertex $v$ from $V(G)$ and, using our hypothesis, $G-v$ is bipartite.
And I'm stuck here. What I've done is basically reduce my graph so it fits the hypothesis, but that's not enough to prove that it is valid for $|V(G)| = L$. I tried thinking about a way to show that since $G-v$ is a subgraph of $G$ and $G-v$ is bipartite then $G$ also is, but that is not true. I have no idea how to continue my proof. Appreciate any kind of help.