\begin{problem}
\begin{theorem*}
A graph $G$ is bipartite if and only if it contains no odd cycle.
\end{theorem*}

We'll walk you through a proof.  As is common with ``if and only if''
assertions, the proof has two parts.  Part (a) asks you to prove that
the left side of the ``if and only if'' implies the right side.  Parts
(b), (c), (d) and (e) help you prove that the right side implies the
left.

\bparts

\ppart Assume the left side and prove the right side.  Three to five
sentences should suffice.

\solution{Select a 2-coloring of $G$.
Consider an arbitrary cycle with vertices $v_1, v_2, \ldots, v_k$.
Then the vertices $v_i$ must be one color for all even $i$ even and
the other color for all odd $i$.  Since $v_1$ and $v_k$ must be
colored differently, $k$ must be even. Thus, the cycle has even
length.  We can make the same argument for any cycle in $G$, so every
cycle has even length.}

\ppart Now assume the right side.  Initially, suppose that $G$ is
a connected graph with no odd cycle, and let $T$ be a spanning tree.
Describe a 2-coloring of $G$ based on this tree.

\solution{Select a ``root'' vertex $v$ arbitrarily.
Color a vertex $w$ red if the distance to $v$ is even, and color $w$
black if the distance to $v$ is odd.}

\ppart Now we must prove that the coloring is valid.  Why must an
edge $\edge{x}{y}$ in the spanning tree connect different-colored
vertices?

\solution{Either the unique path from $v$ to $y$ goes through $x$
or the unique path from $v$ to $x$ goes through $y$.  In either case,
one vertex is at an odd distance from $v$ and the other is at an even
distance from $v$, so the two vertices are differently-colored.

\ppart Why must an edge $\edge{x}{y}$ {\em not} in the tree connect
different-colored vertices?

\solution{Let $z$ be the first common vertex on the path from $x$ to the
root $v$ and the path from $y$ to $v$.  The paths from $x$ to $z$ and
$y$ to $z$ must have different parities (one odd, the other even);
otherwise, these two paths together with the edge $\edge{x}{y}$ would
form an odd cycle.  Therefore, $x$ and $y$ must be colored
differently.}

\ppart Now suppose that $G$ has no odd cycle, but is not necessarily
connected.  Describe a way of obtaining a 2-coloring of $G$.

\solution{Color each connected component of $G$ with 2 colors one at a
time.}

\eparts

\end{problem}

