\documentstyle[11pt,handout]{article}
\begin{document}
\input{localmacros}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{2 December 1998}{23}

\begin{center}
\Large{\bf Problem of the Week -- 10}
\end{center}

A {\em bipartite}\/ graph is an undirected graph $G = (V, E)$ in which $V$ can
be partitioned into two sets $V_1$ and $V_2$ such that all edges go between
the two sets $V_1$ and $V_2$; that is, $(u,v) \in E$ implies either $u \in
V_1$ and $v \in V_2$ or $u \in V_2$ and $v \in V_1$.
\begin{itemize}
\item[(a)] 
Prove that an undirected graph is bipartite if and only if it has no cycles of
odd length.

\item[(b)]
Using breadth-first search, design and analyze an algorithm to determine
whether a given undirected graph is bipartite.  ({\em Hint:}\/ Use the result
of part~(a).)
\end{itemize}
\end{document}