\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\renewcommand{\reading}{ \href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln4.pdf}
{Week 4 Notes}, Rosen \S 7 (excluding 7.6) and 8.1 }
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}


%\hidesolutions         
%\showsolutions

\begin{document}
\problemset{4}          
%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\begin{problem}

Let G be the digraph for a partial ordered set $(S,P)$. In other words,
$S$ is the set of nodes and $a,b\in S$ are connected via a directed edge iff
$aPb$. Prove that G cannot contain any cycles of length $>1$.

\solution{ 
  Suppose $G$ contains a cycle $\langle v_1, v_2...  v_n, v_1\rangle$ where
  $n\geq 2$ and there are directed edges connecting $(v_1, v_2), (v_2,
  v_3)$ etc. as well as $(v_n, v_1)$.  We show that this leads to a
  contradiction.
  
  It can inductively be seen that $(v_1, v_i)$ is an edge in $G$ for
  any $2\leq i\leq n$.  Base case: $v_1Pv_2$ by hypothesis.  Inductive
  step: suppose $v_1Pv_i$ for some $i<n$.  Also, $v_iPv_{i+1}$ by
  hypothesis and using transitivity, it follows that $v_1Pv_{i+1}$.

From the above proof, we can conclude as a special case that
$v_1Pv_n$.  However, these vertices are in a cycle and $v_nPv_1$ by
hypothesis.  Also, since the cycle contains more than one element,
$v_1\neq v_n$.  These statements contradict the antisymmetry property
of a partial ordering.
}
\end{problem}

\iffalse
\begin{problem}
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.

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


}


\end{problem} 
\fi

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\begin{problem}

A planar graph is one which can be drawn in the plane without any
edges crossing (i.e. without the lines or arcs representing them
intersecting except at common endpoints).  Any planar graph with $n$
vertices and $m$ edges satisfies $m \leq 3n-6$.  Show that
\begin{problemparts}
\problempart any planar graph has a node of degree at most $5$.\\

\solution{Suppose that every vertex has degree at least $6$.  Then
\begin{eqnarray*}
2m&=&\sum_{v \in V}\textrm{deg}(v)\geq\sum_{v \in V}6=6n\\
m&\geq&3n
\end{eqnarray*}
contradicting our assertion that $m \leq 3n-6$.
}


\problempart any planar graph can be colored with six colors.

\solution{

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.

}

\end{problemparts}
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
An $n$-node graph is said to be {\em tangled} if there is an edge
leaving every set of $\lceil\frac{n}{3}\rceil$ or fewer vertices.  As
a special case, the graph consisting of a single node is considered
tangled.  (Recall that the notation $\lceil x \rceil$ refers to the
smallest integer greater than or equal to $x$.)

\begin{problemparts}

\problempart Find the error in the proof of the following claim.

\bigskip

{\bf Claim.} Every non-empty, tangled graph is connected.

\bigskip

\begin{proof}
The proof is by strong induction on the number of vertices in the
graph.  Let $P(n)$ be the proposition that if an $n$-node graph is
tangled, then it is connected.  In the base case, $P(1)$ is true
because the graph consisting of a single node is defined to be tangled
and is trivially connected.

In the inductive step, for $n \geq 1$ assume $P(1), \ldots, P(n)$ to
prove $P(n+1)$.  That is, we want to prove that if an $(n+1)$-node
graph is tangled, then it is connected.  Let $G$ be a tangled,
$(n+1)$-node graph.  Arbitrarily partition $G$ into two pieces so that
the first piece contains exactly $\lceil\frac{n}{3}\rceil$ vertices,
and the second piece contains all remaining vertices.  Note that since
$n \geq 1$, the graph $G$ has a least two vertices, and so both pieces
contain at least one vertex.  By induction, each of these two pieces
is connected.  Since the graph $G$ is tangled, there is an edge
leaving the first piece, joining it to the second piece.  Therefore,
the entire graph is connected.  This shows that $P(1), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by strong induction.
\end{proof}

\solution{
The error is in the statement, ``By induction, each of these two
pieces is connected.''  This is not what the induction hypothesis
says; the induction hypothesis states that {\em if a graph is
tangled}, then it is connected.

In abstract terms, we are proving an induction hypothesis of the form
``if (this), then (that)''.  However, we erroneously use the induction
hypothesis as if it were simply of the form ``(that)'.
}

\problempart Draw a tangled graph that is not connected.

\solution{
\begin{figure}[htbp]
\centerline{\includegraphics[width=1.0in]{figures/ps3-tangled-cx}}
\caption{Tangled but non-connected graph}
\end{figure}
}

\problempart An $n$-node graph is said to be {\em mangled} if there is an edge
leaving every set of $\lceil\frac{n}{2}\rceil$ or fewer vertices.
Again, as a special case, the graph consisting of a single node is
considered mangled.  Prove the following claim.

\bigskip

{\bf Claim.} Every non-empty, mangled graph is connected.

\solution{
%\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that these exists an $n$-node graph that is mangled, but
not connected.  Then the graph must have at least two connected
components.  However, there can be at most one connected component
with more than $\lceil\frac{n}{2}\rceil$ vertices, since the graph has
only $n$ vertices in total.  Therefore, there exists a connected
component with $\lceil\frac{n}{2}\rceil$ or fewer vertices.  Since the
graph is mangled, there is an edge leaving this component.  But this
contradicts the definition of a connected component.
%\end{proof}
}

\end{problemparts}

\end{problem}


\begin{problem}
%Rosen \S 7.8, Exercise 16 (Station Channels)
How many different channels are needed for six stations located at the
distances shown in Table~\ref{stationchannels}, if two stations cannot
use the same channel when they are within 150 miles of each other?

\begin{table}[htbp]


\begin{center}
\begin{tabular}{|c|*{6}{|c}|}
\hline
&1&2&3&4&5&6\\
\hline
\hline
1&--&85&175&200&50&100\\
\hline
2&85&--&125&175&100&160\\
\hline
3&175&125&--&100&200&250\\
\hline
4&200&175&100&--&210&220\\
\hline
5&50&100&200&210&--&100\\
\hline
6&100&160&250&220&100&--\\
\hline
\end{tabular}
\end{center}
\caption{Station distances}\label{stationchannels}
\end{table}


\solution{
We draw a graph (see Figure~\ref{stationgraph}) in which any two
vertices are connected iff the 
locations they represent are within 150 miles of each other.
\begin{figure}[htbp]
\centerline{
\begin{picture}(240, 70)
\multiput(0, 10)(60, 0){5}{\circle*{5}}
\multiput(0, 10)(60, 0){4}{\line(1, 0){60}}
\put(180, 70){\circle*{5}}
\put(120, 10){\line(1, 1){60}}
\put(180, 70){\line(1, -1){60}}
\put(180, 10){\line(0, 1){60}}
\put(-5, -5){\makebox(10, 10){4}}
\put(55, -5){\makebox(10, 10){3}}
\put(115, -5){\makebox(10, 10){2}}
\put(175, -5){\makebox(10, 10){1}}
\put(235, -5){\makebox(10, 10){6}}
\put(185, 65){\makebox(10, 10){5}}
\end{picture}
}
\caption{Graph representing station locations}\label{stationgraph}
\end{figure}
Three colors are necessary and sufficient to color this graph: say
red for vertices 2, 4, 6; blue for 3 and 5; yellow for 1.  Thus three
channels are necessary and sufficient for the stations.
}
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% from fall 97, tutorial 3


\begin{problem} A graph is called \emph{bipartite} if its vertices can
  be colored with two colors such that no two vertices of the same
  color share a common edge.

Prove that a graph is bipartite iff it does not contain an odd
cycle.  (Note that you need to prove both directions of the iff).

\solution{\begin{theorem}
A graph $G$ is bipartite iff it has no odd cycles.
\end{theorem}
  
{\em Proof. }
\begin{enumerate}
\item   If $G$ is bipartite then it has no odd cycles.

Proof by contradiction.
Assume for the purpose of a contradiction that $G$ is bipartite and 
has an odd cycle, $C = v_1,v_2,..,v_{2k-1},v_1$.
Let $v_1$ be colored red. Then $v_2$ and $v_{2k-1}$ must be colored blue,
and then $v_3$ and $v_{2k-2}$ must be colored red and in general
for $1 < i \leq k$, $v_i$ and $v_{2k-i+1}$ must be the same color.
We prove this by induction on $i$.

{\em Ind. Hyp.} $P(i)$: In any two coloring of $C = v_1,v_2,..,v_{2k-1},v_1$, $v_i$ and $v_{2k-i+1}$ are the same color.

{\em Base.} $P(2)$. $v_2$ and $v_{2k-1}$ are adjacent to $v_1$, so they
must be colored differently from $v_1$, hence they get the same color.

{\em Step.} Assume $P(i)$. That is $v_i$ and $v_{2k-i+1}$ are the
same color, say red. Then $v_{i+1}$ must be blue and $v_{2k-i}$ must be 
blue also.

From $P(k)$ we have that $v_k$ and $v_{k-1}$ must be the same color which
is not allowed in a valid coloring.
But this implies that the vertices of $G$ cannot be colored with only
two colors. This is a contradiction since $G$ is bipartite and every 
bipartite graph can be colored with 2 colors.

\item If $G$ has no odd cycles then it is bipartite.

Each component of $G$ can be colored separately. So assume $G$ is
a connected graph. We will assign a {\em level} to every vertex of $G$.
Pick some vertex $w$ of $G$, place it at level 1. Then place all the
neighbors of $w$ at level 2. Now among the remaining vertices, 
place all those that are  neighbors of vertices
in level 2 at level 3 and so on. In general, level $i+1$ has the 
neighbors of vertices in level $i$ from the remaining graph.

Notice that each edge runs from some level to an adjacent level only,
i.e. an edge cannot jump across many levels.

Now to show $G$ is bipartite, we can color it as follows: give
the vertices in odd numbered levels the color red and the vertices
in even numbered levels the color blue.

Is this a valid coloring? Suppose not, i.e. there is some edge 
$(u,v)$ such that $u$ and $v$ are the same color. Then $u$ and $v$ 
must be on the same level $i$. Let $u,u_{i-1},u_{i-2},\ldots,w$ be
vertices on a shortest path from $u$ to the start vertex $w$. 
Similarly, let $v,v_{i-1},\ldots w$ be a shortest path from $v$ to $w$.
Let the first vertex where these paths meet be $u_k=v_k$. Then
$u_k,u_{k+1},\ldots,u,v,v_{i-1},\ldots,v_{k-1},v_k$ is a cycle of
odd length. Since we stopped at the first level where the paths had 
a common vertex, this must be a simple cycle: a vertex could not have
been repeated on either of the paths and there is only one vertex
that could have occured in both paths, namely the one where they first meet.
This is a contradiction since we assumed that $G$ has no odd cycles.
\end{enumerate}
\qed
}


\end{problem}

\iffalse


\begin{problem}

Let $G_n$ be a directed graph with vertices numbered $0, 1,
\ldots, n-1$.  There is a directed edge from vertex $i$ to vertex $j$
if and only if $j \equiv i^2 + i + 1 \pmod{n}$.  (See page 119 of
Rosen for a definition of $\equiv$ and $\pmod{n}$.  As a hint,
however, no number theory is required to solve this problem.)

\begin{problemparts}

\problempart Draw the directed graphs $G_1$, $G_2$, and $G_3$.

\solution{

\begin{figure}[htbp]
\centerline{\includegraphics[width=4.0in]{figures/ps3-digraph}}
\end{figure}
}

\problempart Prove that if $n \geq 1$, then $G_n$ is not a directed
acyclic graph.

\solution{
\begin{proof}
Consider the following sequence of vertices in graph $G_n$.

\begin{eqnarray*}
v_1 & = & 0 \\
v_2 & = & v_1^2 + v_1 + 1 \pmod{n} \\
v_3 & = & v_2^2 + v_2 + 1 \pmod{n} \\
\ldots & & \ldots \\
v_{n+1} & = & v_n^2 + v_n + 1 \pmod{n}
\end{eqnarray*}

Note that there is a directed edge from $v_i$ to $v_{i+1}$ for all $1
\leq i \leq n$.  Not all of the vertices $v_1, \ldots, v_{n+1}$ can
be distinct, since the graph contains only $n$ vertices.  Suppose
$v_j$ is the first vertex in the sequence to appear a second time, and
$v_k$ was the initial appearance of that vertex.  Than the sequence of
vertices $v_k, v_{k+1}, \ldots, v_{j-1}$ forms a directed cycle.
Therefore, $G_n$ is not a directed acyclic graph.
\end{proof}
}
\end{problemparts}


\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
An {\em automorphism} of a graph is a relabeling of the
vertices that preserves adjacency.  For example, the graph on the left
side of the figure below has the automorphism $a \rightarrow b, b
\rightarrow a, c \rightarrow c, d \rightarrow d$.  (Here the
notation $x \rightarrow y$ means that the vertex labeled $x$ is
relabeled $y$.)  The relabeled graph is shown on the right side of the
figure.  This relabeling is an automorphism because adjacency is
preserved; that is, in the relabeled graph, just as in the original,
$a$ is adjacent to $b$ and $c$; $b$ is adjacent to $a$ and $c$; $c$ is
adjacent to $a$, $b$, and $d$; and $d$ is adjacent to $c$.  Every
graph has a {\em trivial automorphism} that assigns each node its
original label.

\begin{figure}[htbp]
\centerline{\includegraphics[width=1.5in]{figures/ps3-auto}}
\end{figure}

\begin{problemparts}

\problempart List all non-trivial automorphisms of the graph below using the
$x \rightarrow y$ notation as in the example.

\begin{figure}[htbp]
\centerline{\includegraphics[width=1.5in]{figures/ps3-findauto}}
\end{figure}

\solution{
\[
\begin{array}{c}
a \rightarrow e, b \rightarrow f, c \rightarrow c, d \rightarrow d,
e \rightarrow a, f \rightarrow b, g \rightarrow g, h \rightarrow h \\

a \rightarrow e, b \rightarrow f, c \rightarrow c, d \rightarrow d,
e \rightarrow a, f \rightarrow b, g \rightarrow h, h \rightarrow g \\

a \rightarrow a, b \rightarrow b, c \rightarrow c, d \rightarrow d,
e \rightarrow e, f \rightarrow f, g \rightarrow h, h \rightarrow g
\end{array}
\]
}

\problempart Draw a graph with at least 2 nodes that has only the trivial
automorphism.

\solution{
\begin{figure}[htbp]
\centerline{\includegraphics[width=1.0in]{figures/ps3-noauto}}
\end{figure}
}

\end{problemparts}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\begin{problem}
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$.

\solution{
\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}

}

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\begin{problem}
Prove that in any undirected graph, the sum of the squares of
the vertex degrees is even, or provide a counterexample.
\solution{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.
}
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\begin{problem}
Prove that any tree with a degree $k$ vertex has at least $k$
leaves.  

\solution{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.
}

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\begin{problem}
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
\begin{problemparts}
\problempart $2m/n \geq dmin$.

\solution{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$.
}
\problempart $2m/n \leq dmax$.
\solution{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$.
}

\end{problemparts}
\end{problem}



\fi

\end{document}                            
