= 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 length
$$
\operatorname{depth}(u)+\operatorname{depth}(v)
-2\operatorname{depth}(\operatorname{LCA}(u,v)),
$$
which 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>.
$$
\boxed{G\text{ is bipartite}\iff G\text{ has no odd cycle}.}
$$
This is the <odd-cycle characterization of bipartite graphs>. The argument applies separately to every <connected component>.
Back to article page
