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

\begin{document}
\psol{3}{September 26, 1997}


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%Problem 1
\problem{\bf [7 points]}

Let $G$ be a bipartite graph with $n$ vertices and $m$ edges.
Show that $m \leq n^2 /4$

\bigskip

Suppose the parts are of sizes $k$ and $n-k$.  Then the maximum number of
edges the graph may have is $k(n-k)$.  The maximum of the function 
$f(k) = k(n-k)$ is achieved at $k = n/2$, and has the value 
$f(n/2) = n^2 / 4$.  Therefore, $m \leq  n^2 / 4$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2 (Rosen 7.3-32)
\problem{\bf [7 points]}

Find the adjacency matrix for the 
graphs $K_n,C_n$ and $W_n$ defined in 7.3 of Rosen.

\bigskip

In $K_n$ every vertex is connected to every other vertex, so the 
adjacency matrix has zeros in the diagonal and 1's everywhere else.

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

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 & \ldots & 0 & 1\\
1 & 0 & 1 & \ldots & 0 & 0\\
0 & 1 & 0 & \ldots & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & \ldots & 0 & 1\\
1 & 0 & 0 & \ldots & 1 & 0\\
\end{pmatrix}
\end{gather*}

The adjacency matrix of $W_n$ is similar to the adjacency matrix for
$C_n$, except that we add one more row and column 
for the vertex in the middle of the
wheel (which is connected to everything but itself).


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem{\bf [15 points]}

Let $G=(V,E)$ be an undirected graph, and let there be a weight $r(v)$
associated with each vertex $v$.  Suppose $r$
satisfies the property that for each $v\in V$, the value $r(v)$ is the
average of the values of $v$'s neighbors.  Prove that if the graph is
connected, then $r(u)=r(v)$ for all $u,v\in V$.

\begin{proof} 

The proof is by contradiction.

Suppose that not all the vertices in the graph have the same value.
Let $s = \min_{u \in V} (u)$.
Note that this value may not be unique in 
the graph. Choose a vertex $v$ such that $r(v) = s$ and $v$ has a neighbor
$u$ with $r(u) > s$. We will prove that such a vertex exists.


Pick a vertex $x_0$ of value $s$ and a
vertex $w$ with $r(w) > s$ (such a vertex exists because of the assumption that
$r$ is not constant). Since $G$ is connected, there exists a path
$(x_0,x_1,x_2, \ldots, x_{n-1},x_n)$ with $x_n = w$.
Let $i$ be the first number from $0$ to $n-1$ such that $r(x_i) < r(x_{i+1})$.
Then the vertex $x_i$ is a vertex with value $s$ that has a neighbor of greater
value. Set $v=x_i$ and $u = x_{i+1}$.

Now, $r(u) > r(v)$ 
implies that the average of the values of the neighbors of $v$ must be
greater than $s$. 
Since $r(v)=s$ is supposed to be equal to this average we obtain a 
contradiction.
We conclude that $r$ has to be constant.

\end{proof}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem{\bf [7 points]}

Prove that in any undirected graph, the sum of the squares of
the vertex degrees is even, or provide a counterexample.

\bigskip

The assertion is true. 

{\em Proof 1}

Let $V_e$ be the set of even degree vertices and $V_o$ the set of odd degree
vertices of the graph.
From class we know that there is an even number of odd degree vertices.
So can write

\begin{equation}\label{eq3}
\sum_{v \in V} deg(v)^2 = 
\sum_{v \in V_e} deg(v)^2 + \sum_{v \in V_o} deg(v)^2
\end{equation}

If $v \in V_e$ then $deg(v)$ is even, hence $deg(v)^2$ is also even.  
Therefore, the first term in the right hand side of (\ref{eq3}) is even.
Similarly if $v \in V_o$, then $deg(v)^2$ is odd.  The second term in the
right hand side is a sum of odd numbers with an even number of terms.   
Therefore it is also even.
We conclude that $\sum_{v \in V} deg(v)^2$ is even

{\em Proof 2}

Let $E$ be the set of edges of the graph and
$V = \{ v_1, \ldots , v_n \}$ be the set of vertices of the graph.

\begin{equation}\label{eq1}
(\sum_{i=1}^n deg(v_i))^2 = \sum_{i=1}^n deg(v_i)^2 +
2 \sum_{i \neq j} deg(v_i) deg(v_j)
\end{equation}

The left hand side of (\ref{eq1}) is even because
$ \sum_{i=1}^n deg(v_i) = 2|E|$ and the second part of the right hand side
is obviously even.  Therefore $\sum_{i=1}^n deg(v_i)^2$ is even.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5 
\problem {\bf [7 points]}

Prove that any tree with a degree $k$ vertex has at least $k$
leaves.  

\bigskip

First we prove the following lemma

{\bf Lemma:}
A connected subgraph of a tree is itself a tree.

\begin{proof}
A tree $T$ is a connected graph with unique paths between any two vertices.
Let $H$ be a connected subgraph of $T$.  Since $H$ is connected there is
at least one path between any two vertices in $H$.
If there are more than one paths connecting two vertices of $H$, then there
are more than one paths connecting two vertices of $G$ which is a contradiction.
\end{proof}

Now we prove the statement 
$P(k)=$ ``A tree with a degree $k$ vertex has at least $k$ leaves'' by strong 
induction on $k$.

{\bf Base case:}
$P(1)$ is true because a degree one vertex is by definition a leaf.

{\bf Inductive step:}
Consider a tree with a degree $k+1$ vertex $v$.  If $v$ is connected to a leaf,
remove that leaf.  The resulting tree has a degree $k$ vertex therefore it has
at least $k$ leaves.  Re-attach the leaf.  The initial tree has $k+1$ leaves.

If $v$ is not connected to a leaf, then $v$ is connected to $k+1$ vertices
$v_1, \ldots , v_{k+1}$ each being adjacent to at least one edge other than the
one connecting them with $v$. Let $H_1, \ldots , H_{k+1}$ be the subgraphs 
obtained by detaching $v_i$ from $v$.  Each of the $H_i$ is connected, because
there is a path from any vertex of $H_i$ to $v_i$, therefore,
by the lemma, they are subtrees.  
Furthermore, they are disjoint.  
For if there
is a path between $v_i$ and $v_j$, then there are two
paths connecting $v_i$ and $v_j$, since $v_i$ and $v_j$ are also connected
through $v$.  This contradicts the tree definition.

Now, since none of the $v_1, \ldots ,v_{k+1}$ is a leaf, each of the trees
$H_1, \ldots , H_{k+1}$ has a vertex of degree at least $1$, so by the
inductive hypothesis, each has at least one leaf.  Since the 
$H_1, \ldots , H_{k+1}$ are disjoint, the leaves are distinct.  Therefore the
original tree has at least $k+1$ leaves.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem{\bf [7 points]}

Let $G$ be a graph with $n$ vertices and $m$ edges. Let $dmax$ be the
maximum degree of the vertices of $G$, and let $dmin$ be the minimum
degree of the vertices of $G$. Show that
\bparts
\ppart $2m/n \geq dmin$.

\bigskip

First observe that $2m$ is the sum of the degrees of the vertices
(each edge contributes a degree of $2$ since it is incident to two
vertices).  But the total degree cannot be less than the minimum
degree multiplied by the number of vertices.  
This means that $2m \geq n \cdot dmin$ or that $2m/n \geq dmin$.


\ppart $2m/n \leq dmax$.

\bigskip

As before, observe that $2m$ is the sum of the degrees of the
vertices.  Since the total degree cannot be greater than the maximum
degree multiplied by the number of vertices.  
This means that $2m \leq n \cdot dmax$ or that $2m/n \leq dmax$.


\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%coloring problem by Tom Leighton
%Problem 7
\problem{\bf [10 point]}

You are given the following two facts.

F1)  Any subgraph of a planar graph is planar.

F2) Any planar graph with $n$ vertices and $m$ edges satisfies
$m \leq 3n-6$.

\bparts
\ppart Use (F2) to show\\


(F3) Any planar graph has a vertex of degree at most $5$.\\

\bigskip

Suppose that every vertex has degree at least $6$.  Then
$2m = \sum_{v \in V} deg(v) \geq 6n \rightarrow m \geq 3n$
which contradicts (F2).

\ppart Use F1 and F3 to show that any planar graph can be colored with six colors.

\bigskip

The proof is by induction on the number of vertices $n$.

$P(n) = $ ``A planar graph of $n$ vertices can be colored with at most
$6$ colors''.

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

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

Let $G$ be a planar graph with $n+1$ vertices and remove a vertex $v$ 
of degree 
$5$ (or less).  The remaining $n$-vertex graph can be colored with $6$ colors
by the inductive hypothesis.  Re-attach $v$.
$v$ is adjacent to at most $5$ vertices, occupying at most $5$ out of the
six colors.  We can use the remaining color to color $v$.

We have shown that $P(n) \rightarrow P(n+1)$, so the proof is complete.

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
\problem{\bf [15 points]}

Show that a directed multigraph has an Euler
circuit if and only if the graph is weakly connected and the in-degree and
out-degree of each vertex are equal.

\bigskip

First we will show that if the multigraph has an Euler circuit, then the 
graph is weakly connected and the  in-degree and
out-degree of each vertex are equal.

Suppose that the directed multigraph has an Euler circuit.  Since the circuit
provides a path from any vertex to any other vertex, the graph is strongly
connected (and therefore weakly connected). 
Now, by the existence of the
Euler circuit, every vertex is entered as many times as it is exited. 
Since every time a vertex is entered 1 is added to the in-degree count 
and every time 
it is exited 1 is added to the out-degree count, the degrees must have the 
same value.


Conversely, suppose that we have a directed multigraph $G$ which is weakly 
connected and the in-degree and out-degree of each vertex are equal.
We argue by contradiction.  Suppose that it doesn't have an Euler circuit
and let $C$ be a maximum-length cycle (allowing repeated vertices but not
repeated edges) in the graph.  If $C$ contains all the edges in $G$
we are done.  If not, there is an edge $e$ that is not in $C$.
Since $G$ is connected, there is a path from $e$ that eventually reaches
a vertex in $C$.  This means that there is an edge $e'$ that is not in $C$
and is incident to a vertex $v$ in $C$.
Now consider the subgraph $G-C$. Note that $v$ is a vertex of  $G-C$. 
Also note that
for any vertex in $C$, the in-degree has been decreased by 1 every time it
was entered and the out-degree decreased by 1 any time it was exited.  
Therefore the in and out degrees of the vertices in $G-C$ are still equal.

Start with vertex $v$ and construct a path in $G-C$ as follows.
We know that $v$ is adjacent to some edge $e'$, and since
the in and out degrees of $v$ are equal, there is at least one out-edge
connecting $v$ to some vertex $v_1$.  We let $(v,v_1)$ be the first 
vertex of the path and we proceed similarly from $v_1$ to construct a
path $C' = \{ v, v_1, \ldots , v_k \}$ as long it is possible without
repeating any edges.  

Note that $v_k$ can only be $v$. 
Otherwise, due to the fact that the in-degree and out-degree are
equal, there should be an edge leading out of $v_k$.  We conclude that $C'$
is a cycle.

Now consider the cycle in the original graph $G$ that starts at
$v$ goes around $C$ and then goes around $C'$.  This cycle contains at least
one more edge than $C$ (namely $e'$) so the maximality of $C$ is contradicted.

The proof is complete.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9 
%definition equivalence by Santosh
\problem{\bf [10 points]}

We provide an alternative definition for a tree.

{\em Definition:} A {\em tree} is a connected graph such that
$\forall u,v \in V$, there is a unique path connecting $u$ to $v$.

Prove that this definition is equivalent to the one that defines a tree
to be an acyclic graph of $n$ vertices that has $n-1$ edges.

\bigskip

Let $G$ be a graph  of $n$ vertices such that
$\forall u,v \in V$, there is a unique path connecting $u$ to $v$.

First we show that $G$ is acyclic.
Suppose, for the purposes of contradiction, that $G$ has a cycle.
Pick two vertices $u$ and $v$ on the cycle.  Then there are at least
two paths connecting $v$ and $u$, contradicting the uniqueness assumption.
So $G$ is acyclic.

Also we note that the existence of paths between every two vertices
 implies that
$G$ is connected.  So $G$ is a connected acyclic graph, and from class
we know that it has $n-1$ edges.

Conversely, let $G$ be an acyclic graph with $n$ vertices and $n-1$ edges.
We know from class that such a graph is connected so there exists at least 
one path between any two vertices.

Suppose, for the purposes of contradiction, that there are two distinct
paths $C$ and $C'$ connecting the vertices $u$ and $v$. 
Starting at $u$ consider the first vertex $u'$ where $C$ differs 
from $C'$ (such a vertex exists because the graphs are distinct).  
Also consider the first vertex $v'$ where $C$ and $C'$ meet again
(such a vertex exists because both paths end at $v$).  Then there is a
simple cycle that starts at $u'$ follows $C$ until it reaches $v'$ and
returns to $u'$ following $C'$.
This contradicts the acyclicity of the graph.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10
%equivalence relations and graphs
\problem{\bf [15 points]}

{\em Definition:}
Let $S$ be a set.  Let $R$ be a subset of $S \times S$.
$R$ is an {\em equivalence relation} if it satisfies the following properties

\begin{enumerate}
\item $\forall a \in S, (a,a) \in R$ (reflexivity).
\item If $(a,b) \in R$, then $(b,a) \in R$ (symmetry).
\item If $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$ (transitivity).
\end{enumerate}

{\em Definition:}
Let $R$ be an equivalence relation on $S$.  For $a \in S$, we define the
{\em equivalence class} of $a$ to be the set
$[a]_R = \{ b \in S | (a,b) \in R \}$.

For example, the relation $R$ defined by
$(a,b) \in R$ if $a \equiv b \text{ mod } 4$ is an equivalence
relation on $\integers$.  There are four equivalence classes for this relation,
namely:

\begin{itemize}

\item $[0]_R = \{ z \in \integers | z \equiv 0  \text{ mod } 4 \}$
\item $[1]_R = \{ z \in \integers | z \equiv 1  \text{ mod } 4 \}$
\item $[2]_R = \{ z \in \integers | z \equiv 2  \text{ mod } 4 \}$
\item $[3]_R = \{ z \in \integers | z \equiv 3  \text{ mod } 4 \}$

\end{itemize}

\bparts

\ppart Let $G$ be a simple graph.  Define a relation $R$ on the set of vertices $V$
of $G$ by $(v,u) \in R$, if there is a path connecting $u$ to $v$.

Verify that $R$ is an equivalence relation.

\bigskip

\begin{itemize}

\item Reflexivity:

$R$ is reflexive because trivially every vertex is connected to itself.

\item Symmetry:

Suppose there is a path $(u,x_1), (x_1,x_2), \ldots, (x_n,v)$ connecting 
$u$ to $v$.
Then, the path $(v,x_n), \ldots, (x_1,u)$ connects $v$ to $u$. 
Therefore, $R$ is symmetric.

\item Transitivity:

Let the path $(u,x_1), (x_1,x_2), \ldots, (x_n,v)$ connect $u$ to $v$, and
the path \\
$(v,y_1), (y_1,y_2), \ldots, (y_m,w)$ connect $v$ to $w$.

Then the path $(u,x_1), \ldots, (x_n,v), (v,y_1), \ldots ,(y_m,w)$
connects $u$ to $v$.\\
Therefore $R$ is transitive.

\end{itemize}

\ppart What are the equivalence classes of $R$?

\bigskip

The equivalence classes of $R$ are the connected components of $G$.

\eparts

\end{problems}

\end{document}
