\begin{problem}[10]

\begin{falsethm}
If every vertex in a graph is adjacent to another vertex, then the
graph is connected.
\end{falsethm}

\begin{problemparts}
\problempart[3] Give a counterexample to show that the theorem is false.

\solution[\vspace*{3cm}]{Lots of easy counter-examples, need to draw
one}

Here is a proof of the false theorem using induction.

\begin{figure}[htbp]
\centering \includegraphics[height=1in]{figures/false}
\label{fig:false}
\end{figure}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the predicate that if every
vertex in an $n$-vertex graph is adjacent to another vertex, then the
graph is connected.  In the base case, $P(1)$ is trivially true
because there is only one vertex.

In the inductive step, we assume $P(n)$ to prove $P(n+1)$.  Start with an
$n+1$-vertex graph, $G'$, in which every vertex is adjacent to another
vertex.  Now take some vertex $v$ away from the graph and let the $G$ be
the remaining graph.  By assumption $v$ is connected in $G'$ to one of the
$n$ vertices of $G$; call that one $u$.

Now we must show that for every pair of distinct vertices $x_1$ and
$x_2$ in $G'$, there is a path between them.  If both $x_1$ and $x_2$
are vertices of $G$, then since $G$ has $n$ vertices, we may assume by
induction it is connected.  So there is a path between $x_1$ and
$x_2$.  Otherwise, one of the vertices is $v$ (say $x_1$) and the
other, $x_2$ is in $G$.  But $x_2$ is connected to $u$ by induction,
so there is a path from $x_1$ to $u$ to $x_2$ as shown in the above
figure.
\end{proof}

\problempart[7] Exactly where is the mistake in this proof. Briefly,
but clearly, explain.


\solution[\vspace*{3.5cm}]{ The error is in the statement
``\emph{since $G$ has $n$ vertices, we may assume by induction it is
connected.}''  The induction hypothesis does not say that every
$n$-vertex graph is connected, but only, ``{\em if every vertex in an
$n$-vertex graph is adjacent to another vertex,} then the graph is
connected''.  For example, if $G'$ is the graph with vertices 1, 2, 3,
4 and edges $\set{1,2}$ and $\set{3,4}$, then removing vertex 1 to
form $G$ leaves vertex 2 without an adjacent vertex in $G$, and we
can't conclude by induction that $G$ is connected (which of course it
isn't).

The core problem here is called ``buildup error'' and is a common source
of mistakes in inductive proofs.  Buildup error occurs when the induction
hypothesis $P(n)$ is itself an implication of the form $A(n) \Rightarrow
B(n)$.  In this instance, $A(n)$ is the statement, ``every vertex in an
$n$-vertex graph is adjacent to another vertex'' and $B(n)$ is the
statement, ``the graph is connected''.

In the inductive step of a correct proof, we assume $A(n) \Rightarrow
B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$.  In an erroneous
proof, we assume $B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$.
This is precisely what happened; we assumed, ``the graph is
connected'' rather than, ``if every vertex in an $n$-vertex graph is
adjacent to another vertex, then the graph is connected'.
}

\end{problemparts}
\end{problem}

\comment{Radhika}{From the notes directly. Need to draw a graph for
the solution to part (a). Need to check the wording for the false
proof to make sure it is easy for a stduent to clearly point out where
it went wrong. Also might be worthwhile to rewrite the solution to
indicate what we actually expect a student to write as the solution
(for grading)}
