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

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{5, Fri.}                    % !! start the paper

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
Figures 1--4 show different pictures of planar graphs.

\bparts

\ppart For each picture, describe its faces by listing the cycles
that form their boundaries.

\solution{
Figs 1 \& 2: abda, bcdb, abcda.
Fig 3: abcdea, adea,abda,bcdb.  Fig 4: abcda, abdea, abda, adea.
}

\ppart Which of the pictured graphs are isomorphic?  Which pictures represent the
same (abstract) \emph{planar drawing}?

\solution{
Figs 1 \& 2 have the same face boundaries, so are different pictures of the
\emph{same} planar drawing.  Figs 3 \& 4 both have four faces, but they are
different, for example, Figs 3 has a face with 5 edges, but the
longest boundary in Fig 4 has 4 edges.}

\eparts
\end{problem}


\begin{problem}
Prove that in a drawing of a connected planar graph

\bparts
\ppart every edge is traversed exactly twice by the face boundaries.

\solution{
By induction on the number, $n$, of edges in a planar drawing.  Base case
$n=0$ holds vacuously.  The inductive case works because rule (1) adds one
new edge which is traversed twice by the face in which it is drawn, and all
other faces are unchanged, and rule (2) divides the boundary of one face
into two parts, leaving the number of edge traversals on them unchanged,
adds a traversal of a new edge to each part, and leaves all other faces
unchanged.
}

\ppart if the graph has 3 or more vertices, then every face has length at
least 3 (more precisely, every face traverses edges at least 3 times).

\solution{By induction on the number, $n$, of edges in a planar drawing.
A connected graph with 3 vertices must have at least 2 edges, so we begin
with base case $n=2$.  In this case the graph must be a 2 edge line graph;
if its successive vertices are $a,b,c$, then it has a unique planar drawing
with one face with boundary $abcba$ which traverses each edge twice and so
has length 4.

The inductive case works because rule (1) adds 2 to the length of one face
and leaves the others unchanged, and an edge added by rule (2) can only
connect nonadjacent edges on a face boundary.  This means the face across
which the edge is drawn must have had length at least 4 and its boundary
splits into into two paths of length at least 2.  These paths each 
becomes the boundary of a new face by making one additional traversal of
the new edge, ensuring that both new faces have length at least 3.  All
other faces are unchanged by rule (2).}

\eparts

\end{problem}


\begin{problem}
Suppose we consider planar graphs that may \emph{not} be connected.  So in
addition to the parameters $v,e,f$ of Euler's formula, we also have the
number, $c$, of connected components in the graph.  In this case a face may
have a boundary consisting of several unconnected cycles, as in Figure 5.

\bparts

\ppart Use the additional parameter, $c$, to state a generalized version of
Euler's Formula that applies to possibly unconnected planar graphs.

\solution{
\[
v-e+f-c = 1.
\]}


\ppart Drawings of unconnected graphs use two additional rules: rule (3):
add a new vertex of degree 0, and rule (4) add an edge between vertices on
two different connected components.  Using these rules, explain how to
modify the inductive proof of Euler's formula to prove the generalized
version.

\solution{
By induction on the sum $n= e+v$.  The base case is $n=1$, which means
$v=1$, $e=0$, $f=1$ (just the outer face), and $c=1$, and $1-0+1-1 = 1$ as
required.  The inductive case for rules (1) and (2) is the same since they
do not change $c$.  Rule (3) increases $c$ and $v$ by 1 and leaves $f$ and
$e$ unchanged, so $v-e+f-c$ is unchanged.  Rule (4) increases $e$ by 1 and
decreases $c$ by 1 and leaves $v$ and $f$ unchanged, so $v-e+f-c$ is again
unchanged.
}

\eparts

\end{problem}

\iffalse  %Given out in class, but didn't get to it.  Maybe use on ps5.

\instatements{\newpage}

%S04 cp5f

\begin{problem}
Suppose that one domino can cover exactly two squares on a chessboard,
either vertically or horizontally.

\bparts

\ppart Can you tile an $8 \times 8$ chessboard with 32 dominos?

\mfigure{!}{1.6in}{figures/chess1}

\solution{Yes.  Place 4 vertical dominos in each column.}

\ppart Can you tile an $8 \times 8$ chessboard with 31 dominos if
opposite corners are removed?

\mfigure{!}{1.6in}{figures/chess2}

\solution{No!  Opposing corners are the same color.  Therefore,
removing opposite corners leaves an unequal number of white and black
squares.  Since every domino covers one black square and one white
square, no tiling is possible.}

%\instatements{\newpage}

\problempart Now suppose that an assortment of squares are removed
from a chessboard.  An example is shown below.

\mfigure{!}{1.6in}{figures/chess3}

Given a truncated chessboard, show how to construct a bipartite graph
$G$ that has a perfect matching if and only if the chessboard can be
tiled with dominos.

\solution{Create a vertex for every white square and a
vertex for every black square.  Put an edge between squares that share
an edge.  (This graph is bipartite, since the coloring of the squares
defines a valid 2-coloring of the vertices.)

If a perfect matching exists in this graph, then a tiling exists: put
a domino over each pair of matched vertices.  On the other hand, if a
tiling exists, then a perfect matching exists: match squares covered
by the same domino.}

\ppart Based on this construction and Hall's theorem, can you state a
necessary and sufficient condition for a truncated chessboard to be
tilable with dominos?  Try not to mention graphs or matchings!

\solution{A board can be tiled with dominos if and only if every set
of white squares is adjacent to at least as many black squares and
vice versa.}

\end{problemparts}

\end{problem}
\fi

\iffalse

%\instatements{\newpage}

%S04 cp5f

\begin{problem}
At Guiness brewery in the eary 1900's, W. S. Gosset (a chemist) and
E. S. Beaven (a ``maltster'') were working to improve barley.  Gosset
and Beavan planned to grow several varieties of barley in a field and
compare the yields.  However, local variations in the fertility of the
field might skew the results.  Their solution was to divide the field
into many small plots and grow each crop in several different places.

Similar thinking led to the use of {\em Latin squares} in experiment
design.  A Latin square is an $n \times n$ array of numbers such that
each row and each column contains every number from $1$ to $n$.  For
example, here is a $4 \times 4$ Latin square:

{\Large
\[
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
3 & 4 & 2 & 1 \\ \hline
2 & 1 & 4 & 3 \\ \hline
4 & 3 & 1 & 2 \\ \hline
\end{array}
\]
}

You can imagine that this array is an agricultural field where each
square is a small plot, and the number inside indicates the variety of
barley planted there.

There are some nice connections between Latin squares and graph
theory.  For example, see if you can construct a graph $G_n$ such that
there is a one-to-one correspondence between $n \times n$ Latin
squares and valid $n$-colorings of $G_n$.

\solution{Create a vertex in $G$ for each entry in the Latin Square.
Then connect each vertex to every other vertex in the same row and to
every other vertex in the same column.  Now color the graph with $n$
colors, each corresponding to a number between 1 and $n$.

Notice that every pair of vertices in the same row are connected, so
no two vertices in the same row can get the same color.  Similarly,
since every pair of vertices in the same column are connected, no two
vertices in the same column can get same color either.  These coloring
constraint match the constraints on Latin squares, so there is a
one-to-one correspondence between colorings of $G$ and $n \times n$
Latin squares.}
\end{problem}

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

%\instatements{\newpage}

\begin{problem}
A bipartite graph is {\em regular} if every vertex on the left has degree
$c$ and every vertex on the right has degree $d$.  Prove the following:

\begin{corollary*}
A regular bipartite graph has a matching for the vertices on the left
if $c \geq d > 0$.
\end{corollary*}

%(You may also find this corollary useful on the problem set!)

\solution{We use Hall's Theorem.  Let $L$ denote the set of vertices
on the left and $R$ denote the set of vertices on the right.  We must
show that every set of vertices $L' \subseteq L$ on the left is
adjacent to a set of vertices $R' \subseteq R$ such that $\card{L'}
\leq \card{R'}$.  If this condition holds, then Hall's theorem implies
that a matching for the vertices on the left exists.

Let $L' \subseteq L$ be a subset of vertices on the left, and let $R'
\subseteq R$ be the set of all vertices on the right adjacent to some
vertex in $L$.  Thus, every edge incident to a vertex in $L'$ is also
incident to a vertex in $R'$.  Therefore, the sum of the degrees of
the vertices in $L'$ is at most the sum of the degrees of vertices in
$R'$.  Thus, we have:

\begin{eqnarray*}
c \cdot \card{L'} & \leq & d \cdot \card{R'}
\end{eqnarray*}

Since $c \geq d > 0$ by assumption, this implies $\card{L'} \leq
\card{R'}$.  Thus, the desired condition holds.}
\end{problem}

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

%\instatements{\newpage}
\begin{problem}

\bparts

\ppart Suppose your teammate wrote only three lines of a $5 \times 5$
Latin square before deciding to chuck it all and become a maltster:

{\Large
\[
\begin{array}{|c|c|c|c|c|}
\hline
2 & 4 & 5 & 3 & 1 \\ \hline
4 & 1 & 3 & 2 & 5 \\ \hline
3 & 2 & 1 & 5 & 4 \\ \hline
  &   &   &   &   \\ \hline
  &   &   &   &   \\ \hline
\end{array}
\]
}

Can you fill in the last two lines to extend this ``Latin rectangle''
to a complete Latin square?

\solution{
Here is one possible solution:

{\Large
\[
\begin{array}{|c|c|c|c|c|}
\hline
2 & 4 & 5 & 3 & 1 \\ \hline
4 & 1 & 3 & 2 & 5 \\ \hline
3 & 2 & 1 & 5 & 4 \\ \hline
1 & 5 & 2 & 4 & 3 \\ \hline
5 & 3 & 4 & 1 & 2 \\ \hline
\end{array}
\]
}
}

\ppart Show that filling in the next row of a Latin rectangle is
equivalent to finding a matching in some bipartite graph.

\solution{Construct a bipartite graph as follows.  The
vertices on the left are the columns of the Latin rectangle, and the
vertices on the right are the numbers $1$ to $n$.  Put an edge between
a column and a number if the number has {\em not yet appeared} in the
column.  Thus, a matching in this graph would associate each column
with a distinct number that has not yet appeared in that column.
These numbers would form the next row of the Latin rectangle.}

\ppart Prove that a matching must exist in this bipartite graph and,
consequenctly, a Latin rectangle can always be extended to a Latin
square.

\solution{First, we show that the bipartite graph described above has
a matching.  Each column-vertex on the left has degree $n - k$ and
each number-vertex on the right has degree $n - k$ as well.
Therefore, a matching for the columns exists by the corollary in the
preceding problem.  This implies that we can add rows to the Latin
rectangle by the procedure described above as long as $k < n$.  At
that point, we have a Latin square.}

\eparts

\end{problem}

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

%from q1 S04]

\begin{problem}
GraphTech corporation has built cell phone towers all across the
United States.  Now they need your help with a couple technical
problems.

\bparts

\ppart Each tower uses a certain frequency.  Two towers can not use
the same frequency if they are within 100 miles of each other.
GraphTech needs to know how many frequencies they must purchase.

Model this as a graph problem.  What are the vertices?  What are the
edges?  What graph-related quantity determines the minimum number of
frequencies required?

\solution{The vertices are towers.  There is an edge
between two towers if they are within 100 miles.  The minimum number
of frequencies is the chromatic number of the graph.}

\ppart Callers across the United States will try to use GraphTech's
cell phone service the moment that service is activated.  A caller can
only contact a tower that is within 20 miles.  Each tower can support
up to 5 callers.  GraphTech must try to handle the load.

Model this as a graph problem.  What are the vertices?  What are the
edges?  State a necessary and sufficient condition based on Hall's
Theorem for GraphTech's network to be able to handle all the callers
in the first moment of operation.

\solution{There is one vertex for each caller, and there are five
vertices for each tower.  There is an edge between a caller and all
five vertices of each tower within 20 miles.  A matching for the
callers now assigns each caller to a tower such that no tower is
assigned more than 5 callers.  Thus, by Hall's Theorem, all callers
can be serviced if and only if every set of callers is within range of
at least one-fifth as many towers.}

\eparts

\end{problem}


%\instatements{\newpage}

\newtheorem*{conjecture*}{Conjecture}

Some simple questions in graph theory still await resolution by an
ingenious 6.042 student!  Prove or disprove:

\begin{conjecture*}[Erd\"{o}s-Gyarfas]
Every graph with mimimum degree at least 3 has a cycle whose length is
a power of 2.
\end{conjecture*}

Now that doesn't seem so hard\dots.  But this is an open problem.
Reportedly, Paul Erd\"{o}s, a great Mathematician famous famous, among
other things, for problem solving prize offers, offered \$100 for a proof
and \$50 for a counterexample.  \fi

\end{document}
