 Solution

In a bipartite graph, successive vertices along an edge lie in opposite parts. Following a cycle alternates parts at each step, so returning to the starting part requires an even number of edges. Thus a bipartite graph contains no odd cycle.

Conversely, choose a rooted spanning forest and colour each vertex by the parity of its depth in its component's tree. Suppose an edge $uv$ had equally coloured endpoints. The unique tree path from $u$ to $v$ has lengthwhich is even. Adjoining $uv$ makes an odd cycle. Therefore, if there are no odd cycles, every edge joins opposite colours, which supplies the required bipartition.This is the odd-cycle characterization of bipartite graphs. The argument applies separately to every connected component.