\problemdata     
{S01-PS4-5}           
{graphs, induction}
{}              
{S01-PS4} 		
{S01 Karger}



\begin{problem}

 \textbf{Graphs --- Connectivity}
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 propostion 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.
\graphicspath{{/toc/a/class/6.042/spring02/freshRepository/figures/}}
\solution{
  \begin{samepage}

    \begin{center}
      \includegraphics[height=1in]{ps4-tangled-cx}
    \end{center}
  \end{samepage}
}

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