\documentclass[12pt]{article}   

\usepackage{latex-macros/course}% !! Use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip
                                % query 

\renewcommand{\reading}{Week 5 Notes and Undirected Graphs section of Week 4 Notes}

\begin{document}

\problemset{4}                  % !! Start the problem set with its number

\begin{problem}
For functions $f:A \to B$ and $g:B \to C$, the composition of $g$ and $f$,
written $g \circ f$, is the function $h: A \to C$ where
\[
h(a) \eqdef g(f(a)).
\]

\bparts
\ppart Prove that if $f$ and $g$ are bijections, then so is $g \circ f$.

\ppart Prove that if $f:A \to B$ is a bijection, then there is a
bijection, $e: B \to A$ such that $e \circ f = I_A$, where $I_A : A \to A$
and $I_A(a) \eqdef a$ for all $a \in A$.

\ppart Prove that graph isomorphism is an equivalence.
\eparts

\end{problem}


\begin{problem}
The proof of the Handshake Theorem in Week 5 Notes is a little more
informal than is desirable in the beginning of 6.042.  Rewrite the proof more
carefully as an induction on the number of edges in a graph.
\end{problem}


\begin{problem}
The \term{distance} between two vertices in a graph is the length of the
shortest path between them.  For example, the distance between two
vertices in a graph of airline connections is the minimum number of
flights required to travel between two cities.  The \term{diameter} of a
graph is the distance between the two vertices that are farthest apart.

\bparts
\ppart  What is the diameter of the following graph?  Briefly explain your
answer.

\mfigure{!}{1.75in}{figures/distance-graph}

\solution{
The diameter of the graph above is 5.  The
most-distant vertices are $A$ and $G$, which are at distance 5 from
one another.
}

\ppart What is the chromatic number of this graph?  Prove it.

\solution{It's easy to find a 3-coloring, for example, let $C,D,E$ be
colored $c, d, e$, then color $B$, $H$ and $F$ with color $d$, and $G$ and
$H$ with $e$.  The chromatic number cannot be less than 3, because
vertices $C,D,E$ are all connected and therefore must receive distinct
colors.  Consequently, the chromatic number of the graph is exactly 3.}

\ppart Suppose every vertex in a graph is within distance $n$ of a vertex,
$v$.  Prove that the diameter of the graph is at most $2n$.

\solution{
Let $x$ and $y$ be arbitrary vertices in the graph.  Then there exists
a path of length at most $d$ from $x$ to $v$, and there exists a path
of length at most $d$ from $v$ to $y$.

\mfigure{!}{1.5in}{figures/diameter-bound}

Let $z$ be the vertex that lies on both the $x$-to-$v$ and $v$-to-$y$
paths and is closest to $x$.  (We know that such a vertex exists, since
$z$ could be $v$, at least.)  Joining the $x$-to-$z$ segment to the
$z$-to-$y$ segment gives a path from $x$ to $y$ of length at most $2n$.
Therefore, every vertex is within distance $2n$ of every other.}


\eparts
\end{problem}


\begin{problem}
If a graph is connected, then every vertex must be adjacent to some
other vertex.  Is the converse of this statement true?  If every
vertex is adjacent to some other vertex, then is the graph connected?
The answer is no.

\bparts 

\ppart Give a minimal example of a graph in which every vertex is adjacent
to at least one other vertex, but the graph is not connected.

\ppart So something is wrong with the following proof.  Exactly where is
the first mistake in the proof?

\begin{falsethm}
If every vertex in a graph is adjacent to another vertex, then the
graph is connected.
\end{falsethm}

Nothing helps a false proof like a good picture; see
Figure~\ref{fig:false}.

\begin{figure}[htbp]
\centering \includegraphics[height=1.5in]{figures/false}
% \centerline{\psfig{figure=figures/false.eps,height=1.5in}}
\caption{\em This picture accompanies the false proof.  Two situations
are depicted.  In one, vertices $x_1$ and $x_2$ both are among the
vertices of $G$, and so there is a connecting path by induction.
In the second, $v = x_1$ and $x_2$ is a vertex of $G$.
In this case there is a connecting path because there is an edge from
$v$ to $u$ and a path in $G$ from $u$ to $x_2$ by induction.}
\label{fig:false}
\end{figure}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the predicate that if every
vertex in an $n$-vertex graph is adjacent to another vertex, then the
graph is connected.  In the base case, $P(1)$ is trivially true
because there is only one vertex.

In the inductive step, we assume $P(n)$ to prove $P(n+1)$.  Start with an
$n+1$-vertex graph, $G'$, in which every vertex is adjacent to another
vertex.  Now take some vertex $v$ away from the graph and let the $G$ be
the remaining graph.  By assumption $v$ is adjacent in $G'$ to one of the
$n$ vertices of $G$; call that one $u$.

Now we must show that for every pair of distinct vertices $x_1$ and $x_2$
in $G'$, there is a path between them.  If both $x_1$ and $x_2$ are
vertices of $G$, then since $G$ has $n$ vertices, we may assume by
induction it is connected.  So there is a path between $x_1$ and $x_2$.
Otherwise, one of the vertices is $v$ (say $x_1$) and the other, $x_2$ is
in $G$.  But $x_2$ is connected to $u$ by induction, so there is a path
from $x_1$ to $u$ to $x_2$ as shown in the figure.
\end{proof}

\solution{
The error is in the statement ``\emph{since $G$ has $n$ vertices, we may
assume by induction it is connected.}''  The induction hypothesis does not
say that every $n$-vertex graph is connected, but only, ``{\em if every
vertex in an $n$-vertex graph is adjacent to another vertex,} then the
graph is connected''.  For example, if $G'$ is the graph with vertices 1,
2, 3, 4 and edges $\set{1,2}$ and $\set{3,4}$, then removing vertex 1 to
form $G$ leaves vertex 2 without an adjacent vertex in $G$, and we can't
conclude by induction that $G$ is connected (which of course it isn't).
}

\eparts

\end{problem}

\begin{problem}

\bparts
\ppart\label{d5} Show that every planar graph has a node of degree at most $5$.
\hint Use the $3v-6$ inequality. 

\solution{Consider some planar graph $G$.  Take any connected
  component $H$ of $G$.  If $H$ has at most 2 vertices,
  then every vertex in $H$ has degree at most 1.  Otherwise, for the
  sake of contradiction suppose that every vertex in $H$ has degree at
  least $6$.  Then
\[
2e = \sum_{n \in V}\text{deg}(n) \geq \sum_{n \in V}6 = 6v >6v-12,
\]
contradicting the fact that $e \leq 3v-6$ in any connected planar
graph with more than 2 vertices.}

\ppart Conclude that \emph{any} planar graph can be colored with six
colors.

\solution{The proof is almost identical to the proof in Week 5 Notes that
a graph with maximum degree $d$ is $d+1$ colorable.

The proof is by strong induction on the number, $v$, of vertices.  The
induction hypothesis is
\[
P(v): \text{A planar graph with $v$ vertices can be colored with at most $6$
colors.}
\]

{\bf Base cases ($v \leq 6$):} $P(v)$ is true because each vertex can be
assigned a different color.

{\bf Inductive step:} Assume $P(v)$ is true for some $v \geq 6$ and show
that $P(v+1)$ is true.

%Let $G$ be a planar graph with $v+1$ vertices.  If $G$ is not connected,
%then each of its components is a planar graph with at most $v$ vertices,
%so by strong induction hypothesis it is 6-colorable.  Using the same 6
%colors to color each component, the separate colorings of each component
%together define a 6-coloring of the whole graph.

%Otherwise, $G$ is connected, so 
Let $G$ be a planar graph with $v+1$ vertices. By part~(\ref{d5}),
there is a node, $n$, of degree $\leq 5$.  Let $G'$ be the subgraph of
$G$ obtained by removing node $n$ and all edges incident to it.

Now $G'$ has $v$-vertices and is also planar, so by induction hypothesis,
$G'$ can be colored with $6$ colors.  Now re-attach $n$.  Since $n$ is
adjacent to at most $5$ vertices, there is a 6th color for $n$ different
from colors of its adjacent vertices.  This yields a 6-coloring of $G$.

We have shown that $P(v) \rightarrow P(v+1)$, so the proof is complete.
}
\eparts
\end{problem}




\end{document}
