\documentclass[11pt]{article}
\usepackage{macros-course-lectures}

\renewcommand{\thepage}{\arabic{page}}

%\makeslides

\begin{document}

\onlystudents

\lecture{notes7}{Graphs, Trees, Tours, and Paths}{February 24, 2000}

\forlecture{
Survey: who has been doing the self-study problems?

No more Velleman.

Survey: final exam schedule

Discuss ``grading'' problems and metagrading

For a change of pace, lots of theorems today will use well ordering
(equivalent to induction, but often cleaner)
}

\section{DAGs and Partial Orders}

In class, we defined partial orders: relations that are reflexive,
transitive, antisymmetric\.  In the tutorial and problem set we worked
with DAGs---directed acyclic graphs\.  These are basically the same
thing.

\begin{theorem}
Any partial order $\preceq$, with the reflexive ``loops'' $a \preceq
a$ removed, is a DAG.
\end{theorem}
\begin{proof}
  By contradiction\.  Suppose the resulting relation had a cycle
  $a_1,\ldots,a_k,a_1$ where $a_k \ne a_1$\.  By transitivity (and induction on
  the length of the path) we have $a_1 \preceq a_k$ and $a_k \preceq
  a_1$\.  Thus (since $\preceq$ is a partial order) $a_k=a_1$\.  This
  means the final step in our path is a loop on $a_1$\.  But we removed
  the loops so this step does not exist, a contradiction\.
\end{proof}

\begin{theorem}
The transitive reflexive closure of any DAG is a partial order.
\end{theorem}
  That is, given a DAG, the relation ``there is a path of length 0 or
  greater from $a$ to $b$ in the DAG'' is a partial order.
\begin{proof}
  The given relation is reflexive by definition, and transitive
  because, as we saw last time, we can ``concatenate'' paths from $a$
  to $b$ and from $b$ to $c$ to get an $a$-$c$ path\.  So we just have
  to prove antisymmetry\.  So suppose there is a path from $a$ to $b$
  and a path from $b$ to $a$ but $a \ne b$\.  Then concatenating these
  paths gives a path from $a$ to $a$ that contains a second vertex $b
  \ne a$---that is, a cycle\.  This contradicts the claim that we
  started with a DAG\.  
\end{proof}


So everything you've learned about DAGs has really also been telling
you about partial orders\.  So we won't say more about partial orders
today.


\section{Graphs}

Just like DAGs are a nice way to think about partial orders, graphs in
general are a nice way to think about relations\.  They give a picture
of the relation, which can be much more revealing than a list of
tuples\.  They motivate the study of other properties.

\subsection{Definitions}

We'll start with a bunch of definitions.  Many are inherited from the
definition of relations.  Others are slightly modified for
convenience.  Yet others are new.

\subsection{Simple Graphs}

A {\em graph} is a pair of sets $(V, E)$.  The elements of $V$ are
called {\em vertices}.  The elements of $E$ are called {\em edges}.
Each edge is a pair of distinct vertices.

We are going to concentrate on {\em undirected} graphs.  These
correspond to symmetric relations.  If edge $(u,v)$ is present, edge
$(v,u)$ is also present.  Therefore, it simplifies matters to think of
these two edges as one and the same.  This faintly violates the notion
of a Cartesian pair (where order matters) and really picky
mathematicians denote such an undirected edge by the unordered {\em
  set} $\set{u,v}$, but this rapidly fills up your paper with hard to
read $\set{}$ symbols.

Graphs are also sometimes called {\em networks}.  Vertices are also
sometimes called {\em nodes}.  Edges are sometimes called {\em arcs}.
Graphs can be nicely represented with a diagram of dots and lines as
shown in Figure~\ref{fig:graph}

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/graph.eps,height=2in}}
\caption{\em This is a picture of a graph $G = (V, E)$.  There are four
vertices and four edges.  The set of vertices $V$ is $\{1, 2, 3, 4\}$.
The set of edges $E$ is $\{(1,2), (1,3), (2,3), (3,4) \}$.  Vertex 1
is adjacent to vertex 2, but is not adjacent to vertex 4.}
\label{fig:graph}
\end{figure}

As noted in the definition, each edge $(u, v) \in E$ is a pair of
distinct vertices $u, v \in V$.  Edge $(u, v)$ is said to be {\em
incident} to vertices $u$ and $v$.  Vertices $u$ and $v$ are said to
be {\em adjacent} or {\em neighbors}.  Phrases like, ``an edge joins
$u$ and $v$'' and ``the edge between $u$ and $v$'' are common.

A computer network is can be modeled nicely as a graph.  In this
instance, the set of vertices $V$ represents the set of computers in
the network.  There is an edge $(u, v)$ if there is a direct
communication link between the computers corresponding to $u$ and $v$.

\forstudents{
\subsection{Not-So-Simple Graphs}

There are actually many variants on the definition of a graph.  The
definition in the preceding section really only describes {\em simple
  undirected graphs}.  There are many ways to complicate matters.

\subsubsection*{Multigraphs}

In a simple graph, there are either zero or one edges joining a pair
of vertices.  In a {\em multigraph}, multiple edges are permitted
between the same pair of vertices.

\subsubsection*{Self-Loops}

In a simple graph, each edge is a pair of distinct vertices.  A {\em
self-loop} is an edge that connects a vertex to itself.
Figure~\ref{fig:multigraph} depicts a multigraph with self-loops.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/multigraph.eps,height=1.5in}}
\caption{\em This is a picture of a multigraph with a self-loop.  In
particular, there are three edges connecting vertices 1 and 2 and there
is a self-loop on vertex 3.}
\label{fig:multigraph}
\end{figure}

\subsubsection*{Directed Graphs}

In a {\em directed graph} or {\em digraph}, edges are regarded not as
lines, but as arrows.  (The technical difference is that in a simple
graph each edge is an unordered pair of vertices, whereas in a
directed graph each edge is an ordered pair.)
Figure~\ref{fig:digraph} depicts a directed graph.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/digraph.eps,height=1.5in}}
\caption{\em This is a picture of a directed graph or digraph.}
\label{fig:digraph}
\end{figure}

\subsubsection*{Weighted Graphs}

Sometimes it is useful to associate a number with each edge in a
graph.  These numbers are usually called {\em weights}.  The weight of
an edge $(u, v)$ is often denoted $w(u, v)$.  (If there is no edge
between vertices $u$ and $v$, then often $w(u, v)$ is infinity or
zero.)
}

\subsection{Graphs in the Real World}

There are many real-world phenomena other than computer networks that
can be described nicely by graphs.  Here are some examples:

\begin{description}

\item[Airline Connections] Here the vertices are airports and edges
are flight paths.  We could indicate the direction that planes fly
along each flight path by using a directed graph.  We could use
weights to convey even more information.  For example, $w(i, j)$ might
be the distance between airports $i$ and $j$, or the flying time
between them, or even the air fare.

\item[Precedence Constraints] Suppose you have a set of jobs to
complete, but some must be completed before others are begun.  (For
example, Atilla the Hun advised that you should always to pillage {\em
before} you burn.)  Here the vertices are jobs to be done.  Directed
edges indicate constraints; there is a directed edge from job $u$ to
job $v$ if job $u$ must be done before job $v$ is begun.

\item[Program Flowchart] Each vertex represents a step of computation.
Directed edges between vertices indicate control flow.

\end{description}

\subsection{Standard Graphs}

Some graphs appear so frequently that they have names.  The most
important examples are shown in Figure~\ref{fig:zoo}.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/zoo.eps,height=3.0in}}
\caption{\em The types of graph shown here are so common that they
have names.  (a) The empty graph on five vertices, $E_5$.  An empty
graph has no edges at all.  (b) The cycle on five vertices, $C_5$.
(c) The complete graph on five vertices, $K_5$.  A complete graph has
an edge between every pair of vertices.  (d) A five-vertex line graph.
(e) A $5 \times 5$ 2-dimensional mesh.}
\label{fig:zoo}
\end{figure}


\subsection{Adjacency Matrices}

We defined a graph in terms of a set of vertices and a set of edges.
In a computer it is often represented by an {\em adjacency
  matrix}---another name for the matrix representation of the
underlying relation.

Some variants of simple graphs can also be described well by matrices.
For example, a weighted graph is naturally associated with a matrix
where $w(i, j)$ is the entry at row $i$ and column $j$.

\subsection{Subgraphs}

A {\em subgraph} of a graph $G = (V, E)$ is a graph $G' = (V' , E')$
such that $V' \subseteq V$ and $E' \subseteq E$.  For example, a
triangle is a subgraph of $K_4$ (the complete graph on four vertices),
but not of $C_4$ (a cycle with four vertices).


\subsection{Vertex Degree}

The {\em degree} of a vertex is the number of incident edges.  The
degree of vertex $v$ is often denoted $d(v)$.  For example, referring
to Figure~\ref{fig:zoo}, every vertex in an empty graph has degree 0,
but every vertex in a cycle has degree 2.  A look at the other
examples suggests the following theorem:

\begin{theorem}
In a graph with $m$ edges, the sum of degrees of the vertices is $2m$.
\end{theorem}

\begin{proof}
  By induction on the number of edges.  0 edges means the sum is 0 as
  claimed.  Consider an $m$-edge graph.  Take away one of the edges.
  The remaining graph has degree sum $2(m-1)$ (by induction).  Putting
  back the edge increments two degrees by one, so the degree sum 
  becomes $m$.
\end{proof}

\begin{corollary}
In every graph, there are an even number of vertices of odd degree.
\end{corollary}

\begin{proof}
  If we had an odd number of odd degrees, the degree sum would be
  odd.  But it is even.
\end{proof}

\section{Graph Coloring}

Time to discuss final exams.  The MIT Schedules Office needs to assign
a time slot for each final.  This is not easy, because some students
are taking several classes with finals, and a student can take only
one test during a particular time slot.  The Schedules Office wants to
avoid all conflicts, but wants to make the exam period as short as
possible.

This scheduling problem can be represented by a graph.  Let each
vertex represent a course.  Put an edge between two vertices if there
is some student that is taking both courses.  Identify each possible
time slot with a color.  For example, Monday 9-12 is red, Monday 1-4
is blue, Tuesday 9-12 is green, etc.  The problem of assigning time
slots to exams is then equivalent to the problem of assigning colors
to vertices.

If a student is taking two courses, then there is an edge between two
vertices.  If these vertices are the same color, then there is a
conflict because the student has to take exams for the two courses at
the same time.  Therefore, the problem is to color each vertex of the
graph so that no adjacent vertices have the same color and so that the
number of colors used is as small as possible.  An example is shown in
Figure~\ref{fig:exams}.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/exams.eps,height=2in}}
\caption{\em This graph represents the exam scheduling problem.  Each
vertex stands for a course.  An edge between two vertices indicates
that a student is taking both courses and therefore the exams can not
be scheduled at the same time.  Each exam time slot is associated with
a color.  A schedule that creates no conflicts corresponds to a
coloring of the vertices such that no adjacent vertices receive the
same color.}
\label{fig:exams}
\end{figure}

In general, the minimum number of colors needed to color the vertices
of a graph $G$ so that no two adjacent vertices are the same is called
the {\em chromatic number} and is written $\chi(G)$\footnote{This is
the Greek letter ``chi'' pronounced ``key'' by the ancient Greeks and
``kie'' by mathematicians and frats.}.  For example, if $G$ is the
3-cycle or triangle graph, then $\chi(G) = 3$.

In general, finding the chromatic number of a graph is very hard.
However, we can at least put some upper bounds on the chromatic
number.  For example, the chromatic number of an $n$-vertex graph is
certainly at most $n$, since every vertex could be assigned a
different color.

We can do better, however:
\begin{theorem}
Any graph in which the maximum vertex degree is $\Delta$ can be
colored with at most $\Delta+1$ colors.
\end{theorem}

This theorem implies, for example, that a graph with thousands of
vertices, each of degree 3, requires at most 4 colors.  The proof is
surprisingly easy:

\begin{proof}
  The proof is by induction.  Let $P(n)$ be the proposition that every
  graph with $n$ vertices, all with degree at most $\Delta$, can be
  colored using at most $\Delta + 1$ colors.

  For the base case, $P(1)$, we consider a single vertex with degree
  zero.  In this case, $\Delta = 0$ and the algorithm requires $ 1 \le
  \Delta+1$ colors.

  In the inductive step, assume $P(n)$ to prove $P(n+1)$.  Let $G'$ be
  the graph obtained from $G$ by removing a vertex $v$ and incident
  edges.  No vertex in $G'$ has degree greater than $\Delta$, since
  removing a vertex and incident edges can not increase the degree of
  any other vertex.  By induction, we can color $G'$ with at most
  $\Delta + 1$ colors.  

  Now we need to ``put back'' the vertex $v$ we removed and color it.
  But $v$ has at most $\Delta$ neighbors in $G$.  Among them, these
  other vertices can ``use up'' at most $\Delta$ colors.  Thus, one of
  our $\Delta+1$ candidate colors is still available to color the
  replaced vertex without violating the coloring rules.
\end{proof}

\section{Connectivity}

Is a graph all in one piece or composed of several pieces?  To walk
from one vertex to another, how many edges must one cross?  Are there
many different routes or just one?  These are questions about
connectivity.

\subsection{Basic Notions of Connectivity}

In a graph, a {\em walk} from a vertex $u$ to a vertex $v$ is a
sequence of edges $(u, x_1), (x_1, x_2), \ldots, (x_k, v)$.  A walk
may contain the same edge or vertex multiple times.

In a {\em simple path}, no vertex or is crossed more than once.
However, as a special case, the initial and final vertices may be the
same.  In other words, $u, x_1, x_2, \ldots, x_k$ are all distinct
vertices, and $x_1, x_2, \ldots, x_k, v$ are all distinct vertices,
but $u = v$ is permitted.

There is a walk from $u$ to $v$ iff there is a walk from $v$ to $u$;
one path is obtained from the other by reversing the sequence of
edges.  The same statement holds for simple paths.

A {\em circuit} is a path from a vertex back to itself, i.e. a
sequence of edges $(u, x_1), (x_1, x_2), \ldots, (x_k, u)$.  A {\em
  cycle} is a simple path from a vertex back to itself.  Thus, a walk
is to a circuit as a simple path is to a cycle; both of the former may
contain the same edge or vertex multiple times, but this is ruled-out
in the latter.

We say two vertices are {\em connected} if there is a walk between
them.
\begin{lemma}
  There is a walk between two vertices iff there is a simple path
  between them.
\end{lemma}
So we could equally say connected means there is a simple path between
them.
\begin{proof}
  Consider the shortest walk between the two vertices (this uses the
  well ordering principle, so is really induction).  Suppose it is not
  a simple path---so some vertex is repeated.  So the path has the
  form $a_0,\ldots,a_i,\ldots,a_j,\ldots,a_k$ where $a_i=a_j$.  But
  then $a_0,\ldots,a_,a_{j+1},\ldots,a_k$ is a shorter walk, a
  contradiction.
\end{proof}

A graph is {\em connected} if there is a path between every pair of
distinct vertices.  For example, referring back to
Figure~\ref{fig:zoo}, the empty graph is disconnected, but all others
shown are connected.

Connectedness is an equivalence relation. It is clearly reflexive (if
we allow for length 0 paths). It is symmetric because we can reverse
paths in an undirected graph.  It is transitive because we can
concatenate paths.

Like any equivalence relation, connectedness induces a partition of
the vertices into equivalence classes.  Each equivalence class is
called a {\em connected component}.  A component is a set of vertices
that can all reach each other, but can't reach any other vertices.


We can also say that a connected component of a graph is a subgraph
that is connected and maximal.  This is, if any more vertices are
added to the subgraph, then it is no longer connected.  For example,
every connected graph has exactly one connected component.  The empty
graph on $n$ vertices has $n$ connected components.  A graph with
three connected components is shown in Figure~\ref{fig:3comp}.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/3comp.eps,height=1.5in}}
\caption{\em This is a picture of a graph with 3 connected components.}
\label{fig:3comp}
\end{figure}

\subsection{Cuts}

Another way to look at connectivity is to see what prevents it.

\begin{definition}
  An {\em empty cut} of a graph $G$ is a partition of the vertices $V$
  into two nonempty sets $W$ and $V-W$ such that no edge connects $V$
  and $V-W$ (that is, no edge has one endpoint in each set).
\end{definition}

\begin{lemma}
A graph is connected iff it has no empty cuts.
\end{lemma}
\begin{proof}
  Suppose $G$ has an empty cut $(W,V-W)$.  Let $w \in W$ and $v \in
  V-W $.  We show by contradiction that there is no path from $v$ to
  $w$, which means $G$ is not connected.  So suppose there is a path
  $v=p_0,\ldots,p_k=w$ from $v$ to $w$.  Consider the smallest $j$
  such that $p_j \in W$. (This is using the well ordering principle:
  the set of $j$ such that $p_j \in W$ is nonempty since $k$ is in the
  set, so it has a smallest element $j$).  Note $j\ne 0$, so $p_{j-1}$
  is a vertex on the path that is not in $W$.  So the edge
  $(p_{j-1},p_j)$ has one endpoint in $W$ and the other in $V-W$,
  contradicting the claim that $(W,V-W)$ is an empty cut.

  For the other direction suppose $G$ is disconnected; we construct an
  empty cut.  By assumption there is a pair of vertices $v$ and $w$
  such that there is no path from $v$ to $w$.  Let $W$ be the set of
  vertices connected to $w$ (by a path).  Then $(W,V-W)$ is an empty
  cut.  For suppose the cut is not empty.  Then there is an edge
  $(x,y)$ with $x\in W$ and $y \in V-W$.  But there is a path from $w$
  to $x$.  Adding the edge $(x,y)$ gives a path from $w$ to $y$, so $y
  \in W$.  This is a contradiction.
\end{proof}

\subsubsection*{A False Theorem about Connectivity}

If a graph is connected, then every vertex must be connected to some
other vertex.  Is the converse of this statement true?  If every
vertex is connected to some other vertex, then is the graph connected?
The answer is no.  In fact, the graph with three connected components
showing in Figure~\ref{fig:3comp} is a counterexample.  So what is wrong
with the following proof?

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

Nothing helps a false proof like a good picture; see
Figure~\ref{fig:false}.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/false.eps,height=1.5in}}
\caption{\em This picture accompanies the false proof.  Two situations
are depicted.  In one, vertices $x_1$ and $x_2$ both lie among the
first $n$ vertices, and so there is a connecting path by induction.
In the second, $v = x_1$ and $x_2$ is among the first $n$ vertices.
In this case there is a connecting path because there is an edge from
$v$ to $u$ and a path from $u$ to $x_2$ by induction.}
\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 only one vertex.

In the inductive step, we assume $P(n)$ to prove $P(n+1)$.  Start with
an $n$-vertex graph; this is connected by induction.  Now add a vertex
$v$.  By assumption $v$ is connected to one of the first $n$ vertices;
call that one $u$.

Now we must show that for every pair of distinct vertices $x_1$ and
$x_2$, there is a path between them.  If both $x_1$ and $x_2$ are
among the first $n$ vertices, then there is a path by induction.
Otherwise, one of the vertices is $v$ (say $x_1$) and the other is
among the first $n$ vertices.  These are connected by the path from
$x_1$ to $u$ to $x_2$ as shown in the figure.
\end{proof}

The error is in the early statement ``Start with an $n$-vertex graph;
this is connected by induction.''  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''.

The core problem here is called ``buildup error'' and is a common
source of mistakes in inductive proofs.

The name buildup error arises from the intuition that usually drives
the error: that in order to create an instance of size $n+1$, you take
an instance of size $n$ and extend it by one.  If you are careless,
you can forget some of the possible ways a size $n+1$ problem can
arise: you fail to ``build'' all the size $n+1$ instances, so your
proof doesn't cover all the instances.

More formally, 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''.

\subsubsection*{A True Theorem about Connectivity}

If a graph has too few edges, then there can not be a path between
every pair of vertices.  More generally, a graph with a very small
number of edges ought to have many connected components.  (Remember,
``many connected components'' does not mean ``very connected'';
rather, it means ``broken into many pieces''!)  The following theorem
generalizes these observations.

\begin{theorem}
A graph with $k$ edges and $n$ vertices has at least $n - k$ connected
components.
\end{theorem}

For example, a graph with 0 edges and $n$ vertices has at least $n - 0
= n$ connected components.  A graph with 100 vertices and 35 edges
must have 100 - 35 = 65 connected components.

The theorem is proven by induction on $k$.  This may seem odd, because
for $k > n$, the theorem says that the number of connected components
is greater than some negative number!  This is useless, but certainly
true, so there is no harm.

\begin{proof}
The proof is by induction.

Let $P(k)$ be the predicate that an $n$-vertex graph with $k$ edges
has at least $n - k$ connected components.  In the base case, $P(0)$
holds because an $n$-vertex graph with 0 edges does have at least $n -
0 = n$ components.

In the inductive step, assume that an $n$-vertex graph with $k$ edges
has at least $n - k$ connected components to prove that an $n$-vertex
graph with $k + 1$ edges has at least $n - k - 1$ connected
components.  Let $G$ be a graph with $n$ vertices and $k + 1$ edges.
Remove one edge $e$.  The resulting graph has $n$ vertices and $k$
edges.  By induction there are at least $n - k$ connected components.

There are two possibilities when we replace the edge $e$.  First, if
$e$ is incident to two vertices in the same connected component, then
the number of connected components is unchanged at $n - k$.
Otherwise, if $e$ is incident to vertices in two different connected
components, then the two become a single connected component.  This
reduces the number of connected components by one to $n - k - 1$.  In
both cases, the number of connected components is at least $n - k - 1$
as claimed.
\end{proof}

If a graph has fewer than $n-1$ edges, then the theorem implies it has
more than one connected component.  Therefore, a graph must have at
least $n-1$ edges to be connected.  In fact, there are graphs with $n
- 1$ edges and a single connected component; the line graph of
Figure~\ref{fig:zoo} is an example.

Is this a complete proof?  Not quite.  We claimed that adding on edge
reduces the number of connected components by one.  This is obvious by
picture, but how do we prove it formally?  

\begin{lemma}
If an edge is added that connects two distinct components of a graph,
the number of components is reduced by one.
\end{lemma}
\begin{proof}
Suppose the added edge is $(v,w)$, and let $[v]$ and $[w]$ be the
connected components containing $v$ and $w$ respectively.  We claim
that upon adding edge $(v,w)$, we merge $[v]$ and $[w]$ into a single
component and affect no other components.

To see that no other component is changed, suppose for contradiction
that there is some vertex $q$ {\em not} in the component of $v$ or $w$
for which adding $(v,w)$ changes its component--that is, the set of
vertices it can reach.  There must be a new path from $q$ to some
other vertex $r$.  The only way this path can be ``new'' is if it uses
edge $(v,w)$.  So bother $v$ and $w$ are on the path from $q$ to $r$.
Suppose without loss of generality that $v$ appears first on the path.
Then there is a path from $q$ to $v$ that does not use edge $(v,w)$.
This path existed before we added $(v,w)$, meaning that $q$ is in the
same component as $v$.  This contradicts our initial assumption.
\end{proof}


\begin{corollary}
Deleting a graph edge increases the number of components by at most
one.
\end{corollary}
\begin{proof}
  Suppose deleting edge $e$ increased the number by more than one.  We
  have just seen that putting $$e$$ back can  decrease the number
  of components by at most one.  So deleting $e$ and putting it back
  would give a net gain in the number of components!  This is a
  contradiction.
\end{proof}




\section{Trees}

Important special type of graph for CS applications. 

We have just seen that $n-1$ edges are required for connectivity.
They are sometime sufficient (a line).  

Let's explore the smallest connected graphs.

\subsection{Definitions}

What is a good notion of smallest?  No wasted edges.
\begin{definition}
A {\em tree} is a connected graph with no cycles.
\end{definition}


\begin{figure}[htbp]
\centerline{\psfig{figure=figures/tree.eps,height=2.0in}}
\caption{\em  This tree has 11
  ``leaves'', which are defined as vertices of degree at most one.
  The remaining 7 vertices are called ``internal nodes''.}
\label{fig:tree}
\end{figure}

The vertices in a tree can be classified into two categories.
Vertices of degree at most one are called {\em leaves}, and vertices
of degree greater than one are called {\em internal nodes}.


Trees are usually drawn as in Figure~\ref{fig:tree} with the leaves on
the bottom.  Keep this convention in mind; otherwise, phrases like
``all the vertices {\em below}...'' will be confusing.
\forstudent{(The English mathematician Littlewood once remarked that
  he found such directional terms particularly bothersome, since he
  habitually read mathematics reclined on his back!)}

Trees arise in many problems.  For example, the file structure in a
computer system can be naturally represented by a tree.  In this case,
each internal node corresponds to a directory, and each leaf
corresponds to a file.  If one directory contains another, there there
is an edge between the associated internal nodes.  If a directory
contains a file, then there there is an edge between the internal node
and a leaf.

Trees can actually be defined several different ways, as the following
lemma shows).
\begin{lemma}
The following properties of a graph $G$ are equivalent (each implies
the others):
\begin{enumerate}
\item $G$ is a connected graph with no cycles 
\item $G$ is a connected graph that is disconnected by the removal of any
  edge, ie, a ``minimal'' connected graph.
\item $G$ is a graph with a unique simple path between every pair of
  vertices
\end{enumerate}
\end{lemma}
Since the definitions are equivalent, any one of them could have been
taken as the definition of a tree.

Theorems asserting that several mathematical statements are equivalent
are quite common.  One way to prove such a theorem would be to
consider every pair of statements in turn and prove them equivalent.
That is, we would prove $1 \Leftrightarrow 2$, $2 \Leftrightarrow 3$,
and $3 \Leftrightarrow 1$.

This is overkill.  A simpler approach is to show $1 \Rightarrow 2$, $2
\Rightarrow 3$, and $3 \Rightarrow 1$.  These three implications are
sufficient to prove every pair of statements equivalent.  For example,
$2 \Leftrightarrow 3$ follows because we prove $2 \Rightarrow 3$
directly, and prove $3 \Rightarrow 2$ with the two steps $3
\Rightarrow 1 \Rightarrow 2$.

\begin{lemma}
  $(1\implies 2)$ A connected graph with no cycles is disconnected by
  the removal of any edge.
\end{lemma}
\begin{proof}
  By contradiction.  Suppose we can delete edge $(u,v)$ without
  disconnecting the graph.  This means there is a path from $u$ to $v$
  that doesn't use $(u,v)$, and thus a simple path.  Adding edge
  $(u,v)$ to a simple path that doesn't use $(u,v)$ creates a cycle.
  This contradicts the claim of no cycles.
\end{proof}

\begin{lemma}
$(3 \implies 1)$ A graph with a unique simple path between any pair of
nodes is connected and has no cycles.
\end{lemma}
\begin{proof}
  It clearly meets the definition of connectivity.  To see there are
  no cycles we argue by contradiction.  Suppose we have a (simple)
  cycle $v_1,\ldots,v_k,v_1$.  Then there are 2 simple paths from
  $v_1$ to $v_k$, namely $v_1,\ldots,v_k$ and the edge $(v_1,v_k)$.
\end{proof}

\begin{lemma} 
$(2 \implies 3)$
A connected graph that is disconnected by the removal of any edge has
a unique simple path between any pair of vertices.
\end{lemma}
\begin{proof}
  Suppose there are two different simple $u$-$v$ paths.  Call one
  $P_1$: $u=x_0,x_1,\ldots,x_k=v$.  Call the other $P_2$:
  $u=y_0,\ldots,y_l=v$.  Let $i$ be the smallest such that $x_i \ne
  y_i$ (why does this have to exist?).  Claim: we can remove
  $(y_{i-1},y_i)$ without disconnecting $G$.  To see this, consider a
  pair of vertices $z$ and $w$.  There's a simple path between them at
  the start.  It remains to show there's still a path (doesn't need to
  be simple) after removing $(y_{i-1},y_i)$.  We use proof by cases.

Case 1:  $(y_{i-1},y_i)$ wasn't on the path.  Then the path remains
after removing $(y_{i-1},y_i)$.

Case 2: $(y_{i-1},y_i)$ was on the path.  WLOG, $y_{i-1}$ is
encountered first. So the path looked like
$z,\ldots,y_{i-1},y_i,\ldots,w$.  So there's a different path: go from
$z$ to $y_{i-1}$ on the first part of $z$-$w$ path, then from
$y_{i-1}$ to $u$ on the first part of $P_2$, then from $u$ to $v$ on
$P_1$, then from $v$ to $y_i$ on the second part of $P_2$, then from
$y_i$ to $w$ on the second part of the $z$-$w$ path.
\end{proof}


\subsection{Spanning Trees and Forests}

We've just argued that the ``minimal'' (poset, under edge containment)
connected graphs are trees.  It turns out that every connected graph
actually contains one:

\begin{defin}
A {\em spanning tree} of a graph is a subset of the graph edges that
forms a tree on all the graph nodes.
\end{defin}

Notice that the notion ``tree'' is an intrinsic concept (cares only
about the nodes adjacent to the edges of the tree), while ``spanning
tree'' is extrinsic (cares about whether you have all the graph's
nodes).

\begin{lemma}
Every connected graph contains a spanning tree.
\end{lemma}
\begin{proof}
  Well ordering.  Consider the counterexample with the fewest edges.
  If you cannot delete any edge and stay connected, it is a tree (3rd
  definition of tree).  So you can delete an edge and get a smaller
  counterexample.  Contradiction.
\end{proof}

Some graphs aren't connected; they don't have spanning trees.
Instead, they have spanning {\em forests}:

\begin{defin}
A {\em forest} is any acyclic graph.
\end{defin}

\begin{lemma}
Each connected component of a forest is a tree.
\end{lemma}
\begin{proof}
Each connected component of a forest is connected and acyclic.
\end{proof}

\begin{defin} 
A {\em spanning forest} for a graph $G$ is a forest that connects
every pair of vertices that were connected in $G$,
\end{defin}

People take some liberties with ``tree:'' they call a set of edges a
tree if it connects its vertices and is acyclic.  So we talk about a
forest as being ``a collection of trees'' even though each tree is
only on vertices of a connected component, not on all graph vertices.

In particular, a spanning forest $G$ is just a collection of trees,
one spanning each connected component of $G$.


\subsection{Counting Tree Edges.  Induction off Leaves}


\begin{defin}
A {\em leaf} is a node of degree 1.
\end{defin}

\begin{lemma}
  Any tree with more than one vertex has a leaf.
\end{lemma}
\begin{proof}
  Consider a longest simple path $v_1,\ldots,v_k$ (why does such
  exist?).  I claim $v_1$ is a leaf.  Proof: suppose not.  Then it has
  a second neighbor $x$.  Is $x=v_i$ for some $i$?  No, that would
  give a cycle.  Thus $x,v_1,\ldots,v_k$ is a longer simple path, a
  contradiction.
\end{proof}

The following is ``obvious,'' but I'll write down a proof for those who
want to read it.
\begin{lemma}
If we remove a leaf and its edge from a tree, we get a tree.
\end{lemma}
\begin{proof}
  Suppose we remove leaf $v$ and its one incident edge $(u,v)$.  We
  need to show the remaining graph is still connected (it is clearly
  still acyclic).  Consider the unique simple path between two other
  vertices $x$ and $y$.  Can $(u,v)$ be on this path?  No, because
  $(u,v)$ is the only edge incident on $v$, so we would have to
  traverse it twice to enter and leave $v$.  This would make a
  non-simple path.

  Since $(u,v)$ is not on the path from $x$ to $y$, there is still a
  path after we delete $(u,v)$.  This is true for all pairs $x$ and
  $y$, so the remaining graph is connected.
\end{proof}

\begin{lemma}
Any tree on $n$ vertices has $n-1$ edges.
\end{lemma}
\begin{proof}
(Trivial base case).  Inductive step:
Start with an arbitrary tree with $n+1$ nodes.
Remove one node and its incident edge.
By the previous lemma, the result is a tree (with $n$ nodes).
By the IH, this tree has $n-1$ edges.
So the original tree has $n$ edges.
\end{proof}

\begin{lemma}
Any $n$ vertex connected graph $G$ with $n-1$ edges is a tree.
\end{lemma}
\begin{proof}
  We proved earlier that to be connected (have one connected
  component) a graph must have at least $n-1$ edges.  So if we remove
  any edge from $G$, it becomes disconnected.  This is one of the
  definitions of a tree.
\end{proof}





\section{Euler Tours}

The Koenigsberg bridge problem: can we cross every bridge in Koenigsberg
exactly once, without repeats, returning to our starting point?

\forlecture{
\begin{verbatim}

          |    |           |     /
      ----|----|---   -----|----/
     /    |    |   \ /     |  
----<             --X--     
     \    |    |   / \     |
      ----|----|--/   \----|----\
          |    |           |     \

\end{verbatim}
}

This problem has a graph representation.

Euler, 1736, proved NO.  So we call such tours ``Euler Tours.''

\begin{theorem}
  If undirected $G$ has Euler tour, then $G$ is connected and every
  vertex has even degree.
\end{theorem}
\begin{proof}
Direct every edge according to tour.  We enter a vertex as many times
as we leave it.  So every vertex must have indegree
equal to outdegree.  So total even.
\end{proof}

100 years later, Hierholzer proved the converse (trouble with coming
second---no one remembers your name!)

\begin{theorem}
If $G$ is connected and has even degree, then it has an Euler tour.
\end{theorem}

\begin{lemma}
If $G$ has even degree and at least one edge, then it has a circuit.
\end{lemma}
\begin{proof}

If connected, handshaking proves $n$ edges, so not a tree, so cycle.
But this also applies to unconnected:  consider a component that
contains at least one edge and apply the above.  (There must be such
a component because every edge of the graph must be in one such component).
\end{proof}




\begin{proof} (Of main result)
By contradiction.

  Idea: Let $C$ be the longest circuit without any repeated edges.
  Delete it.  Delete all isolated vertices.  Since $C$ is not an
  Euler tour, some vertices remain.
  Some vertex $u$ that remains is on $C$.  Why?  Because $G$ is
  connected. Take any remaining vertex $v$, it has a path to a vertex in
  $C$.  The first time we reach an edge of $C$, we stop.  This gives
  $u$. Now, by the lemma, find a circuit containing $u$.  Attach to
  $C$, giving a bigger circuit.  (A contradiction.)
\end{proof}

\long\def\comment#1{}
\section{Hamiltonian Paths}

A slightly different question: is there a tour that traverses every
{\em vertex} exactly once?

Such a cycle is called a {\em Hamiltonian Cycle.}  

In a small variant, a simple path that traverses every vertex exactly
once is a {\em Hamiltonian Path}.

Small change, but suddenly, instead of answer being trivial, becomes
very complicated.  It is believed that no computer program can answer
this question efficiently (it is NP-complete).

\end{document}

DON'T ERASE---USE FUTURE YEARS



\begin{lemma}
Any graph with minimum degree exceeding $n/2$ has a Hamiltonian Cycle.
\end{lemma}
\begin{proof}
Consider longest simple path $v_1,\ldots,v_k$.  Suppose not
 everything.  Consider cases.  If $v_1$ or $v_k$ is adjacent to a
 vertex not on the path, then we can add that vertex at an end of the
 path and get a longer path, a contradiction.  So every neighbor of
 $v_1$ and $v_n$ is on the path.  Claim $G$ has a cycle on these
 vertices.  

 Let $v$ be a vertex
not in cycle.  It has degree $n/2$, we'll show can splice into cycle,
get longer cycle, Contradiction.

How can we splice?  Find two vertices adjacent on cycle, both neighbors
of $v$.

How?  Pigeonhole.  What pigeons?  neighbors of $v$.  What holes?
Adjacent pairs of nodes on cycle.  Cycle has (at most) $n-1$ nodes, so
can break into (at most) $\lceil (n-1)/2 \rceil \le n/2$ buckets.  So
two neighbors in one bucket, means 2 adjacent neighbors.
\end{proof}


This gives a special class of graphs with Hamiltonian Cycles.  In
general, no one knows how to find these well.  I helped publish what is
the currently theoretically best algorithm for finding long cycles.
In an $n$-vertex Hamiltonian graph, it will find one of length at
least $\log n$.  Not very good, is it?


\subsection{Oriented Trees}

Trees in CS (and elsewhere) are often drawn in a particular
orientation, one node at the top, called the {\em root}, and the
others on paths moving downward. \\
(Of course, {\em real} trees, like maples, etc., have the root at the
bottom, but no one in CS seems to have noticed this.) \\
\\
Depends on distinguishing one node, any node, as root. \\
Level $0$ node. \\
Then all its neighbors drawn just below it, level $1$. \\
Then all their neighbors, level $2$, etc. \\
{\em Rooted tree} = undirected tree + root. \\
Maximum level number $=$ {\em height} of rooted tree. \\
\\
Sometimes ``orient'' (direct) all the edges downward, producing a
directed tree. \\
Prove can do?


(Undirected) tree + root yields directed tree. \\
Note different roots yield different directed trees (can even have
different heights). \\
Draw example, Fig. 5. \\
\\
Could also change the order of siblings, same tree. \\
\\
With rooted tree, use terminology {\em parent}, {\em sibling}, {\em
ancestor}, {\em descendent}. \\
From genealogy trees (but neglecting spouse edges). \\
Draw one. \\
\\
Def: {\em subtree}. \\
\\
Definition:
A rooted tree is an $m$-ary tree, $m \geq 1$, if every internal vertex
has no more than $m$ children. \\
\\
Special case of $m = 2$ is binary tree. \\
Almost the same as we defined earlier in term (as an example to
illustrate recursive definitions); \\
there is a slight difference in that now we're not distinguishing left
and right. \\
Sometimes we do this, but then, if we're being careful, we call the
tree an {\em ordered rooted tree} instead of just a rooted tree. \\
Sometimes I'll be sloppy and not explicitly say ``ordered'',  although
I mean it. \\
\\
\\
Examples of uses of trees: \\
\\
Representing organization structure (who reports to whom). \\
Representing computer file systems (UNIX, almost) \\
\\
Will see more in a few minutes. 

\subsection{Counting on Trees}

What can we say about number of vertices, edges, internal vertices,
leaves, etc., in $m$-ary tree? \\
\\
First consider special case: full trees. \\
Define {\em full} $m$-ary tree -- each internal node has $m$ children. \\
(However, needn't have all leaves at same level -- draw examples. \\

\begin{theorem}
Suppose that a full $m$-ary tree ($m \geq 2$) has 
$l$ leaves,
$i$ internal nodes,
$e$ edges,
$n$ total nodes.
Then:
\begin{enumerate}
\item
(A basic relationship for full $m$-ary trees, $n$ in terms of $i$.)
$n = mi + 1$.
\item
(First consequence, $i$ in terms of $n$.)
$i = {n - 1 \over m}$.
\item
($l$ in terms of $n$)
$l = {(m-1)n + 1 \over m}$.
\item
($n$ in terms of $l$)
$n = {ml - 1 \over m - 1}$.
\item
($l$ in terms of $i$)
$l = (m-1)i + 1$.
\item
($i$ in terms of $l$)
$i = {l - 1 \over m - 1}$.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}
\item
Every vertex except root is child of an internal vertex. \\
So $n$ is equal to $1$ plus the number of children vertices. \\
Claim there are exactly $mi$ children vertices, since there are $i$
internal vertices and each has exactly $m$ children. \\
\item
Just solve the previous for $i$.
\item
Combine obvious fact $l = n - i$ and previous part.
\item
Solve previous for $n$.
\item
Combine obvious fact and part 1, solve for $l$.
\item
Solve previous for $i$.
\end{enumerate}
\end{proof}

Can say more for the further restricted case:  complete trees. \\
And {\em complete} $m$-ary tree (full and all leaves at same level). \\

\begin{theorem}
Suppose that a complete $m$-ary tree ($m \geq 2$) has 
$h$ height,
$l$ leaves,
$i$ internal nodes,
$e$ edges,
$n$ total nodes.
Then:
\begin{enumerate}
\item
$l = m^h$.
\item
$i = {m^h - 1 \over m - 1}$
\item
$n = {m^{h+1} - 1 \over {m - 1}}$
\item
$e = {m^{h+1} - 1 \over m - 1} - 1$
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}
\item
$l = m^h$ \\
\\
By induction on $h$. \\
BASE:  $h = 0$: $1 = m^0$ leaves. \\
INDUCTIVE: Assume for $h$, prove for $h+1$.  \\
Given tree $T$ of height $h+1$, children subtrees have height $h$, so
by inductive hypothesis, each has $m^h$ leaves. \\
Leaves of whole tree are exactly the leaves of the subtrees. \\
So $m \times m^h$, which $= m^{h+1}$, as needed. \\
\item
Have $i = {l - 1 \over m - 1}$, substitute previous part.
\item
Have $n = {ml - 1 \over m - 1}$, substitute expression for $l$.
\item
By subtracting $1$ from the previous.
\end{enumerate}
\end{proof}

The preceding theorem gives $l$, $i$, $n$, $e$ in terms of $h$ and $m$. \\
\\
Can use these counting results to get {\em upper bounds} for
non-complete, in fact, non-full $m$-ary trees, e.g.: \\
\begin{enumerate}
\item
$n \leq mi + 1$.
\item
$i \geq {n - 1 \over m}$.
\item
$l \leq {(m-1)n + 1 \over m}$.
\item
$n \geq {ml - 1 \over m - 1}$.
\item
$l \leq (m-1)i + 1$.
\item
$i \geq {l-1 \over m - 1}$.
\item
$l \leq m^h$.
\item
$i \leq {m^h - 1 \over m - 1}$
\item
$n \leq {m^{h+1} - 1 \over m - 1}$
\item
$e \leq {m^{h+1} - 1 \over m - 1} - 1$
\end{enumerate}

LTTR to prove these.

\subsection{Applications of Trees}

\subsubsection{Binary Search Trees}

To aid in storing and searching for data. \\
\\
Store data with {\em keys} from totally ordered set, at nodes of
ordered binary tree. \\
Do this to make it fast to insert and look up items using their keys. \\
\\
Invariant property to maintain: \\
Any value occurring in left subtree of node is $<$ value at node. \\
Any value in right subtree of node is $>$ value at node. \\
\\
Example: Fig. 6 \\
\\
Fast for searching. \\
E.g. to see if $t$ is in tree, compare from top,
go left if less, go right if greater, etc. \\
Trace and reach it. \\
E.g., to see if $n$ is in tree, trace -- not there. \\
The beauty is that the whole tree need not be searched, just one path. \\ 
Usually faster, unless tree is very skewed. \\
\\
Fast also for insertion of new data. \\
Trace. \\
\\
Deletion may leave empty nodes, needs special reorganization methods. \\
See in algorithms class 6.046.

\subsubsection{Compiling}

Very important use of trees is to represent programs, and pieces of
programs, internally during the compilation process.  \\
Trees give the structure of the program, which is not made explicit in
a linear text representation. \\
\\
Example: Arithmetic expressions \\
\\
E.g., (2 + x) - (3 - (x + y)) written as ...Fig. 7
Ordered tree. \\
\\
\\
Example: More interesting program structure: \\
\begin{verbatim}
if x > y then while x <= 5 do x := x+1; a:= a^2 
\end{verbatim}
Draw, Fig. 8 \\
\\
This kind of tree is called a {\em parse tree}.  \\
It is produced during the compilation process, by a compiler program. \\
\\
Besides containing the given information, it gets decorated with other
info, like the types of the variables. \\
It is then used as the basis for generating machine code. 

\subsubsection{Decision Trees}

Can represent the decision structure of a program. \\
Unwind loops, represent as tree. \\
\\
Example: Sorting a list of $4$ numbers $a,b,c,d$ (assume unequal): \\
Fig 9: \\
\\
Answers at bottom. \\
Height of tree corresponds closely to worst-case running time.

How many edges in a tree?  To answer this, we'll show two things: on
an $n$ vertex graph:
\begin{itemize}
\item more than $n-1$ edges implies cycle
\item less than $n-1$ edges implies disconnected.
\end{itemize}
So a tree has $n-1$ edges.

\begin{lemma} Any graph with finitely many vertices and minimum
  degree 2 or more has a cycle. 
\end{lemma}
\begin{proof}
  Start at some vertex $v_0$.  It has at least one neighbor $v_1$.
  Now define $v_k$ to be some neighbor of $v_{k-1}$ that is {\em not}
  $v_{k-2}$.  Always exists by minimum degree 2, so well defined.
  Suppose $n$ vertices.  By pigeonholing, two of $v_0,\ldots,v_n$, say
  $v_i$ and $v_j$, are same vertex.  Then $v_i,\ldots,v_j$ is a
  circuit, can turn to cycle.
\end{proof}

Not true for infinite graph.  Counterexample?

\begin{corollary}
Any $n$ vertex graph with $n$ (or more) edges has a cycle.
\end{corollary}
\begin{proof}
Well ordering.  Let smallest counterexample have $n$ vertices and $m
\ge n$ edges and no cycle.  Suppose has degree 0 node.  Deleting it
reduces $n$ but not $m$, doesn't create a cycle.  Contradicts choice
of $n$.  Suppose has degree 1 node $v$ with incident edge $e$.   Then
deleting $v$ and $e$ gives a graph with $n$ and $m$ reduced by $1$,
contradicts choice of $n$
(technical point: why is this still a graph?  Because we deleted every
edge that uses $v$).  So minimum node degree is 2.  But this must have
cycle by previous lemma.
\end{proof}

\begin{corollary}
Any tree has at most $n-1$ edges.
\end{corollary}

\begin{lemma}
Any nontrivial tree has a leaf.
\end{lemma}
\begin{proof}
First, note every tree has a node of degree less than 2.  Proof by
handshaking.  If $n$ degree two nodes, have $n$ edges.  

Now, suppose degree 0.  Then not connected.  So degree 1.
\end{proof}

\begin{lemma}
Every tree has a leaf.  
\end{lemma}
\begin{proof}
Degree 0 impossible (not connected).   So if no leaf, min degree is
2.  Implies cycle.
\end{proof}

\begin{lemma}
Any tree has $n-1$ edges.
\end{lemma}
\begin{proof}
  Induction.  Base case $n=2$ easy.  So consider $n$ vertex tree $T$.  It has
  a leaf $v$ with neighbor $w$.  Delete $v$ and edge $(v,w)$.  Claim
  remainder is $n-1$ vertex tree.  So has $n-2$ edges.  Now adding 1
  edge and 1 vertex.  

  Remains to show result is tree.  Is there a cycle?  No, because
  wasn't before.  So only trick is to show connected.  So consider
  vertices $x,y$.  Had simple $x$-$y$ path in original tree $T$.  Only
  problem: might have used $v$ and edge $(v,w)$.  But if reached $v$,
  then traversed $(w,v)$.  But then must have traversed $(v,w)$ right
  after.  So isn't simple path.  Contradiction.  So connected.
\end{proof}

\subsection{Paths in Trees}

Alternative definition often given for tree: \\

\begin{defin}
A tree is a graph with a unique simple path between every pair of
vertices.
\end{defin}

\begin{lemma}
This definition is equivalent to old.
\end{lemma}
\begin{proof}
  Suppose we have a connected graph with no cycles.  Consider vertices
  $x$ and $y$.  Have a path, since connected.  Why unique?  Because
  concatenation of two distinct paths (one $x$-$y$, other reversed
  $y$-$x$) form a circuit (slightly tricky to prove; need to rule out
  taking a path and its reversal, which is a circuit but contains no
  cycle).  So first def implies second.

  Suppose have a unique simple path between every pair.  Then
  connected.  Now suppose have cycle.  Then have two simple paths
  between any pair of vertices on the cycles (one in each direction).
\end{proof}


This yields a third equivalent definition:

\begin{defin}
  A tree is any minimal connected graph. That is, it is a graph that
  is connected but removing any edge makes it disconnected.
\end{defin}

Explain minimal: poset, under containment of edges.

\begin{lemma}
Equivalent.
\end{lemma}
\begin{proof}
Suppose unique simple path between every pair.  Then connected.
Suppose $(u,v)$ is an edge.  Then it is unique simple path from $u$ to
$v$.  So if remove, $u$ and $v$ are disconnected.

Suppose removing any edge disconnects.  Claim no cycle.  Proof:
suppose $v_1,\ldots,v_k,v_1$ is a cycle.  Then if graph is connected,
can remove edge $(v_1,v_2)$ and stay connected.  Why?  Take vertices
$x$ and $y$.  Connected before, so path between them.  If use edge
$(v_1,v_2)$, can replace with path $v_2,v_3,\ldots,v_k,v_1$ to get new
path.
\end{proof}
  
\end{document}

\endinput
