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

\begin{document}
\pset{3}{September 16, 1997}{Tuesday, September 23}

{\bf Reading assignment: 7.1-7.5,7.7 of Rosen,
7.8 optional}


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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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$.


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

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

Prove that any tree with a degree $k$ vertex has at least $k$
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$.
\ppart $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 node of degree at most $5$.\\

\ppart Use F1 and F3 to show that any planar graph can be colored with six colors.
\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 (see Rosen 
p.465 definition 5), and the in-degree and out-degree of each vertex are equal.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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 simple a 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.

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

\end{problems}

\end{document}
