\documentclass[twoside,12pt]{article}
\usepackage{light}
\usepackage{subfigure}

\showsolutions
%\hidesolutions

\newcommand{\edge}[2]{#1\text{---}#2}

\begin{document}

\problemset{4}{September 28, 2004}{Monday, October 4 by 9PM
%[\stamp]
}

%[Problem 6(a) slightly revised, 10/3, 10am.]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% TOPICS: Adjacency matrices, coloring
% From: f01-ps4-2.tex

\begin{problem}[10 points]
The adjacency matrix of a graph is given below.

\[
\left[
\begin{array}{cccccc}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0
\end{array}
\right]
\]

\bparts

\ppart Draw the graph defined by this adjacency matrix.  Label
the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
corresponds to row and column $i$ of the matrix.

\solution{ 
\begin{center}
\includegraphics[width=2in,height=2in]{adjgraph}
\end{center}
%\centerline{\resizebox{!}{2.0in}{\includegraphics{adjgraph}}}
}

\ppart What is the diameter of this graph? Explain why.

\solution{This graph has diameter $2$.  There are three pairs of vertices
such that the distance between them is two: $\set{1,5}, \set{2,3}$ and
$\set{4,6}$.  There is an edge between all other pairs of vertices, and
hence the distance between those pairs is $1$.}


\ppart Find a cycle in this graph of maximum length and explain
why it has maximum length.

\solution{
The cycle 1-6-3-4-5-2-1 has length 6.
\iffalse

\textbf{NICKH VERSION:
The cycle with edges $\{\edge{1}{6}, \edge{6}{3}, \edge{3}{4},
 \edge{4}{5}, \edge{5}{2}, \edge{2}{1} \}$ has length 6.}
\fi

Since any cycle can contain each vertex at most once, no cycle can have
length greater than 6.  Therefore the stated cycle has maximum length.}


\ppart Give a coloring of the vertices that uses the minimum
number of colors. Prove that this a minimum coloring.

\solution{The diagram above shows a 3-coloring.  The chromatic number
cannot be less than 3, because vertices 1, 2, and 4 are all connected
and therefore must receive distinct colors.  Consequently, the
chromatic number of the graph is exactly 3.}

\eparts
\end{problem}


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

% TOPICS: Isomorphism
% From: Essentially taken from the Course Notes for the University of Waterloo class C&O 230.

\begin{problem}[20 points]
A property of a graph is said to be \emph{preserved under isomorphism} if
whenever $G$ has that property, every graph isomorphic to $G$ also has
that property.  For example, the property of having five vertices is
preserved under isomorphism: if $G$ has five vertices then every graph
isomorphic to $G$ also has five vertices.

In the following questions, you will asked to be prove whether certain pairs of graphs
are isomorphic.
If they are isomorphic, you can prove this by writing down an isomorphism.
If they are not, you can prove this by giving a property $p$ that is preserved under isomorphism
such that one graph has property $p$ but the other does not.
You do not need to prove that your chosen property is preserved under isomorphism.

\begin{figure}[h]
\begin{center}
\mbox{  \subfigure[$G_1$]{\includegraphics[width=2in,clip]{G1}}
        \hspace{17mm}
        \subfigure[$G_2$]{\includegraphics[width=2in,clip]{G4}} }
\mbox{  \subfigure[$G_3$]{\includegraphics[width=2in,clip]{G2}}
        \hspace{17mm}
        \subfigure[$G_4$]{\includegraphics[width=2in,clip]{G3}}
        }
\end{center}
\end{figure}

\bparts

\ppart  Are the graphs $G_1$ and $G_2$ isomorphic?

\solution{ 
No. Let $p$ be the property that the graph has a vertex of degree four.
Then $G_2$ has property $p$ but $G_1$ does not. }


\ppart  Are the graphs $G_1$ and $G_3$ isomorphic?

\solution{ 
Yes. The following function is an isomorphism from $G_1$ to $G_3$:
\begin{align*}
&f(1)=1 \quad&& f(2)=2 \quad&& f(3)=3 \quad&& f(4)=8 \quad&& f(5)=9 \\
&f(6)=10 \quad&& f(7)=4 \quad&& f(8)=5 \quad&& f(9)=6 \quad&& f(10)=7
\end{align*}
}

\ppart  Are the graphs $G_1$ and $G_4$ isomorphic?

\solution{ 
No. Let $p$ be the property that the graph has a cycle of length four.
Then $G_4$ has property $p$ but $G_1$ does not. }

\eparts

\end{problem}


\iffalse  use on quiz?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% From: f01-ps4-5.tex
%-----------------------------------------------
% source: Spring 95 Quiz 1, pRepository
% topics: graph connectivity


\begin{problem}[20 points]
The {\em complement} of an undirected graph $G=(V,E)$ is the
graph $\bar{G}=(V, \bar{E})$.  That is, $\bar{G}$ contains exactly
those edges that are not in $G$.  Prove that if $G$ is not connected
then $\bar{G}$ is.

\noindent \textit{Hint:} Consider two separate cases: vertices in
different components of $G$ and vertices in the same component of $G$.

\solution{
  Suppose $G=(V,E)$ is not connected.  Then $G$ can be divided into
  nonempty disjoint connected components $G_1, G_2, \ldots G_k$ (where
  $k>1$).  Consider any two vertices $a, b$ in $V$.  Let's show that they
  are connected by a path in $\bar{G}$.
\begin{description}

\item[Case 1]  \ $a$ and $b$ are in different connected components of
$G$.  Then there is no edge in $E$ connecting $a$ and $b$.  Thus $\bar{E}$
contains an edge connecting $a$ and $b$.

\item[Case 2]  \ $a$ and $b$ are in the same connected component of
$G$.  Let $c$ be a vertex in a different connected component.  By case
1, $a$ and $c$ are connected, as are $b$ and $c$.  Thus $a$ and $b$ are
connected through $c$.

\end{description}
Thus $\bar{G}$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $\bar{G}$ is connected.
}

\end{problem}
\fi

%% revised from S04, class problems 7, wednesday
%% used F03 rec4, Fall99 Q2, prob 4, Final exam Fall02

\begin{problem}[20 points]
The following operations will be applied to a graph: pick any two vertices
$u \neq v$.
\begin{enumerate}

\item\label{del} If there is an edge of between $u$ and $v$ and there is
also a path from $u$ to $v$ which does \emph{not} include this edge, then
\textbf{delete} the edge $\set{u,v}$.

\item\label{add} If there is no path from $u$ to $v$, then \textbf{add}
the edge $\edge{u}{v}$.

\end{enumerate}
Keep repeating these operations until it is no longer possible to find two
vertices $u \neq v$ to which an operation applies.  A graph to which no
operation applies is called ``stuck.''

\bparts

\ppart Let $G$ be the graph with vertices $\set{1,2,3,4}$ and edges
\[
\set{\set{1,2},\set{3,4}}
\]
Draw all the stuck graphs possible when starting with $G$.

\solution{It's not possible to delete any edge.  The procedure can only
add an edge connecting exactly one of vertices 1 or 2 to exactly one of
vertices 3 or 4, and then terminate.  So there are four possible graphs to
get stuck at.}

\ppart Prove that a graph that is stuck must be a tree.

\solution{We show that a stuck graph must be connected and cycle-free.
We know from the Notes that this implies it is a tree.

If a graph is not connected, then there must be two vertices with no path
between them.  So operation~\ref{add} would allow an edge to be added
between them, which means the graph was not stuck.  So a stuck graph must
be connected (contrapositve).

Similarly, if a graph had a cycle, then operation~\ref{del} would allow
an edge to be deleted from the cycle, which means the graph was not stuck.
So a stuck graph must be cycle-free.}

\ppart \label{derived} Let $e$ be the number of edges in $G$, let $c$ be
the number of connected components it has.  Show that the value of $3c +
2e$ gets smaller when either operation is applied.  Conclude that no matter how
you apply the operations to a graph, you will get stuck.

\solution{Operation~\ref{del} for deleting an edge decreases $e$ by 1, but
ensures that exactly the same vertices remain connected after the
deletion, i.e., $c$ does not change.  So $3c+2e$ decreases by 2.

Operation~\ref{add} for adding an edge ensures that the number of
connected components $c$ decreases by one and the number of edges $e$
increases by one.  Therefore $3c+2e$ decreases by $1$.

In particular, since $3c+2e$ is always positive, it's not possible to
apply the operations more that $3c+2e-1$ times before getting stuck.
}

\eparts
\end{problem}


\begin{problem}[20 points]

\begin{theorem}\label{bip}
A graph $G$ is bipartite if and only if it contains no odd cycle.
\end{theorem}

We'll walk you through a proof.  As is common with ``if and only if''
assertions, the proof has two parts.  Part (a) asks you to prove that
the left side of the ``if and only if'' implies the right side.  Parts
(b), (c) and (d) help you prove that the right side implies the
left.

\bparts

\ppart Assume the left side and prove the right side.  Three to five
sentences should suffice.

\solution{Select a 2-coloring of $G$.  Consider an arbitrary cycle with
vertices $v_1, v_2, \ldots, v_k$.  Then the vertices $v_i$ must be one
color for all even $i$ even and the other color for all odd $i$.  Since
$v_1$ and $v_k$ must be colored differently, $k$ must be even.  Thus, the
cycle has even length.}

\ppart Explain why there is a 2-coloring of any tree, $T$.

\solution{Select a ``root'' vertex $v_0$ arbitrarily.  Color a vertex $v$
red if the distance in $T$ from $v_0$ to $v$ is even, and color $v$ black
if the distance from $v_0$ is odd.

To see that this defines a 2-coloring of $T$, let $\edge{x}{y}$ be an edge
of the tree.  We must show that $x$ and $y$ are assigned different colors.

Consider the unique path from $v_0$ to $x$.  If this path used
$\edge{x}{y}$, then it went through $y$ just before $x$, so the distance
from $v_0$ to $x$ was one greater than the distance to $y$.  If the path
did not include the edge $\edge{x}{y}$, the unique path from $v_0$ to $y$
ends with this edge and is one longer than the path from $v_0$ to $x$.  In
either case, one vertex is at an odd distance from $v_0$ and the other is
at an even distance from $v_0$, so the two vertices are
differently-colored.}


\ppart Suppose that $G$ is a \emph{connected} graph with no odd cycle, and
let $T$ be a spanning tree of $G$.  Show that a 2-coloring of $T$ also
defines a 2-coloring of $G$.

\solution{Vertices connected by an edge in $T$ have different colors in a
2-coloring of $T$, so we need only show that an edge $\edge{x}{y}$ {\em
not} in the tree must connect different-colored vertices.

Let $z$ be the first common vertex on the path in $T$ from $x$ to the root
$v_0$ and the path in $T$ from $y$ to $v_0$.  The path from $x$ to $z$,
followed by the path from $z$ to $y$, followed by the edge $\edge{y}{x}$
form a cycle which, by hypothesis, must be of even length.  Since the
length of the cycle is one plus the sum of the lengths of the two paths,
one of the paths must have odd length and the other even length.  This
implies that of the paths from $x$ to $v_0$ and from $y$ to $v_0$, one has
even length and the other odd length.  From the way we 2-colored $T$, it
follows that $x$ and $y$ must be colored differently.}

\ppart Now just assume the right side, namely $G$ is a graph with no odd
cycle, but is not necessarily connected.  Describe a way of obtaining a
2-coloring of $G$.

\solution{Color each connected component of $G$ with 2 colors one at a
time.}

\eparts

\end{problem}


\begin{problem}[10 points]
A \emph{perfect match} in an arbitrary (not necessarily bipartite) graph
is a subset of edges such that every vertex is an endpoint of exactly one
edge in the subset.  Informally, a perfect match corresponds to pairing up
each person with a unique compatible \emph{buddy} -- who might be of the
same sex -- as opposed to the bipartite case in Hall's Theorem, where
matches must be to a person of the opposite sex.

Suppose a graph has two perfect matchings such that every \emph{edge} is
in at least one of the matchings.  Prove that the graph is bipartite.

\emph{Hint:} Observe that two edges incident on the same vertex cannot be
in the same matching, and use the previous problem.

\solution{Let $G$ be the graph, and consider any cycle in $G$.  If an
edge, $l$, on the cycle is in one perfect matching, then neither of its
end vertices can be matched with any other vertex under that matching.  So
the edges on either side of $l$ in the cycle must belong to the other
matching.  That means that the edges around the cycle alternate which
matching they are in.  This implies the length of the cycle must be even,
so by Theorem~\ref{bip}, $G$ is bipartite.}

\iffalse
\solution{NICKH VERSION:

Let $G$ be the graph, and consider any cycle $C$ in $G$. 

We first show that each edge in the cycle $C$ belongs to exactly one of
the matchings.  To do this, we prove the contrapositive: any edge that is
in both of the matchings is not in the cycle.  Let $e=\edge{u}{v}$ be an
edge of the graph that is contained in both of the matchings.  Suppose
that there is another edge $e'=\edge{u}{w}$ incident with $u$.  The vertex
$u$ can be incident with at most one edge from each matching, and edge $e$
is in both matchings, so this implies that $e'$ can be in neither of the
matchings.  But our original assumption is that every edge of the graph is
in at least one of the matchings, so edge $e'$ cannot exist.  That is,
there are no other edges incident with $u$.  Thus the edge $e$ cannot
belong to our cycle $C$ since every vertex on a cycle must have degree at
least $2$.

Now let $e$ be an edge on cycle $C$.  By our previous remarks, $e$ belongs
to exactly one of the matchings.  So neither of its end vertices can be
matched with any other vertex under that matching.  So the edges on either
side of $e$ on the cycle $C$ must belong to the other matching.  That
means that the edges around the cycle alternate which matching they are
in.  This implies the length of the cycle $C$ must be even, so by
Theorem~\ref{bip}, $G$ is bipartite.}\fi


\end{problem}

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

% part(c) from: s02-ps4-2.tex

\begin{problem}[20 points]

Suppose a connected, planar graph has $v$ vertices, $e$ edges, and $f$
faces.

\bparts

\ppart\label{e3v6} Show that if $v > 2$, then
\[
e \leq 3v-6.
\]

\emph{Hint:} Every edge appears exactly twice on the borders of the faces
of the graph\footnote{If an edge touches only one face, then it is
considered to have two appearances on the border of the face (one ``going''
and the other ``coming'').  For example, if the whole graph consists of a
single path with $e$ edges, then it only has one face; the border of
this face has $2e$ appearances of edges.}, and the border of every face has
at least three appearances of edges.  Assume these facts and use Euler's
formula.


\solution{
\begin{align}
v-e+f &= 2, & \text{Euler}\label{vef}\\
2e & \geq 3f, & \text{by the hint}\label{e3f}\\
v-e+\frac{2e}{3} & \geq 2, & \text{by~\eqref{vef},~\eqref{e3f}}\label{23}\\
3v-6 & \geq e. & \text{by algebra from~\eqref{23}}
\end{align}
}

\ppart\label{d5} Show that the graph has a node of degree at most $5$.

\solution{Suppose that every vertex has degree at least $6$.  Then
\[
2e = \sum_{n \in V}\text{deg}(n) \geq \sum_{n \in V}6 = 6v >6v-12,
\]
contradicting part~(\ref{e3v6}).
}

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

\solution{The proof is by strong induction on the number, $v$, of vertices.
The induction hypothesis is
\[
P(v): \text{A planar graph of $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 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}


\iffalse  INITIALLY POSTED VERSION.
 
\begin{problem}[20 points]

Suppose a planar graph has $v$ vertices, $e$ edges, and $f$ faces.

\bparts

\ppart\label{e3v6} Show that
\[
e \leq 3v-6.
\]

\emph{Hint:} Every edge borders exactly two faces, and every face of a
planar graph must have at least three edges.  Use Euler's formula.

\solution{
\begin{align}
v-e+f &= 2, & \text{Euler}\label{vef}\\
2e & \geq 3f, & \text{by the hint}\label{e3f}\\
v-e+\frac{2e}{3} & \geq 2, & \text{by~\eqref{vef},~\eqref{e3f}}\label{23}\\
3v-6 & \geq e. & \text{by algebra from~\eqref{23}}
\end{align}
}

\ppart\label{d5} Show that the graph has a node of degree at most $5$.

\solution{Suppose that every vertex has degree at least $6$.  Then
\[
2e = \sum_{n \in V}\text{deg}(n) \geq \sum_{n \in V}6 = 6v >6v-12,
\]
contradicting part~(\ref{e3v6}).
}


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

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

{\bf Base case ($v = 1$):} $P(1)$ is true because a single vertex can be
colored with $1$ color.

{\bf Inductive step:} 
Assume $P(v)$ is true in order to show that $P(v+1)$ is true.

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


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

\end{document}
