\documentclass[12pt]{article}

\usepackage{graphicx}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in} {\bssdoz CME 305: Discrete
Mathematics and Algorithms} {\\ \bssten Instructor: Professor Amin
Saberi (saberi@stanford.edu) } {\\ \bssten Midterm -- 02/17/09}

\vspace{4cm}

{\bf Problem 1.} We say that a graph is $k$-regular if all its vertices 
have degree $k$. Prove that all $k$-regular bipartite graphs have a perfect 
matching.

{\noindent Hint: use Hall's Marriage Theorem}

\vspace{1cm}

{\bf Problem 2.} A proper coloring of the edges of a graph $G$ is an
assignment of colors to edges such that no two adjacent edges have
the same color. A graph is said to be $k$-edge-colorable if there is
a proper edge-coloring of the graph that uses $k$ or fewer colors.

Prove that if the maximum degree in a bipartite graph $G$ is
$\Delta$, then $G$ is $\Delta$-edge-colorable. Also provide a polynomial-time 
algorithm that produces such a coloring.

\vspace{1cm}

{\bf Problem 3. (extra credit)} Give a polynomial time algorithm for
a proper coloring of the vertices of a $3$-vertex-colorable graph of
size $n$ with at most $O(\sqrt{n})$ colors.



\end{document}