Using induction to prove that a graph without cycles of odd length is bipartite

Question

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.

Answer 1

Give your graph $G-v$ a (black/white) vertex colouring corresponding to its bipartition. Consider the neighbours of $v$ in $G$, say $w_1,\ldots,w_k$. If they all have the same colour, you are fine. Suppose not, for instance, $w_1$ is black and $w_2$ is white. Then $w_1$ and $w_2$ are in different components of $G-v$ for otherwise there's a path in $G-v$ from $w_1$ to $w_2$ and extending this to $v$ and then back to $w_1$ gives an odd length cycle in $G$. As $w_1$ and $w_2$ are in different components of $G-v$ if one reverses the colours of the vertices in one component, $w_1$ and $w_2$ both gain the same colour. Repeat, until all the $w_i$ have the same colour...