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

\begin{document}
\psol{3}{February 24, 1998}

{\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$.

For $C_n$, we label the vertices so that the cycle goes 
$v_1,v_2,\ldots,v_n,v_1$.  Then the matrix has 1's on the diagonals just 
above and below the main diagonal and in positions $(1,n)$ and $(n,1)$,
and 0's everywhere else. 

\begin{gather*}
\begin{pmatrix}
0 & 1 & 0 & 0 &\ldots & 0 & 1\\
1 & 0 & 1 & 0 &\ldots & 0 & 0\\
0 & 1 & 0 & 1 &\ldots & 0 & 0\\
0 & 0 & 1 & 0 &\ldots & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & 0 &\ldots & 0 & 1\\
1 & 0 & 0 & 0 &\ldots & 1 & 0\\
\end{pmatrix}
\end{gather*}


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


Vertices of $K_{n,m}$ are partitioned into a group of $n$
vertices and a group of $m$ vertices. In this graph, an edge is
present between two vertices if and only if the two vertices are from 
different groups.
Therefore, the adjacency matrix of $K_{n,m}$ consists of
four sub-matrices. The top left and the bottom right matrices
consist of 0's with size $n * n$ and $m * m$ respectively.
The top right and the bottom left matrices consist of 1's
with size of $n * m$ and $m * n$ respectively.
 
 
\begin{gather*}
\begin{pmatrix}
0 & \ldots & 0 & 1 & \ldots & 1\\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
0 & \ldots & 0 & 1 & \ldots & 1\\
1 & \ldots & 1 & 0 & \ldots & 0\\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
1 & \ldots & 1 & 0 & \ldots & 0\\
\end{pmatrix}
\end{gather*}


\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.

The base case is,
 
\begin{gather*}
Q_1 =  
\begin{pmatrix}
0 & 1\\
1 & 0\\
\end{pmatrix}
\end{gather*}
 
Then, every $Q_{n+1}$ ($n \geq 1$) is defined inductively. 
The size of $Q_{n+1}$ is
$2^{n+1} * 2^{n+1}$ and the left top and right bottom quarter of the matrix
are $Q_n$, which correspond to the two subgraphs $Q_n$ in $Q_{n+1}$. The right top and left bottom quarter of the matrix
are identity matrices of size $2^n*2^n$($I_{2^n}$), which correspond to the 
edges connecting vertices $k$ and $k+2^n$ for $0\leq k<2^n$, which differ by the most 
significant bit only.

\begin{gather*}
Q_{n+1} =
\begin{pmatrix}
Q_n & I_{2^n} \\
I_{2^n} & Q_n \\
\end{pmatrix}
\end{gather*}



\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.\\

$C_9$ and $C_{20}$ can be colored with $3$ and $2$ colors respectively.
To see this, let's number the vertices of $C_n$ from $1$ to $n$ 
by going around the cycle. If $n$ is even,
we can assign every even vertex with one color and every odd vertex
with the other color. Since  $n$ is even and $1$ is odd, vertex $n$ and vertex 1
 will have 
different colors. Therefore, we only need $2$ colors.


If $n$ is odd, we need one more color, since both $1$ and $n$ are odd and
they cannot have the same color. Therefore, we will assign
all the even vertices with one color, all the odd vertices except $n$ with
a second color and $n$ with a third color. Therefore, we need $3$
colors. Since 9 is odd and 20 is even, $C_9$ and $C_{20}$ need $3$ colors 
and $2$ colors respectively.\\

Wheels can be colored with very few colors as well. A wheel is indeed a cycle with 
one extra vertex
adjacent to all the vertices in the cycle. 
Therefore we only need one more
color for the extra vertex. Since we need $2$ colors for an even
cycle and $3$ colors for an odd cycle, an even wheel needs
$3$ colors and an odd wheel needs $4$ colors. Therefore, we can
color $W_{13}$ with $4$ colors.\\

The number of colors for $K_{311,222}$ seems to depend on $311$ and $222$.
However, only two colors are needed. Color the set of the $311$ vertices with
one color and the set of the $222$ vertices with a second color. Since no edge
connects two vertices in the same group in a bipartite graph, no two adjacent vertices have the same color. 
In fact, we can extend this result to any $m$ and $n$ in $K_{m,n}$. Therefore,
any complete bipartite graph is 2-colorable.


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

\bparts 

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

The two graphs are isomorphic. Informally, we can see by breaking the graph
into a $K_4$ and a extra vertex with two edges connected to $K_4$.
Therefore, a function $f$ that maps $u_1$ $\rightarrow$ $v_1$, $u_2$ $\rightarrow$ $v_3$,
$u_3$ $\rightarrow$ $v_2$, $u_4$ $\rightarrow$ $v_5$ and $u_5$ $\rightarrow$ $v_4$, is an isomporphism 
between the two graphs. We can verify this since there is an edge between
$u_i$ and $u_j$ iff there is an edge between $f(u_i)$ and $f(u_j)$ for
all $1 \leq i, j \leq 5$. \\


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

The two graphs are not isomorphic. Both graphs have two vertices of 
degree 3: $u_2$ and $u_3$ in the first graph and $v_2$ and $v_4$ 
in the second graph.  
Since $u_2$ and $u_3$ are adjacent while $v_2$ and $v_4$ are not,
the two graphs are not 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.

It is invariant under isomorphism. There must be an one-to-one and onto
mapping between the vertices of two isomorphic graphs. Therefore, the number 
of vertices in the two graphs must be
the same. If one graph has even number of vertices, then the other must
have even number of vertices.\\

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

It is not invariant under isomorphism. We do not really care what the 
vertices are. Vertices can be any kind of mathematical objects. 
All we are interested is that whether there
exists a one-to-one and onto function $f$ mapping from vertices of one graph 
to vertices of another with the property that $a$ and $b$ are adjacent in the
first graph if and only if $f(a)$ and $f(b)$ are adjacent in the  second
graph, for all $a$ and $b$ in the first graph. \\

So, for example, let $G_1$ be a graph with a single vertex, 1, and $G_2$ be
a graph with a single vertex, 2. Obviously the two graphs are isomorphic, but
$G_2$ does not have vertices which are even integers.\\
\ppart
$G$ has a vertex of degree 3.

It is invariant under isomorphism.  

Let $G_1, G_2$ be simple graphs and $f:V_1\to V_2$ be an isomorphism
between them.  Suppose $v\in V_1$ has degree 3; we want to show that there
is a vertex of degree 3 in $V_2$.  In fact, we'll show that $f(v)$ has
degree 3.
 
Since $v$ has degree 3, there are exactly 3 vertices adjacent to $v$; say
these are $v_1,v_2,v_3$.  Since $f$ is a bijection, $f(v_1),f(v_2)$ and
$f(v_3)$ are all distinct.  Since there is an edge between $v$ and $v_i$
in $G_1$, the definition of isomrphism implies that there is an edge
between $f(v)$ and $f(v_i)$ for $i=1,2,3$, so the degree of $f(v)$ is at
least 3.
 
We now prove by contradiction that the degree of $f(v)$ is at most 3.
Suppose $f(v)$ had degree $>3$.  This means there is a vertex $w \in V_2$
which is not equal to $f(v_1), f(v_2),$ or $f(v_3)$, but is also adjacent
to $f(v)$.  Since, $f$ is a bijection, there is a vertex $v_4 \in V_1$
such that $f(v_4) = w$ and $v_4 \neq v_i$ for $i=1,2,3$.  Since $w=f(v_4)$
is adjacent to $f(v)$, the definition of isomorphism implies that $v_4$ is
adjacent to $v$, contradicting the fact the $v_1,v_2,v_3$ were exactly the
vertices adjacent to $v$.\\


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

It is invariant under isomorphism.

Prove by contradiction:  Let a graph $G_1$ has exactly one vertex of 
degree $3$ while another graph $G_2$ does not have exactly one vertex of 
degree 3. Suppose the two graphs are isomorphic. If $G_2$ does not have 
a vertex of degree 3, then from part (c), there is a contradiction.
If $G_2$ has more than one vertices of degree 3, then there must
be at least one vertex in $G_2$ of degree 3 which is mapped to 
a vertex of degree $\neq 3$ in $G_1$. Since two vertices of different degrees
are mapped from $G_1$ to $G_2$, using the same argument from part (c),
it reaches a contradiction. Therefore, if $G_1$ has exactly one 
vertex of degree 3 , then $G_2$ must also have exactly one 
vertex of degree 3.\\


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

It is not invariant under isomorphism. 

Let $G_1$ be a graph with three vertices, $1$, $2$ and $\{1,2\}$. There is
only one edge from vertex $1$ to vertex $2$. Therefore, $\{1,2\}$ is a vertex
of $G_1$ and also an edge of $G_1$. 

On the other hand, let $G_2$ be a graph with three vertices,
$7$, $12.1$ and an ordered pair $(1, -3)$(note: these are somewhat
tasteless, but legitimate things to use as vertices). There is only 
one edge from vertex $7$ to vertex $12.1$.
Obviously two graphs are isomorphic; however, $G_2$ does not have 
a vertex which is an edge at the same time. 
Therefore, it is not invariant under isomorphism.


\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.

We use the induction on $n$.
Let $P(n)$::= $W_n$ has inherited degree 3.

{\bf Base Case:} $W_3$ has four vertices of degree 3 and it has 
inherited degree 3 by definition (i).

{\bf Inductive Step:} Assume $P(n)$ is true, we need to prove $P(n+1)$.
$W_{n+1}$ has $n+1$ vertices of degree $3$ and $1$ vertex of degree $n+1$.
The graph $G$ obtained by removing a vertex of degree $3$ has $n-2$ vertices
of degree $3$, $2$ vertices of degree $2$ and $1$ vertex of degree $n$.
We can also obtain $G$ by removing a edge between two vertices of degree $3$
in $W_n$. Since $W_n$ has inherited degree 3 by inductive hypothesis and removing an edge
does not increase the degree of vertices, $G$ has inherited degree 3.
Then, by definition (ii), $W_{n+1}$ has inherited degree 3.

Therefore, we prove that $W_n$ has inherited degree 3 for $\forall n \geq 3$. \\

%Since this single vertex graph has
%{\em inherited degree 3}, the graph right before (two verticies)
% has {\em inherited degree 3}. Therefore, by building back the
%$W_n$ up, we conclude that it has {\em inherited degree 3}.\\

%So, the point is that if you can keep removing a vertex with
%degree $\leq d$ until every vertex in the subgraph has 
%degree $\leq d$ then the original graph before the vertices are removed
%has {\em inherited degree d}.\\

\ppart
Prove that a tree has inherited degree 1.

We use the definition of tree in
Rosen, 8.1: a tree is a connected undirected graph with no simple
circuits.  Also, we only consider trees with a finite number of
vertices.

We need to prove two facts here. First we have to prove that every tree 
with at least two vertices has a leaf (a leaf is a vertex of degree one). 
Then we need to show that the subgraph
constructed by removing one leaf is still a tree.\\

First, let's prove that every tree with at least two vertices has a leaf.
Let $T$ be a tree, and let $P$ be a longest simple path in $T$. 
In a finite graph, a path of length greater than or equal to 
the the number of vertices must visit some vertex more than once.  
So a \emph{simple} path must be shorter than the
number of vertices.  Therefore in any finite graph there must be longest
simple path.  (We're using the Well-ordering principle here, taking the
least element of $\set{\card{V}-k : k \mbox{ is the length of a simple
path}}$.)

Suppose $P = (v_1, v_2 \ldots, v_k)$, we claim that $v_1$ is a leaf.  
For if not, there will be an edge $\{v,v_1\}$ in $T$ where $v \neq v_2$. 
The vertex $v$ cannot occur in $P$, for otherwise this creates a cycle, which 
contradicts that the graph is a tree.
Therefore, $P'=(v, v_1, v_2 \ldots, v_k)$ is also a simple path in the tree 
and $P'$ is longer than $P$. But this is a contradiction  
because we have assumed that  $P$ is the longest path in the tree. 
As a result, a tree with 2 or more vertices has to have a leaf. 

Second, let's prove that the subgraph constructed by removing one leaf
is still a tree. 
From the definition given in the
book (cf. Rosen p531), a tree is a connected undirected graph with no simple
circuits. Removing a leaf from a tree does not create any 
circuit. Also, since the leaf has degree 1, it is not connecting any 
other two vertices in the tree. Therefore, after removing the leaf, no vertices 
get disconnected. In other words, the subgraph is still connected.
%removed is adjacent to only one vertex and
%that leaf can only be connected to the graph via the adjacent vertex, 
%the subgraph is still connected. 
Since the subgraph is a connected undirected 
graph with no simple circuits, it is also a tree.\\

Since every tree has a leaf(vertex with degree 1) and the subgraph
is still a tree after removing a leaf, we can apply the same
method in the previous part to show that a tree has inherited degree 1.\\

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

We use induction on the number of
vertices in a graph to prove this fact. 

Let $P(n)$::= ``$\forall d>0$, any $n$-vertex graphs with inherited degree $d$ is $(d+1)$ colorable.''  

{\bf Base Case}: $n=1$. There is only one 1-vertex graph. And it is obviously
$(d+1)$ colorable ($\forall d>0$).

{\bf Inductive Step:} Assume that $P(n)$ is true, we need to 
prove $P(n+1)$ is true. Given any $(n+1)$-vertex graph $G$ with inherited degree $d$ for any $d>0$, 
there are 2 possible cases: 
\begin{enumerate}
\item All vertices in $G$ has degree $\leq d$. Then it is $(d+1)$-colorable,
as proved in the lecture.
\item There is a vertex $v\in G$ of degree $\leq d$, and the subgraph
$G'$ obtained by removing $v$ has inherited degree $d$. Since $G'$
has $n$ nodes and has inherited degree $d$, by inductive hypothesis $G'$ is 
$(d+1)$ colorable. Now consider the vertex $v$. Since it has degree $\leq d$,
it has at most $d$ neighbors and therefore it can be colored with the $(d+1)^{st}$ color 
which is different from all of its neighbors.
\end{enumerate}

Therefore, by induction, every graph with inherited degree $d$ is $(d+1)$-colorable.\\

%following method to color a graph with inherited degree $d$.
%Let's remove a vertex with degree $\leq d$ until we have every 
%vertices have the degrees $\leq d$.
%Then, we can easily show that every graph with all the vertices with
%degree $\leq d$ can be colored with $d+1$ colors by induction.\\
%The base case is a graph with one vertex. It is true since only one
%color is needed. For induction step, 
%let's consider a graph $G_{n+1}$ with $n+1$ vertices of degree $\leq d$.
%Let's remove a vertex from $G$ and let say the remaining graph is $G_n$.
%Since we are not increasing the degree of any vertex by removing a vertex,
%all the vertices in $G_n$ have the degrees $\leq d$. So, by inductive
%hypothesis, we can color $G_n$ with $d+1$ colors. Now, let's put the
%vertex we took out back to the graph. Since that vertex can be adjacent
%to at most $d$ other vertices, we can color it with one remaining color.
%Therefore, we proved that every graph with all the vertices with degree
%$\leq d$ can be colored with $d+1$.\\
%
%Then,  we can keep adding a vertex with degree $\leq d$ to build back 
%the original graph with inherited degree $d$, since we can always 
%assign a (n+1)th color to the added vertex. Therefore,
%Any graph with inherited degree $d$ 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.

An example would be $K_{n+1, n+1}$. Every vertex in $K_{n+1, n+1}$ has
degree $n+1$. Therefore, it does not have inherited degree $n$.
However, it is $2$-colorable since every complete bipartite graph is $2$-colorable.


\eparts

\end{problems}

\end{document}
