\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] Draw a counterexample to show that the theorem is false.

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

Here is an alleged proof of the false theorem.

\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
$G$ be the remaining graph.  By assumption $v$ is adjacent to one of
the $n$ vertices in $G$; call that vertex $u$.

%% note earlier ti said by assumption $v$ is connected in $G'$ which
%% does make any sense and can be misconstrued to mean that $G'$ is
%% connected which is the very thing we are trying to prove.
%% this may hit us later

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] Underline the first sentence where the proof above goes
wrong.  Briefly, but clearly, explain what's wrong.


\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).

This is a variant of ``buildup error.''  The argument implicitly assumes
that any size $n+1$ graph with the property that all vertices adjacent to
another vertex, is built up from a size $n$ graph with the same property,
but not every such size $n+1$ graph can be bulit this way.}

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