\problem An {\em edge coloring} of a graph is an assignment of a color
to each edge of a graph so that no two edges that share an endpoint
have the same color.
\begin{problemparts}
\ppart Prove that a graph with maximum degree $\Delta$ MUST be colored
with at least $\Delta$ colors.

This is pretty tight, because a famous theorem of Vizing says that
every graph can be edge-colored with $\Delta$ or $\Delta+1$ colors.
We'll prove a special case.

\ppart Prove by induction that a graph with maximum degree $\Delta$
can be colored with at most $2\Delta-1$ colors.

\ppart Suppose every vertex in a graph has even degree.  Prove that
the graph's edges can be colored with two colors such that exactly
half the edges incident on each vertex have each color.  {\bf Hint:}
  consider alternating colors on an Euler tour of the edges.

\ppart Prove that a graph in which every edge has degree $2^k$ can be
edge-colored with exactly $2^k$ colors.

\ppart Prove that a graph with maximum degree $2^k$ can be colored
with exactly $2^k$ colors.
\end{problemparts}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
