\problemdata     
{graph-5}           
{equivalence of tree definitions}              
{}              
{S02 in-class Week 4} 		
{S02 Radhika}        	


\begin{problem}
Prove that 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$.

\solution{
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. 
\paragraph{$(1)\Longrightarrow (2)$} Suppose that $G$ is an acyclic graph with
$|E|=|V|-1$. We need to demonstrate the following two facts:

\begin{description}
\item[1. 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. $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$. 

\paragraph{Base case:} For $n=1$ and $n=2$ the claim holds, since in
both cases, a graph with $n-1$ edges is connected.
\paragraph{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{description}

\paragraph{$(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{description}
\item [1. $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. $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$.
\paragraph{Base case:} For $n=0$ and $n=1$, a connected, acyclic graph
can have at most $n-1$ edges. 
\paragraph{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{description}

}
\end{problem}