A graph is bipartite exactly when it has no odd cycle

($\Rightarrow$) Suppose the classes are $A$ and $B$. Going along a cycle, we alternate between $A$ and $B$, and we return to the start, so the number of steps is even.

($\Leftarrow$) Assume there is no odd cycle. It suffices to colour each connected component separately. In a component choose a root $r$ and give a vertex $x$ the colour of the parity of $d(x)$, the length of a shortest path from $r$ to $x$.

Suppose an edge $uv$ joins two vertices of the same parity. Then the walk "shortest path $r\to u$, the edge $uv$, shortest path $v\to r$" is a closed walk of length $d(u)+1+d(v)$, which is odd.

Claim. A closed walk of odd length contains an odd cycle.

*Proof by strong induction on the length $L$.* If no vertex repeats (except the start/end), the walk is a cycle, of odd length $L$. Otherwise some vertex $w$ occurs twice in the walk, which splits it into two closed walks (from $w$ to $w$) whose lengths $L_1,L_2$ are positive, smaller than $L$, and add up to $L$. One of them is odd; apply the induction hypothesis to it. $\square$

So the edge $uv$ would create an odd cycle, a contradiction. Hence every edge joins vertices of opposite parity, and the graph is bipartite.

Example. Trees, even cycles and grids have no odd cycle, so they can be $2$-coloured. A triangle needs $3$ colours.

Lesson. Colour by parity of distance; an odd closed walk always hides an odd cycle.