\problemdata
{S00 ps4}
{tangled graphs}

\begin{problem}
% topic: tangled graphs
% source: fall98 pset3 Problem 6

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, that
is, for every set of at most $\lceil\frac{n}{3}\rceil$ vertices,
there is an edge between a vertex in the set and a vertex not in the
set.  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.

\emph{{\bf Theorem?}} Every non-empty, tangled graph is connected.

\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.  We can't be sure the two partitions
are themselves tangled, in which case our inductive hypothesis says
nothing about their connectivity.  See 3(b).
}


\problempart Draw a tangled graph that is not connected.

\solution{
\begin{solution}
\begin{figure}[htbp]
\centerline{\resizebox{!}{1in}{\includegraphics{figures/ps3-tangled-cx.eps}}}
\end{figure}
\end{solution}
}

\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 that every non-empty, mangled graph
is connected.

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