= Solution
Suppose first that $G$ is <bipartite>. As one traverses any <cycle in a graph>, its vertices alternate between the two vertex classes. Returning to the initial class therefore requires an <even number> of edges, so $G$ contains no <odd cycle>.
Conversely, suppose that $G$ has no <odd cycle>. Work separately in each <connected component of a graph>, choose a root $r$, and put
$$
A=\{v:d(r,v)\text{ is even}\},
\qquad
B=\{v:d(r,v)\text{ is odd}\},
$$
where $d$ is the <graph distance>. If adjacent vertices $u,v$ were in the same class, then $|d(r,u)-d(r,v)|\leq1$ and parity would force $d(r,u)=d(r,v)$. Choose a breadth-first <spanning tree>. The two tree paths from $r$ to $u$ and $v$ diverge at some last common vertex; their remaining segments have equal length, and adjoining the edge $uv$ gives an odd cycle. This contradiction shows that every edge joins $A$ to $B$, proving the <odd-cycle characterization of bipartite graphs>.
Back to article page
