\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 Solutions}


{\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

{\bf Solution: } Given $G(A,B,E)$ select a subset $S \in A$. The number of
edges leaving this set is $k |S|$ (since the graph is $k$-regular) which 
equals to the sum of the degrees of vertices in $S$. Since each of these 
edges must enter $N(S)$, the neighborhood of $S$, we have,
\[ k|S| = d(S) = \sum_{v \in S} d(v) \leq \sum_{u \in N(S)} d(u) =
d(N(S)) = k |N(S)| \]
For $S = A$ and $k \geq 1$, $N(A) = B$, the inequality above is satisfied 
exactly and we conclude that $|A| = |B|$ . Furthermore we have for any 
subset $|S| \leq |N(S)|$. Thus by Hall's Marriage theorem $G$ has a perfect 
matching.

{\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.

{\bf Solution:} We construct a graph $G'$ from $G(A,B,E)$ as follows.
Add enough vertices to $A$ or $B$ so that $n = |A| = |B|$. Since the graph
is bipartite we have $r = d(A) = d(B) = |E|$. Perform the following procedure.
While $r < \Delta n$, add egde $(u,v)$ for all $u \in A$ and $v \in B$
such that $d(u) < \Delta$ and $d(v) < \Delta$ incrementing $r$ by one
after each step.

At each step $d(A) = d(B) < \Delta n$ and $d(w) \leq \Delta$ for all 
vertices $w$. Thus the pair $(u,v)$ exists. Adding an edge inreases
both $d(A)$ and $d(B)$ by one. So after some finite number of steps
we have $r = \Delta n$ and $d(w) \leq \Delta$ which implies the constucted
graph $G'$ is $\Delta$-regular.

From problem $1$ we know that $G'$ has a perfect matching $M'$. Color
these edges (no two are adjacent) with color $c_0$ and remove them from
the graph obtaining a new graph $G''$. Note that $G''$ is
$(\Delta-1)$-regular and again has a perfect matching $M''$ which we can
color with $c_1$. When all edges are gone we've used $\Delta$ colors and
no two adjacent edges have the same color.  
Thus $G'$ is proper $\Delta$-edge-colorable.

Finally, since removing edges and vertices from a graph does not damage 
a proper edge coloring, $G$, a subgraph of $G'$, is also 
$\Delta$-edge-colorable.

{\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.

{\bf Solution:} See solutions to Homework 3 (extra credit).


\end{document}