\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{textcomp} % to get \textcent
\usepackage{epsfig}

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document} 
\inclassproblems{4, Wed}                    % !! start the paper

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\begin{problem}
Color the following graphs with the minimum possible colors, such no
two adjacvent vertices have the same color.
\mbox{}
\begin{figure}[htb]
\begin{center}
%\input{/toc/pub/www/classes/6.042/fall01/figures/j-sol.latex}
\includegraphics[width=\textwidth]{figures02/cp4W-prob1}
\end{center}
\end{figure}

\solution{

%{\em TA NOTES: (comment out before publishing). Will spend at least 10
%minutes on this, perhaps more of going well. Things to suggest: how do
%you prove this a valid coloring (e.g. check the ends of all edges),
%how do you prove that you cannot color this graph with fewer colors,
%how would you generalize any of the graphs to n vertices, etc. Could
%use the board to write a proof.}


\mbox{}
\begin{figure}[htb]
\begin{center}
%\input{/toc/pub/www/classes/6.042/fall01/figures/j-sol.latex}
\includegraphics[width=\textwidth]{figures02/cp4W-prob1sol}
\end{center}
\end{figure}

}
\end{problem}

%%-----------------------------------------------------------
\newpage
\newpage
{\it Definition:} The degree of a vertex is the number of edges
connecting it to other vertices.

{\it Theorem:} The sum of the degrees of the vertices in a simple
graph equals twice the number of edges, i.e. $2|E| = \sum_{v \in V}
deg(v)$.

{\it Handshaking Theorem:} In every graph, there are an even number
of vertices of odd degree.

\begin{problem}
Prove that in any undirected graph, the sum of the squares of
the vertex degrees is even, or provide a counterexample.
\end{problem}
\solution{The assertion is true. 

{\em Proof 1}

Let $V_e$ be the set of even degree vertices and $V_o$ the set of odd
degree vertices of the graph.  From class we know that there is an
even number of odd degree vertices. So can write

\begin{equation}\label{eq3}
\sum_{v \in V} deg(v)^2 = 
\sum_{v \in V_e} deg(v)^2 + \sum_{v \in V_o} deg(v)^2
\end{equation}

If $v \in V_e$ then $deg(v)$ is even, hence $deg(v)^2$ is also even.
Therefore, the first term in the right hand side of (\ref{eq3}) is
even.  Similarly if $v \in V_o$, then $deg(v)^2$ is odd.  The second
term in the right hand side is a sum of odd numbers with an even
number of terms.  Therefore it is also even.  We conclude that
$\sum_{v \in V} deg(v)^2$ is even

{\em Proof 2}

Let $E$ be the set of edges of the graph and
$V = \{ v_1, \ldots , v_n \}$ be the set of vertices of the graph.

\begin{equation}\label{eq1}
(\sum_{i=1}^n deg(v_i))^2 = \sum_{i=1}^n deg(v_i)^2 +
2 \sum_{i \neq j} deg(v_i) deg(v_j)
\end{equation}

The left hand side of (\ref{eq1}) is even because $ \sum_{i=1}^n
deg(v_i) = 2|E|$ and the second part of the right hand side is
obviously even.  Therefore $\sum_{i=1}^n deg(v_i)^2$ is even. 
}

%------------------------------------------------------------
\begin{problem}
\newcommand{\dmax}{\ensuremath{dmax}\xspace}
\newcommand{\dmaxpr}{\ensuremath{dmax'}\xspace}

Prove that it is possible to color a graph $G$ with $\dmax +1$ colors,
where \dmax represents the maximum degree of any node in $G$.

\solution{ 

%{\em TA NOTES: (comment out before punblsihing solution). Allow
%students to consider alternate ways of proving this. Suggest induction
%on size of graph only after they've thought about it. If they come up
%with induction first, then ask them to consider other ways they could
%prove this. Ask groups to write up induction proof on the board.}

There are many different ways of proving this claim. Here we'll use
induction on the size of the graph. This approach also yields a
recursive algorithm for coloring the graph.

\begin{proof}
Let $P(n)$ be the predicate that it is possible to color every
$n$-vertex graph G with at most $\dmax +1$ colors.

\paragraph{Base case:} Consider a graph G with 1 vertex ($n=1$). This vertex has
degree zero, so $\dmax =0$. Since we can color that lone vertex with
$\dmax +1 =1 $ color, $P(1)$ holds.

\paragraph{Inductive step:} we assume $P(n)$ to prove $P(n+1)$.
Consider an $(n+1)$-vertex graph $G$ with maximum degree \dmax. Let
$G'$ be the graph obtained from $G$ by (temporarily) removing an
arbitrary vertex $v$ and all incident edges and let \dmaxpr be its
maximum degree. Since $G'$ now has $n$ vertices, we can apply the
inductive hypothesis which says that we can color it with at most
$\dmaxpr +1$ colors.

We now add vertex $v$ to get back $G$. This cannot \emph{decrease} the
maximum degree, so $\dmax \geq \dmaxpr$. Therefore, $\dmax +1$ colors
suffice to color all the nodes other than $v$ (that is, $G'$). As for
$v$, since it can have degree at most $\dmax$, it has at most $\dmax$
neighbors and we have $\dmax +1$ colors at our disposal, so we can
always pick one which is not used by any of its neighbors.

This proves that $G$ is also colorable, hence $P(n+1)$ is true.

\end{proof}

Note that this theorem implies, for example, that a graph with
thousands of vertices, each of degree 3, requires at most 4 colors. So
for example the whole US worth of wireless devices would only require
a number of distinct frequencies comparable to the local radius
(neighborhood) of a single wireless device (as opposed to the number
of total devices).  }

\end{problem}

%-------------------------------------------------------------
% \begin{problem}

% Let $G$ be a graph with $n$ vertices and $m$ edges. Let $dmax$ be the
% maximum degree of the vertices of $G$, and let $dmin$ be the minimum
% degree of the vertices of $G$. Show that
% \begin{problemparts}
% \problempart $2m/n \geq dmin$.

% \solution{We want to show that $2m \geq n\cdot dmin$. Observe that $2m$
% is the sum of the degrees of all the vertices (each of the $m$ edges
% adds 2 to the total sum since it increases the degree of each of its
% two incident vertices by 1). The sum of the $n$ degrees cannot be less
% than $n$ times the minimum degree. In other words,  $2m \geq n \cdot
% dmin \implies 2m/n \geq dmin$.  

% }

% \problempart $2m/n \leq dmax$.

% \solution{Similarly, the sum of the $n$ degrees cannot be greater
% than $n$ times the maximum degree. So,  $2m \leq n \cdot
% dmax \implies  2m/n \leq dmax$.
% }

% \end{problemparts}
% \end{problem}

\end{document}


