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

%\hidesolutions
\showsolutions

\begin{document}

\recitation{8}{March 2, 2005}

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

\section{Graphs and Trees}

The following two definitions of a tree are equivalent.

{\em Definition 1:} A tree is an acyclic graph of $n$ vertices that
has $n-1$ edges.

{\em Definition 2:} A {\em tree} is a connected graph such that
$\forall u,v \in V$, there is a unique path connecting $u$ to $v$.

In general, when we want to show the equivalence of two definitions,
we must show that if the first definition is met, so is the second,
and vice versa.
\textbf{$(1)\Longrightarrow (2)$} Suppose that $G$ is an acyclic graph with
$|E|=|V|-1$. We need to demonstrate the following two facts:

\begin{itemize}
  
\item[1.] \textbf{There is a unique path connecting any pair of
    vertices.}  The proof is by contradiction. Suppose that there
  exists a pair of vertices $(u,v)$ with two distinct paths $p_1$ and
  $p_2$ connecting $u$ to $v$. In more ``graphic'' terms, we have
  $u\stackrel{p_1}{\leadsto}v$ and $u\stackrel{p_2}{\leadsto}v$. Let
  $\stackrel{\leftarrow}{p_2}$ be the \emph{reverse} of path $p_2$
  (which takes us from $v$ to $u$). Then
  $u\stackrel{p_1}{\leadsto}v\stackrel{\stackrel{\leftarrow}{p_2}}{\leadsto}u$
  is a cycle from $u$ back to $u$, which contradicts the fact that $G$
  is an acyclic graph. Therefore, we conclude that there exists a
  \emph{unique} path between any two pairs of vertices.
  
\item [2.] \textbf{$G$ is connected.}  We want to prove that an
  acyclic graph $G$ with $n$ vertices and $n-1$ edges is connected.
  The proof is by induction on the number of vertices of $G$.
  
  \textbf{Base case:} For $n=1$ and $n=2$ the claim holds, since in
  both cases, a graph with $n-1$ edges is connected.
  \textbf{Inductive step:} Assume that the claim is true for all graphs
  up to size $n$. Consider an acyclic graph $G$ with $n+1$ vertices
  and $n$ edges. At least one of the vertices must have degree $1$
  (see note \footnote{Since there are $n$ edges, the sum of the
    degrees of the vertices is $2n$. There are $n+1$ vertices, which
    means that at least one vertex must have degree either $0$ or $1$
    (if they all had degree $2$ or more, the sum of the degrees would
    be $\geq 2n+2$). The $0$-degree vertex is actually imposible,
    because the subgraph of $n$ vertices would have $n$ edges, and
    this would create a cycle (see the second inductive proof).
    Therefore, at least one vertex has to have degree exactly 1. }).
  Now take that vertex of degree 1 and remove it, along with the
  associated edge. The graph $G'$ that remains has $n$ vertices and
  $n-1$ edges and is connected according to our induction hypothesis.
  We then restore the vertex we removed to get back to $G$ and notice
  that $G$ must also be connected because the subgraph $G'$ is
  connected, and the vertex $v$ we just took out is connected to the
  subgraph through its edge.

\end{itemize}

\textbf{$(2)\Longrightarrow (1)$}Starting from a graph $G$ that
satisfies the second definition,we want to show that the following two
things must be true:

\begin{itemize}
\item [1.] \textbf{$G$ is acyclic} We can prove this by conradiction.
  Suppose that there is a cycle in $G$, and take any pair $(u,v)$ of
  vertices in the cycle. Since we are in a cycle, we know that there's
  a path $p_1$ connecting $u$ to $v$ and another, different path $p_2$
  connecting $v$ to $u$. But then taking path $p_2$ in reverse would
  take us from $u$ to $v$, which contradicts the assumption that
  there's a \emph{unique} path connecting every pair of vertices.
  Therefore, we conclude that $G$ must be aclyclic.
  
\item[2.] \textbf{$G$ has $n-1$ edges.} We know that $G$ is a
  connected graph and above we showed that it must also be acyclic. In
  class we showed that an acyclic graph with $n$ vertices needs at
  least $n-1$ edges to be connected. We now need to prove that it can
  have \emph{at most} $n-1$ edges (otherwise, it will not be acyclic).
  The proof is by induction on $n$.
\textbf{Base case:} For $n=0$ and $n=1$, a connected, acyclic graph
can have at most $n-1$ edges.

\textbf{Inductive step:} Assume that all connected, acyclic graphs
with $n$ vertices or less have $\leq n-1$ edges. Consider a connected,
acyclic graph $G$ with $n+1$ vertices. Remove a vertex $v$ along with
all incident edges. This will create $k\geq 1$ connected
components\footnote{the case $k=1$ corresponds to the situation in
  which the removal of the vertex leaves us with a connected subgraph
  (one piece)}. Each connected component is connected (by definition)
and acyclic (since $G$ was acyclic). Therefore by our induction
hypothesis, the $i$th connected component ($1\leq i\leq k$) can have
at most $|V_i|-1$ edges. Thus the total number of edges will be at
most $n-k$. Now, we bring back the vetex we removed along with all its
incident edges. Notice that since $G$ is acyclic, the vertex cannot be
connected to each component with more than one edges\footnote{If there
  were two edges connecting the vertex to a connected component, we
  could go from the vertex to the connected component through the
  first edge, then find a path to the second connection point
  [guaranteed to exist b/c we are in a connected component] and return
  to the original vertex through the second edge. This would
  contradict the assumption that our original graph was acyclic}. This
means that the number of new edges is at most $k$, which brings our
total number of edges to at most $n-k+k=n$. Thus, the claim holds for
$G$ as well.
\end{itemize}

\newpage

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}

\end{document}
