\documentstyle[12pt,twoside,xypic,amssymb]{article}
\input{macros-course}

\let\b\bullet

\begin{document}

\pset{5}{March 14, 1996}{March 22, 1996}

{\bf Reading for this assignment:}   Rosen course text, \S 7.2--5, 7.8, 1.8

{\bf Reading for next week's lectures:} \S 5.1--5.3

\bigskip

\begin{problems}

% graph non-isomorphism
\problem
In last tutorial you have seen that the two graphs
\[
\diagram
 & \b \rrline\xline'[1,0][2,0] & & \b \ddline\\
 \b \urline\rrline\ddline & & \b \urline\ddline\\
 & \b \xline'[0,1][0,2] & & \b\\
 \b \rrline\urline & & \b \urline
\enddiagram
\quad\quad
\diagram
 & \b \rrline\xline'[1,0][2,0] & & \b \xline'[3,-1]\\
 \b \urline\rrline\ddline & & \b \urline\drline\\
 & \b \rrline & & \b\\
 \b \rrline\urline & & \b \urline
\enddiagram
\]
are not isomorphic.
Both graphs have eight vertices and are 
connected and 
3-regular (a graph is 3-regular iff
each vertex has degree 3).
 
\bparts 
\ppart
Give another 3-regular connected simple graph with eight vertices
that is not isomorphic to 
either of the above graphs,
and prove the non-isomorphism.
\ppart (EXTRA credit) Find one more non-isomorphic 
3-regular connected simple graph with 8 vertices.
\ppart (EXTRA EXTRA credit) Find them all and prove it.
\eparts
 
{\bf Note}: All graphs must be connected and simple, i.e.,
no loops or
multiple edges between nodes.

%graph isomorphism
\problem
The simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ 
are {\em edge-isomorphic} if there is a one-to-one
and onto function $g$ from $E_1$ to $E_2$ 
with the property that any two edges $d$ and $e$ in $E_1$
share an endpoint in $G_1$ if and only if 
their images $g(d)$ and $g(e)$ share an endpoint 
in $G_2$.
Such a function is called an {\em edge-isomorphism}.

\bparts
\ppart Show that if two simple graphs are isomorphic
 then they are also edge-isomorphic.
\ppart Give a easy example of two simple graphs 
 that are edge-isomorphic but not isomorphic.
\ppart (EXTRA credit) Exept for a few peculiar graphs
 the following ``theorem'' is true:
 \begin{quote}
  Theorem: Two simple graphs are edge-isomorphic if and only
  if they are isomorphic.
 \end{quote}
 Characterize the ``peculiar graphs'' for which 
 the above theorem does not hold and 
 prove that the theorem is true for any non-peculiar 
 graph.
\eparts

% graph connectivity
\problem
There is a network of $k$ highways among
$n$ cities.
(A highway is defined to be a road between
two cities that does not go through any intermediate
cities.)
Show that if $k>(n-1)(n-2)/2$, 
then one can always travel between any two cities
through connecting highways.

% eulerian circuits
\problem
In this problem you have to find 
a circular arrangement of nine $a$'s,
nine $b$'s and nine $c$'s such that each of the
27 words of length 3 from the alphabet $\{a,b,c\}$
appear exactly once.

Consider a directed graph $G$ 
where the vertices are all possible words
of length two from the alphabet $\{a,b,c\}$,
and there is an edge from vertex $xy$ to vertex 
$wz$ if and only if $y=w$.

\bparts 
\ppart 
 Show how the problem of finding the circular 
 arrangement of letters
 can be formulated as findind
 a particular kind of path in the graph $G$.
\ppart
 Find the path and give the a circular arrangement of 
 $a$'s, $b$'s and $c$'s with the desired property.
\eparts

% Graph problems (from CLR)
\problem 
Show that $G$ is bipartite if and only if it has no cycles of odd length.

% Coloring
\problem
\bparts
\ppart Let $d$ be the maximum degree of any vertex in a graph $G$.  Show
that $G$ can be colored with $d+1$ colors (You may assume that 
the graph is finite).

\ppart
Let $f:\nats\to\nats$ and $G_0, G_{1}, \ldots$ be a sequence of undirected
graphs such that the number of edges in $G_{n}$ is $O(f(n))$.  Show that
$G_{n}$ can be colored with $O(\sqrt{f(n)})$ colors.  \eparts

\problem Prove or disprove where $f$ and $g$ are non-decreasing functions
from $\nats$ to $\nats$:
\bparts
\ppart If $f = O(g)$ and $g \not = O(f)$, then $f = o(g)$.
\ppart Either $f = O(g)$ or $g = O(f)$.
\eparts

\end{problems}
\end{document}


