\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

\begin{document}

\recitation{6}{September 29, 2004}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\insolutions{
%\stamp

\section{Graph Quiz!}

Rules: Teams take questions in cyclic order.  Each team has \textbf{15
seconds} to answer.  A correct answer is worth 1 point.  If a team can
not answer a question correctly, the question goes to the next team.
If no team can answer, the TA gets a point and provides the answer.
This test is open book.  Between problems, the game may stop for
questions.  The TA can change the rules in any way he or she sees fit
at any time.

Here is a picture of a graph $G = (V, E)$.

\begin{center}
\includegraphics[height=1.75in]{rec-example}
\end{center}

(The edge $\edge{E}{D}$ is absent initially, but will be added later.)

\begin{enumerate}

\item What are the elements of $V$ called?  Vertices.

\item What are the elements of $E$ called?  Edges.

\item What are the elements of $V$ in this case?  $\set{A, B, C, D, E, F}$

\item What are the elements of $E$ in this case?  $\set{\edge{A}{B},
\edge{A}{C}, \edge{B}{C}, \edge{B}{D}, \edge{C}{D}, \edge{E}{F}}$

\item Is this graph connected?  No.

\item What is the definition of \textit{connected}, anyway?  A graph
is connected if there is a path between every pair of vertices.

\item What is a \textit{connected component} of a graph?  A maximal,
connected subgraph.  Here, maximal means that including any more
vertices would yield a disconnected subgraph.

\item What are the connected components of this graph?

\begin{itemize}

\item The subgraph consisting of vertices $E$ and $F$ and the edge
between them.

\item The subgraph consisting of vertices $A$, $B$, $C$, and $D$ and
the edges between them.

\end{itemize}

\item \textbf{Now suppose we add the edge $\edge{E}{D}$.}  Is the
graph connected now?  Yes.

\item What is the distance between $A$ and $D$?  2

\item How is the distance between vertices $x$ and $y$ defined?  It is
the length of the shortest path between $x$ and $y$.

\item What is the diameter of this graph?  4

\item How is diameter defined?  It is the distance between the
farthest pair of vertices.  ($A$ and $F$ in this case.)

\item Is this a tree?  No.

\item What is a tree, anyway?  A connected, acyclic graph.  (However,
there are many other equivalent ways to characterize a tree and any
one could be taken as the definition.)

\item How many different cycles are there?  Three.  One with vertices
$A$, $B$, $C$, one with vertices, $B$, $C$, $D$, and one with vertices
$A$, $B$, $C$, and $D$.

\item What's a spanning tree of this graph?  There are several; one is
the subgraph with vertices $A$ through $F$ and edges $\edge{A}{B}$,
$\edge{B}{C}$, $\edge{B}{D}$, $\edge{E}{D}$, and $\edge{E}{F}$.  Later
answers assume this one.

\item What is a spanning tree of a graph $G = (V, E)$ anyhow?  A tree
with vertex set $V$ and edge set $E' \subseteq E$.

\item Does every graph have a spanning tree?  No, but every connected
graph does.

\item For the remaining questions, let's focus on that spanning tree.
Which vertices are the leaves of this tree?  $A$, $C$, and $F$

\item Does there exist a tree with the same number of vertices, but a
different number of edges?  No.  For every tree, $\size{V} = \size{E}
+ 1$.

\item Does there exist a tree with the same number of vertices, but a
different number of leaves--- yes or no?  Yes.

\item What's an example of a 6-vertex tree NOT isomorphic to the
spanning tree?  One example is a path of length 5.

\item What exactly does it mean for two graphs to be isomorphic?
There is a a one-to-one correspondence between the vertices in the two
graphs such that there is an edge between two vertices in the first
graph if and only if there is an edge between the two corresponding
vertices in the second graph.

\item How can you prove this spanning tree is not isomorphic to the
one two questions back?  In general, the simplest way is to identify
some distinguishing property, such as the number of vertices, number
of edges, number of leaves, or pattern of vertex degrees.  Any
argument along these lines is sufficient.

\end{enumerate}

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

\section{A False Proof}
}
Recall that a graph is \term{connected} if for every pair of vertices
$u$ and $v$, there is a path between $u$ and $v$.

\begin{falseclm*}
If every vertex in a graph has degee at least 1, then the graph is
connected.
\end{falseclm*}

\bparts

\ppart Prove that this Claim is indeed false by providing a
counterexample.

\solution%[\vspace{1in}]
{There are many counterexamples; here is one:

\mfigure{!}{0.75in}{false-connect-cx}

}

\ppart Since the claim is false, there must be at least one error in the
following ``proof''.  Find the first error.

%\instatements{\newpage}

\begin{proof}
We use induction.  Let $P(n)$ be the proposition that if every vertex
in an $n$-vertex graph has degree at least 1, then the graph is
connected.

\noindent \textit{Base case:} There is only one graph with a single
vertex and it has degree 0.  Therefore, $P(1)$ is vacuously true,
since the if-part is false.

\noindent \textit{Inductive step:} We must show that $P(n)$ implies
$P(n+1)$ for all $n \geq 1$.  Consider an $n$-vertex graph in which
every vertex has degree at least 1.  By the assumption $P(n)$, this
graph is connected; that is, there is a path between every pair of
vertices.  Now we add one more vertex $x$ to obtain an $(n+1)$-vertex
graph:

\mfigure{!}{1.75in}{false-connect-pic}

All that remains is to check that there is a path from $x$ to every
other vertex $z$.  Since $x$ has degree at least one, there is an edge
from $x$ to some other vertex; call it $y$.  Thus, we can obtain a
path from $x$ to $z$ by adjoining the edge $\edge{x}{y}$ to the path
from $y$ to $z$.  This proves $P(n+1)$.

By the principle of induction $P(n)$ is true for all $n \geq 1$, which
proves the theorem.
\end{proof}

\solution{The faulty assumption underlying this argument is that
\textit{every $(n+1)$-vertex graph with minimum degree 1 can be
obtained from an $n$-vertex graph with minimum degree 1 by adding 1
more vertex}.

The counterexample above shows that this assumption is false; there is
no way to build that 4-vertex graph from a 3-vertex graph with minimum
degree 1.  Thus the first error in the proof is the statement ``This
proves $P(n+1)$''.

More generally, this is an example of ``build-up error''.  Generally,
this arises from a faulty assumption that every size $n+1$ graph with
some property can be ``built up'' from a size $n$ graph with the same
property.  (This assumption is correct for some properties, but
incorrect for others--- such as the one in the argument above.)

One way to avoid an accidental build-up error is to use a ``shrink
down, grow back'' process in the inductive step: start with a size
$n+1$ graph, remove a vertex (or edge), apply the inductive hypothesis
$P(n)$ to the smaller graph, and then add back the vertex (or edge)
and argue that $P(n+1)$ holds.  Let's see what would have happened if
we'd tried to prove the claim above by this method:

\noindent \textit{Inductive step:} We must show that $P(n)$ implies
$P(n+1)$ for all $n \geq 1$.  Consider an $(n+1)$-vertex graph $G$ in
which every vertex has degree at least 1.  Remove an arbitrary vertex
$v$, leaving an $n$-vertex graph $G'$ in which every vertex has
degree... uh-oh

The reduced graph $G'$ might contain a vertex of degree 0, making the
inductive hypothesis $P(n)$ inapplicable!  We are stuck--- and
properly so, since the claim is false!}

\eparts

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

\end{document}
