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

\begin{document}
\pset{3}{February 18, 1998}{Tuesday, February 24}

{\bf Reading assignment: Rosen sections 7.1--7.4, 7.8, 8.1--2}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1 (Rosen 7.3-32)
\problem [10 pts]

The graphs  $C_n$, $Q_n$, $W_n$, and $K_{n,m}$ are defined in Rosen 7.2.

\bparts

\ppart Describe the adjacency matrix for $C_n$.

\ppart Describe the adjacency matrix for $K_{n,m}$.

\ppart Give a simple recursive definition of the adjacency matrix for the
graph $Q_{n+1}$.  \hint Use the matrix of $Q_n$ and suitable identity
matrices.

\eparts


%Problem 2

\problem [10 pts]

Find the minimum number of colors to color (with no two adjacent
vertices given the same color, {\em cf.} Rosen, 7.8) each of $C_9, C_{20},
W_{13}$ and $K_{311,222}$.  Explain briefly.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem [20 pts]

\bparts 

\ppart Prove or disprove that the pair of graphs given in Rosen 7.3,
Exer.\ 38 are isomorphic.


\ppart Prove or disprove that the pair of graphs given in Rosen 7.3,
Exer.\ 42 are isomorphic.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem [30 pts]

Some properties of a simple graph, $G$, are described below.  For each
property, carefully prove or give a counterexample to the claim that the
property is {\em invariant under isomorphism} ({\em cf.} Rosen, p.455).

\bparts
\ppart
$G$ has an even number of vertices.

\ppart
None of the vertices of $G$ is an even integer.

\ppart
$G$ has a vertex of degree 3.

\ppart
$G$ has exactly one vertex of degree 3.

\ppart
One of the vertices of $G$ is also an edge of $G$.

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem [30 pts]

{\bf Definition}:
A simple graph, $G$, has {\em inherited degree $d \geq 0$ }
if and only if\\
(i) every vertex of $G$ has degree $\leq d$, or\\
(ii) there is a vertex $v \in G$ of degree $\leq d$, and the subgraph of
$G$ obtained by removing $v$ has inherited degree $\leq d$.

\bparts
\ppart
Prove that $W_n$ has inherited degree 3.

\ppart
Prove that a tree has inherited degree 1.

\ppart
Prove that if a graph has inherited degree $d$, then it is
$(d+1)$-colorable.

\ppart
For every $n>0$, describe an example of a graph which does not have
inherited degree n, but which is 2-colorable.

\eparts

\end{problems}

\end{document}
