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

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

\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Prove the following corollary, which is stated in the course notes.

\begin{corollary*}
A connected graph has an Euler walk if and only if either 0 or 2
vertices have odd degree.
\end{corollary*}
\end{problem}

\solution{Suppose that a connected graph has an Euler walk.  The walk
traverses 2 edges incident to a vertex each time it visits that
vertex.  The walk also traverses 1 edge incident to each endpoint at
the beginning and end of the walk.  Therefore, the graph has 2
vertices of odd degree if the endpoints are distinct, and 0 vertices
of odd degree if the endpoints are the same.

Now suppose that a connected graph has either 0 or 2 vertices of odd
degree.  If there are 0 vertices of odd degree, then the graph has an
Euler tour by the original theorem, and so the graph has an Euler
walk.  If there are 2 vertices of odd degree, $u$ and $v$, then add
edge $\edge{u}{v}$.  The resulting graph has 0 vertices of odd degree
and thus has an Euler tour.  Deleting edge $\edge{u}{v}$ from the tour
yields an Euler walk on the original graph.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Every vertex in graph $G$ has degree at least $k$.  Prove that $G$
contains a path of length $k$.
\end{problem}

\solution{Let $P$ be the longest path in $G$.  Let $x$ be one
endpoint of the path $P$.  Now $x$ is adjacent to at least $k$ other
vertices.  All of these must lie on path $P$; otherwise, the path
could be extended.  Therefore, $P$ contains at least $k + 1$ vertices,
including $x$, and thus has length at least $k$.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
The course notes prove that a graph can be colored with $k + 1$
colors, provided every vertex has degree at most $k$.  Use some kind
of induction to prove the following, related assertion.

\begin{theorem*}
Let $k$ be a positive integer.  If every vertex in a connected graph
$G$ has degree at most $k$ and some vertex in $G$ has degree less than
$k$, then $G$ is $k$-colorable.
\end{theorem*}

Suggestion: Although $k$ is the only integer variable explicitly named
in the problem statement, nothing is forcing you to use induction on
$k$.  In fact, most graph-related induction proofs use induction on
the number of vertices or the number of edges.

\solution{We use induction on the number of vertices in the graph $G$,
which we denote by $n$.  The induction hypothesis is, ``If every
vertex in a connected $n$-vertex graph $G$ has degree at most $k$ and
some vertex has degree less than $k$, then $G$ is $k$-colorable.''
First, suppose that $G$ is a connected graph with $n = 1$ vertices.
Then the claim holds, since $G$ is $k$-colorable for every positive
integer $k$.

Next, assume that the claim holds for every connected graph with $n
\geq 1$ vertices.  Let $G$ be a connected graph with $n + 1$ vertices.
Let $x$ be a vertex in $G$ with degree less than $k$.  Remove $x$ and
all incident edges from $G$.  This may decomponse $G$ into several
connected components $G_1$, $G_2$, \ldots, each with a vertex
previously adjacent to $x$.

\mfigure{!}{1.5in}{ps4-components}

Each of these previously-adjacent vertices now has degree at most $k -
1$.  Thus, we can $k$-color each connected component by induction.
Now add back $x$ and all incident edges.  Since $x$ is adjacent to
fewer than $k$ other vertices and $k$ colors are available, we can
color $x$ differently from all its neighbors.  Therefore, the claim
holds for every connected graph with $n+1$ vertices as well.  The
theorem follows by induction.  }

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Scholars through the ages have identified {\em twenty} fundamental
human virtues: honesty, generosity, loyalty, prudence, completing the
weekly 6.042 reading-response email, etc.  At the beginning of the
term, every student in 6.042 possessed exactly {\em eight} of these
virtues.  Furthermore, every student was unique; that is, no two
students possessed exactly the same set of virtues.  The 6.042 course
staff must select {\em one} additional virtue to impart to each
student by the end of the term.  Prove that there is a way to select
an additional virtue for each student so that every student is unique
at the end of the term as well.

Suggestion: Use Hall's theorem.  Try various interpretations for the
vertices on the left and right sides of your bipartite graph.

\solution{Construct a bipartite graph $G$ as follows.  The vertices on
on the left are all students and the virtues on the right are all
subset of nine virtues.  There is an edge between a student and a set
of 9 virtues if the student already has 8 of those virtues.

Each vertex on the left has degree 12, since each student can learn
one of 12 additional virtues.  The vertices on the right have degree
at most 9, since each set of 9 virtues has only 9 subsets of size 8.

Therefore, by the special case of Hall's Theorem proved in the
in-class problems on Friday, there is a matching for the students.
Thus, if each student is taught the additional virtue in the set of 9
virtues with whom he or she is matched, then every student is unique
at the end of the term.
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
For each integer $n \geq 0$, we can define a graph called an {\em
$n$-cube}, which is denoted $H_n$.  The vertices are all $n$-bit
sequences, $\set{0, 1}^n$.  There is an edge between two vertices if
they differ in exactly one bit position.

\mfigure{!}{1.25in}{ps4-ncubes}

\bparts

\ppart Prove that $H_n$ is bipartite for all $n$.

\solution{We prove that the $n$-cube is bipartite by describing an
explicit 2-coloring.  Each vertex is an $n$-bit sequences, $b_1 b_2
\ldots b_n$.  Color a vertex red if $b_1 + b_2 + \ldots + b_n$ is
even, and color the vertex blue if the sum is odd.  Since adjacent
vertices differ in exactly one bit, one must have an even sum and the
other an odd sum.  Therefore, the endpoints of every edge are colored
differently.}

\ppart Prove that $H_n$ has a Euler tour for all even $n \geq 2$.

\solution{We prove that $H_n$ has an Euler tour by showing that it is
connected and every vertex has even degree.

First, consider two arbitrary vertices in an $n$-cube, $b_1 b_2 \ldots
b_n$ and $c_1 c_2 \ldots c_n$.  These two vertices are joined by a
path which traverses the distinct vertices in the following sequence:

\[
\begin{array}{c}
b_1 b_2 b_3 \ldots b_n \\
c_1 b_2 b_3 \ldots b_n \\
c_1 c_2 b_3 \ldots b_n \\
\ldots \\
c_1 c_2 c_3 \ldots c_n \\
\end{array}
\]

Therefore, the graph is connected.

Each vertex $v$ in an $n$-cube is adjecent to exactly $n$ other
vertices, those which can be obtained by flipping one of the $n$ bits
of vertex $v$.  Therefore, if $n$ is even, every vertex in an $n$-cube
has even degree.  Thus, $H_n$ has an Euler tour for all even $n \geq
2$.}

\ppart Prove that $H_n$ has a Hamiltonian cycle for all $n \geq 2$.
Consider an inductive argument based on the fact that $H_{n+1}$
consists of two subgraphs isomorphic to $H_n$ (bold lines) with
corresponding vertices joined (dotted lines):

\mfigure{!}{1.25in}{ps4-ncube-construction}

\solution{We use induction on $n$.  Let $P(n)$ be the proposition that
an $n$-cube has a Hamiltonian cycle.  A $2$-cube is itself a cycle on
four vertices, so $P(2)$ is true.  Now suppose that $P(n)$ is true for
some $n \geq 2$, and consider an $(n+1)$-cube.  As noted in the
suggestion, this graph consists of two subgraphs isomorphic to the
$n$-cube, with corresponding vertices joined by edges.  By induction,
there is a Hamiltonian cycle $C_n$ in one of these two subgraphs and a
corresponding Hamiltonian cycle $C_n'$ in the other.  Deleting an edge
$\edge{u}{v}$ from $C_n$, deleting the corresponding edge $\edge{u'}{v'}$
from $C_n'$, and adding the edges $\edge{u}{u'}$ and $\edge{v}{v'}$
creates a Hamiltonian cycle in the $(n+1)$-cube.  Therefore, $P(n+1)$
is true, and the claim follows by the principle of induction.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Let's say that a graph has ``two ends'' if it has exactly two vertices
of degree 1 and all its other vertices have degree 2.  For example,
here is one such graph:

\mfigure{!}{0.75in}{ps4-path}

\bparts

\ppart Prove that the following theorem is false by drawing a
counterexample.

\begin{falsethm*}
Every two-ended graph is a path.
\end{falsethm*}

\solution{
A graph consisting of a path together with a cycle is a counterexample.
}

\ppart Point out the first erroneous statement in the following
``proof'' of the false theorem.  Describe the error as best you can.

\begin{proof}
We use induction.  The induction hypothesis is that every two-ended
graph with $n$ edges is a path.  First, we show that the induction
hypothesis holds for $n = 1$.  The only two-ended graph with a single
edge consists of two vertices joined by an edge:

\mfigure{1.5in}{!}{ps4-oneedge}

Sure enough, this is a path.

Next, we assume that the induction hypothesis holds for some $n \geq
1$ and prove that it holds for $n + 1$.  Let $G_n$ be any two-ended
graph with $n$ edges.  By the induction assumption, $G_n$ is a path.
Now suppose that we create a two-ended graph $G_{n+1}$ by adding one
more edge to $G_n$.  This can be done in only one way: the new edge
must join an endpoint of $G_n$ to a new vertex; otherwise, $G_{n+1}$
would not be two-ended.

\mfigure{!}{1in}{ps4-induction}

Clearly, $G_{n+1}$ is also a path.  Therefore, the induction
hypothesis holds for all graphs with $n+1$ edges.  The theorem follows
by the principle of induction.
\end{proof}

\solution{The first error is in the statement, ``Therefore, the
induction hypothesis holds for all graphs with $n+1$ edges.''  We have
not shown that the hypothesis holds for {\em all} two-ended graphs;
rather, we have only shown that the induction hypothesis holds for
those two-ended graphs {\em that can be obtained by adding one more
edge to an existing two-ended graph}.  This is not all two-ended
graphs, as the counterexample demonstrates.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
