
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 1
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{30} \textbf{Hamiltonian Circuits}
\begin{problemparts}


In this problem you will prove that for any positive integer $n$, any 
$2n$ by $2n$ grid graph has a Hamiltonian circuit.  

An $n$ by $m$ grid graph is made up of vertices described as pairs of 
integers $(x, y)$ where $0 \leq x < n$ and $0 \leq y < m$.  There is
an edge between two vertices if their $x$-coordinates differ by 1 or
if their $y$-coordinates differ by 1 but NOT if both differ by 1.

So, for example, there would be edges between the vertices $(2,3)$ and
$(3,3)$ but not between $(2,3)$ and $(3,2)$.

\problempart {\bf (4 points)}  Draw a 4 by 4 grid graph.  Label vertices
$(1, 3)$, $(2, 2)$, and $(2, 3)$.  

\solution{
\bigskip
{\bf Solution: }
\begin{center}
{\includegraphics[height=3.0in]{figures/quiz1p6a}}
\end{center}
}

\smallspace

\problempart {\bf (10 points)} Prove that the chromatic number of any
$m$ by $n$ grid graph is 2 (for $m, n > 1$).

\solution{
\bigskip {\bf Solution: } To prove that the chromatic number of an $m$
by $n$ grid graph is 2, we must show that it cannot be colored with 1
color, and that it can be colored with 2 colors.

Since $m,n > 1$, there is an edge from $(0,0)$ to $(0, 1)$, so the
graph cannot be 1-colored, since these two vertices must have different
colors.

To color the graph with 2 colors, simply let all vertices $(x,y)$
where $x + y$ is even be colored white, and let all vertices where
$x+y$ is odd be colored black.  Since nodes are only adjacent to other
nodes where $x$ or $y$ differs by 1, but not both, we see that every
node adjacent to $(x,y)$ is such that the sum of that nodes
coordinates is either $x+y-1$ or $x+y+1$.  Thus, any white node is
adjacent only to black nodes, and vice versa.  

}

\nextproblem

\problempart {\bf (16 points)} Prove by induction that any $2n$ by
$2n$ grid graph has a Hamiltonian circuit for $n \geq 1$.  (Other
proof methods will not get credit) Note: this question does not have
anything to do with the question in part (b).

\solution{
\bigskip {\bf Solution: }
Let $P(n)$ be the statement ``Any $2n$ by $2n$ grid graph has
a Hamiltonian circuit.''

$P(1)$:  Any 2 by 2 grid graph is just a square.  The square itself
is a circuit, and it touches all the nodes.  Thus, it is a Hamiltonian
circuit.

Assume $P(n)$.  Let $G$ be a $2(n+1)$ by $2(n+1)$ grid graph.  We
construct a Hamiltonian circuit for $G$ as follows.  First, let the
subgraph on all the vertices with $x < 2n$ and $y < 2n$ be called
$H$.  $H$ is a $2n$ by $2n$ grid graph, so it has a Hamiltonian circuit.

Start at vertex $(0, 2n+1)$ and continue straight to $(2n+1, 2n+1)$
and then down to $(2n+1, 0)$, then to $(2n, 0)$.  Now, since we know
there's a Hamiltonian circuit in $H$, pick one.  $H$ must include
the edge from $(2n-1, 0)$ to $(2n-1, 1)$ since in $H$, vertex $(2n-1, 0)$
has degree 2.  

Now we continue our path to vertex $(2n-1, 0)$ and through the circuit 
for $H$ in the direction of $(2n-2, 0)$.  After visiting all the nodes
in $H$, this will return us to $(2n-1, 1)$.  From there we continue to 
$(2n, 1)$ and up to $(2n, 2n)$ and back to $(0, 2n)$ and we close the
circuit by going back to $(0, 2n+1)$.  

Thus, $P(n+1)$.  By induction, if $n$ is an integer $\geq 1$ then
Any $2n$ by $2n$ grid graph has a Hamiltonian circuit.
}

\nextproblem

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 1
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{15} \textbf{Directed Graphs}

Recall that a {\em tournament graph} is a directed graph in which
between any two different nodes $a$ and $b$ there is an edge either
from $a$ to $b$ or from $b$ to $a$ but not both, and there are no
other edges in the graph.

For each of the following, answer true or false and give a brief
justification of your answer.

\begin{problemparts}

\problempart{\bf (5 points)} There is no tournament graph on 4 nodes with
an Euler circuit.

\solution{
\bigskip {\bf Solution: }
The claim is true.

In a tournament graph on 4 nodes, every node will have an odd number
(3) of edges, so the degree of every node is odd.  A directed graph
has an Euler circuit only when every node has equal in-degree and
out-degree.  However, if the total degree (in-degree plus out-degree)
is odd, the in-degree and out-degree cannot be equal.  Thus, there is
no Euler circuit.
}

\smallspace

\problempart{\bf (5 points)} There is no tournament graph on 5 nodes
with an Euler circuit.


\solution{
\bigskip {\bf Solution: }
The claim is false.

An example is the graph on five nodes $a, b, c, d, e$ where the
edges are $(a,b),\, (b,c),\, (c,d),$ $(d,e),\, (e,a),\, (a,c),\,(c,e),\,
(e,b),\, (b,d),\,(d,a).$  The edges in this order make an Euler circuit.  
}

\smallspace

\problempart{\bf (5 points)} There is no tournament graph on 225 nodes with
an Euler circuit.

\solution{
\bigskip {\bf Solution: }
The claim is false.

The complete graph on 225 nodes has an Euler circuit, since every node
has degree 224, which is even.  Since an Euler circuit contains every
edge, all we have to do to construct a 225-node tournament graph with
an Euler circuit is take the Euler circuit on $K_{225}$ and choose a
direction, then include every edge in our 225-node tournament graph in
the direction it appears in the Euler circuit.  This will be a
tournament graph, since every two nodes are connected and every edge
is directed.

}

\nextproblem

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (12 points)} The vertices of a directed graph can be
partitioned into {\em strongly-connected components}.  Two vertices
$u$ and $v$ belong to the same strongly connected component if there
is a path from $u$ to $v$ and a path from $v$ to $u$.  A strongly
connected component may consist of a single vertex.

Theory Pig has noticed a strange phenomenon.  He starts with a
directed graph and partitions the vertices into strongly-connected
components.  He then removes all edges that connect two vertices in
the same strongly-connected component.  The resulting graph always
seems to be acyclic.

An example is worked out in the figure below.  The original directed
graph is shown on the left.  The vertices $a$, $b$, and $c$ form one
strongly-connected component.  The single vertex $d$ forms a second
strongly-connected component.  Theory Pig removes the edges $a
\rightarrow b$, $b \rightarrow c$, and $c \rightarrow a$, since these
edges connect vertices in the same strongly-connected component.  The
resulting graph is shown on the right.  Note that this graph is
acyclic.

\bigskip

\centerline{\resizebox{!}{1.5in}{\includegraphics{scc.eps}}}

\bigskip

Use proof by contradiction to show that for every directed graph,
application of Theory Pig's procedure gives a directed acyclic graph.

\solution{
\begin{proof}
Let $G = (V,E)$ be an arbitrary directed graph.  Let $G' = (V,E')$ be
the directed graph that remains after we remove all edges that connect
two vertices in the same strongly-connected component.

The proof is by contradiction.  Suppose that $G'$ is not acyclic.
Then let $u$ and $v$ be consecutive nodes in a directed cycle.  There
is a path from $u$ to $v$ consisting of a single edge.  There also is
a path from $v$ to $u$, because the nodes are in a cycle.  Since every
edge in $G'$ is also in $G$, these same two paths exist in the
original graph $G$.  Therefore, $u$ and $v$ are in the same
strongly-connected component of $G$.  But then the edge from $u$ to
$v$ should have been removed during the construction of $G'$.  Since
the the edge was not removed, we have a contradiction.  Therefore,
$G'$ is acyclic.
\end{proof}
}