Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 7 / b / 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.