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

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

%\makeslides

\begin{document}

\lecture{notes7}{Graphs and Trees}
{September 28, 2000}

\noindent
Topics for today:
\begin{itemize}
\item
Graph coloring
\item
Graph connectivity
\item
Euler circuits 
\item
Hamiltonian circuits
\item
Trees
\end{itemize}
\reading{Rosen, Sections 7.4, 7.5, 7.8, 8.1, 8.2, 8.4, 8.5}

\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=/a/class/6.042/spring00/archive/lectures/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 $d$ can be
colored with at most $d$ 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}
Fix d.
The proof is by induction.  Let $P(n)$ be the proposition that every
graph with $n$ vertices, all with degree at most $d$, can be
colored using at most $d + 1$ colors.

For the base case, $P(1)$, we consider a single vertex.
Clearly, this can be colored with $1 \leq d + 1$ colors.

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

  Now we need to ``put back'' the vertex $v$ we removed and color it.
  But $v$ has at most $d$ neighbors in $G$.  Among them, these
  other vertices can ``use up'' at most $d$ colors.  Thus, one of
  our $d+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}

Definitions similar to those for digraphs.

In a graph, a {\em path} from a vertex $u$ to a vertex $v$ is a
sequence of vertices $u = u_0, u_1, u_2, \ldots, u_k = v$, where each
$(u_i,u_{i+1})$ is an edge of the graph.
A path may contain the same edge or vertex multiple times.

In a {\em simple path}, no vertex appears more than once.
However, as a special case, the initial and final vertices may be the
same.  In other words, $u_0, u_1, u_2, \ldots, u_{k-1}$ are all distinct
vertices, and $u_1, u_2, \ldots, u_k$ are all distinct vertices,
but $u_0 = u_k$ is permitted.

Because we are working with undirected graphs,
there is a path from $u$ to $v$ iff there is a path 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\/}, or {\em cycle\/} is a path from a vertex back to
itself, i.e. a path $u = u_0, u_1, u_2, \ldots, u_k = v$ where $u =
u_0 = u_k = v$.
%A {\em cycle} is a simple path from a vertex back to itself.  
%Thus, a path 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 path between
them.
\begin{lemma}
  There is a path between two vertices iff there is a simple path
  between them.
\end{lemma}
So we could equally well say connected means there is a simple path between
them.

\begin{proof}
Like the analogous proof for the digraph case. 
\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.

\begin{theorem}
In any undirected graph, connectedness is an equivalence relation.
\end{theorem}

\begin{proof}
It is reflexive because we allow length $0$ paths.
It is symmetric because we can reverse paths in an undirected graph.  
It is transitive because we can concatenate paths.
\end{proof}

Like any equivalence relation, connectedness induces a partition of
the vertices into equivalence classes.  Each equivalence class is
called a {\em connected component}.  A connected component is a set of vertices
each of which can reach all the others, and none of which can 
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=/a/class/6.042/spring00/archive/lectures/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}
A {\em cut\/} in a graph $G = (V,E)$ is a partition of the vertices
$V$ into two nonempty sets $W$ and $V - W$. \\
A cut is said to be {\em empty\/} provided that no edge of $G$
connects $W$ and $V - W$, that is, no edge has one endpoint in each set.
\end{definition}

\begin{theorem}
A graph is connected iff it has no empty cuts.
\end{theorem}
\begin{proof}
Show the equivalent proposition: a graph is disconnected iff it has an
empty cut. \\
\\
Suppose $G$ has an empty cut $(W,V-W)$.  \\
Let $w \in W$ and $v \in V-W $.  \\
We show that there is no path from $v$ to $w$, 
which implies that $G$ is not connected.  \\
We proceed by contradiction: 
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 that $G$ is disconnected and 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}

\subsection{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 with at least $2$ nodes 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=/a/class/6.042/spring00/archive/lectures/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(2)$ is trivially true.

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 \Rightarrow B$.
%[[[Actually, it should be ``for all $G$ with $n$ nodes, $A(G)
%\Rightarrow B(G)$''.]]]
In this instance, $A$ is the statement, ``every vertex is adjacent to
another vertex'' and $B$ is the statement, ``the graph is connected''.

In the inductive step of a correct proof, we assume $A \Rightarrow
B$ for $n$ in order to prove $A \Rightarrow B$ for $n+1$.  In an erroneous
proof, we assume $B$ for $n$ in order to prove $A \Rightarrow B$ for $n+1$.
This is precisely what happened; we assumed, ``the graph is
connected'' rather than, ``if every vertex is
adjacent to another vertex, then the graph is connected''.

\subsection{Number of Connected Components}

Now a true theorem about connectivity...

We start with the common-sense observation that if a graph has too few 
edges, it cannot contain 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
makes these observations concrete. 

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

For example, a graph with $0$ edges and $20$ vertices has at least $20 - 0
= 20$ connected components.\\
A graph with 100 vertices and 35 edges must have at least 100 - 35 =
65 connected components. \\
A graph with 35 vertices and 100 edges must have at least 35 - 100 =
-65 connected components. \\
(True, but not very interesting.) \\
\\
The theorem is proved by fixing any generic $n$, and then working 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 true, so there is no harm.

\begin{proof}
Fix $n$. 
The proof is by induction on $k$, starting from $k = 0$. \\
\\
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. \\
\\
For the inductive step, assume that an $n$-vertex graph with $k$ edges
has at least $n - k$ connected components, and try 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$, which gives a subgraph $G'$. \\
The resulting graph $G'$ has $n$ vertices and $k$ edges.  \\
By inductive hypothesis, this graph $G'$ has at least $n - k$
connected components. \\
\\
Now consider what happens to the number of connected components when
we add the edge $e$ back in. \\
There are two possibilities: $e$ may be incident on two vertices
in the same connected component of $G'$, or two vertices in different
connected components of $G'$. \\
\\
In the first case, where $e$ is incident on two vertices in the same connected
component, then the number of connected components is unchanged when
$e$ is added back in, that is, $G$ has at least $n - k$ connected
components in this case. \\
\\
In the second case, where $e$ is incident on vertices in two different 
connected components of $G'$, the two become a single connected
component when $e$ is added back in. \\
This reduces the number of connected components by exactly one, which
implies that there are still at least $n - k - 1$ connected components
in $G$. \\
\\
In both cases, the number of connected components is at least $n - k -
1$, which is what we need to show. 
\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 one edge
between two separate connected components 
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 both of $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 {\em 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}

% 3:00

\section{Euler Tours}

We have already seen Euler circuits for directed graphs---circuits
that traverse every edge of the digraph exactly once.  
We can consider the same kind of problem for undirected graphs. \\
\\
The Koenigsberg bridge problem: can we cross all seven bridges in the
town of Koenigsberg
exactly once, without repeats, returning to our starting point?
%[[[Could use an improved picture.]]]
\begin{verbatim}

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

\end{verbatim}
This problem has a graph representation as shown in Figure~\ref{fig:euler} \\

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/euler.eps,height=1.5in}}
\caption{\em Graph representation for the Koenigsberg bridge problem.}
\label{fig:euler}
\end{figure}

Stated as a general graph theory problem, the problem is to construct
a circuit of the graph that traverses every edge exactly once. 
(Each edge will be traversed in exactly one direction.) \\
(Actually, note that the Koenigsberg graph is technically a
multigraph, not a simple graph, because it has multiple edges between
two of the pairs of vertices. 
We could change this into a simple graph by adding some extra vertices
in the middle of the repeated edges.) \\
Euler, 1736, proved that it can't be done.
So we call such tours ``Euler Tours.''
\
\begin{theorem}
If undirected graph $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 (that's the trouble with coming
second---no one remembers your name!)
\begin{theorem}
If $G$ is connected and every node has even degree, 
then it has an Euler tour.
\end{theorem}

\begin{proof}
If $G$ has only one node then it has a trivial (1-node) Euler tour.
So assume $G$ has at least two nodes.
Then $G$ must have at least one edge. \\
\\
Starting from this edge, construct a circuit with no repeated edges:
trace from node to node until we cannot go any further on an unused
edge. \\
(Example) \\
Because every node has even degree, this can only happen when we
return to the node we started at (every other node we reach will have
another edge by which we may leave). \\
\\
Let $C$ be the longest circuit without any repeated edges.
If $C$ includes all the edges of $G$, we are done.  So assume it
doesn't. \\
Let $H$ be the subgraph of $G$ consisting of all the edges of $G$ that
aren't in $C$, and all the nodes of $G$ that are incident on these
edges. \\
Claim that some node $u$ in $H$ is also in $C$. \\
Why?  Because $G$ is connected. \\
\\
Now choose any edge of $H$ incident upon $u$. \\
Starting with that edge, construct a cycle in $H$, following the same
procedure as above. \\
Eventually, it has to get back to its starting point $u$.\\
Now we have two cycles with disjoint edge sets and a common vertex 
$u$. \\
Splice them together to get a larger cycle than $C$. \\
Contradicts choice of $C$ as maximum. 
\end{proof}

% 3:10

\section{Hamiltonian Circuits}

A slightly different question: is there a simple circuit that traverses every
{\em vertex} exactly once? \\
Such a circuit is called a {\em Hamiltonian circuit\/} (Hamiltonian
cycle). \\
Similarly, a simple path that traverses every vertex exactly
once is a {\em Hamiltonian path}. \\
\\
Small change from the Euler circuit question, but suddenly, instead of
answer being trivial, it becomes very complicated.  \\
It is believed that there is no simple criterion to determine whether
or not a graph has a Hamiltonian circuit;
in fact, it is believed that no computer program can answer
this question efficiently (it is NP-complete). \\
\\
The book has some simple criteria for existence and nonexistence of
Hamiltonian cycles. 
Here is a slightly harder result. 

\begin{lemma}
Any graph with $n$ vertices, $n \geq 3$, in which the minimum degree
of each node is at least $n/2$, has a Hamiltonian circuit.
\end{lemma}

%[[[The proof in last semester's notes was wrong, because it assumed
%that the new vertex's neighbors all had to be on the cycle.  
%This one comes from Bondy and Murty, p. 54-55.]]]

\begin{proof}
By contradiction. \\
Suppose some graph has $n$ vertices, $n \geq 3$, and the minimum degree
of each node is at least $n/2$, but that graph does not have a
Hamiltonian circuit. \\
If we add edges to this graph one at a time, we eventually end up with
a complete graph, which does have a Hamiltonian circuit. \\
(Why?) \\
Somewhere in the process of adding edges, we have a graph $G$ 
that doesn't have a Hamiltonian circuit, but adding one more edge
$(u,v)$ yields a graph $G'$ that does have a Hamiltonian circuit. \\
We'll get a contradiction for this $G$. \\
\\
Since $G$ plus the one edge $(u,v)$ has a Hamiltonian circuit, $G$
alone has a Hamiltonian path from $u$ to $v$ (just remove the one new
edge). \\
Write $u = u_1,\ldots, u_n = v$, includes all the nodes of $G$. \\
\\
Now let's play with that path and turn it into a circuit, to get a
contradiction. \\
We will use the fact that $u$ and $v$ each have degree at least $n/2$
to produce two edges to replace one edge $(u_i,u_{i+1})$ on the
path... \\


\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/hamiltonian.eps,height=2in}}
\caption{\em Converting the Hamiltonian path into a circuit}
\label{fig:hamiltonian}
\end{figure}

Now let's count:
Of the $n-2$ intermediate nodes on the path 
$u_2,\ldots,u_{n-1}$ (all but the first and last) we know that at
least $n/2$ are neighbors of $u$, and at least $n/2$ are neighbors of $v$. \\
So it can be shown that there are two adjacent nodes, $u_i$ and
$u_{i+1}$, where $u_i$ is a neighbor of $v$ and $u_{i+1}$ is a
neighbor or $u$. \\
Postpone this for a minute... \\
Then cut and add edges, to produce a Hamiltonian circuit,
contradiction. \\
\\
Now, how do we get $u_i$ and $u_{i+1}$? \\
Just count how many are in various sets.  Use a little trick: \\
Let $S$ be $\{ i: u_{i+1} \mbox{ is a neighbor of } u \}$. \\
Let $T$ be $\{ i: u_i \mbox{ is a neighbor of } v \}$. \\
Each of $S$ and $T$ has at least $n/2$ elements.
Since there are only $n-2$ possible values of $i$, some $i$ must be in
both sets. \\
That is, $u_i$ is a neighbor of $v$ and $u_{i+1}$ is a neighbor of $u$.
\end{proof}

This gives a special class of graphs with Hamiltonian circuits.
But no one has nice criteria for finding Hamiltonian circuits in
general, or for determining if they exist. 

% 3:20

\section{Trees}

Important special type of graph for CS applications. \\
Trees are the ``smallest'' connected graphs, in the sense that they
have the fewest edges required for connectivity. \\
We will provide definitions and basic properties, including looking at
some alternative definitions and showing they are equivalent. \\
\\
We will count numbers of vertices and edges. \\
\\
We will relate trees to graphs, by talking about spanning trees and
spanning forests. \\
\\
We will show some places where trees are used in computer science:  
Decision trees, binary search trees, parse trees, tree-structured file
systems,... \\

\subsection{Basic definitions}

\begin{definition}
A {\em tree} is a connected (undirected) graph with no simple circuits
of length $> 2$.
\end{definition}

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/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 can 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 simple circuits of length $>2$ 
(a tree, as defined above). 
\item $G$ is a connected graph that is disconnected by the removal of any
  edge, i.e., a ``minimal'' connected graph.
\item $G$ is a graph with a unique simple path between every pair of distinct
  vertices.
\end{enumerate}
\end{lemma}
Since the definitions are equivalent, any one of them could be
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 would be 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 simple circuits of length
$>2$ 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)$.
Therefore, there is a simple path from $u$ to $v$ that doesn't use
$(u,v)$.
Adding edge $(u,v)$ to this simple path creates a simple circuit.
This contradicts the claim of no simple circuits.
\end{proof}

\begin{lemma}
$(3 \implies 1)$ A graph with a unique simple path between any pair of
nodes is connected and has no simple circuits of length $> 2$.
\end{lemma}

\begin{proof}
It clearly meets the definition of connectivity.  To see there are
no simple circuits we argue by contradiction.  \\
Suppose we have a simple circuit $v_1,v_2,\ldots,v_k,v_1$ of length $>2$.\\
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}
We prove the contrapositive.
Suppose there are two different simple paths from $u$ to $v$.  \\
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 the edge $(y_{i-1},y_i)$ without disconnecting
$G$.  \\
To see this, consider any 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}

%[[[From here to end of this subsection, we have some old proof
%sketches for the various other implications.]]]

\remove{
1 implies 3
  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.
%
Explain minimal: poset, under containment of edges.
%
3 implies 2:
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.
%
2 implies 1
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 remove 

% 3:30

\subsection{Counting tree nodes and edges}

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

\begin{lemma}
Any tree with more than one vertex has at least one leaf.
\end{lemma}

\begin{proof}
Consider a longest simple path $v_1,\ldots,v_k$ (why does such
exist?). \\
Claim $v_1$ is a leaf. \\
Proof: suppose not.  \\
Then $v_1$ has a second neighbor $x$. \\
Is $x=v_i$ for some $i$?  No, that would give a simple cycle of length
$> 2$.  \\
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}
By induction on $n$, starting from $n=1$. \\
Base case is trivial. \\
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 inductive hypothesis, 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}
Let's use the second definition of a tree---minimal connected
graph. \\
We are assuming that $G$ is connected. \\
We must show that if we remove any edge from $G$, the resulting graph
is disconnected. \\
\\
Since $G$ has $n-1$ edges, removing any edge reduces the number of
edges below $n-1$. \\
But we proved earlier that to be connected (have one connected
component) a graph must have at least $n-1$ edges.  \\
So that means that removing any edge disconnects the graph.
\end{proof}

So, we actually have yet another equivalent definition of a tree:
a connected graph with $n$ nodes and $n-1$ edges (for some $n$).

\remove{
[[[The following are some leftover related lemmas.]]]
%
\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}
} % end remove

% 3:35

\subsection{Spanning Trees and Forests}

This subsection wasn't covered in lecture, but will be covered in
Friday's tutorial.

We've just seen that the ``minimal'' (poset, under edge containment)
connected graphs are trees.  It turns out that every connected graph
contains a tree:
\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}
Example \\
\\
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}
By contradiction. \\
Suppose there is some counterexample, and use well-ordering to obtain
a counterexample graph $G$ with the fewest edges. \\
Because it's a counterexample, $G$ is connected, but has no spanning tree. \\
\\
There are two cases: \\
\\
1. You can delete some edge from $G$ and stay connected. \\
Then you get a smaller counterexample (still have no spanning tree). \\
That contradicts the way $G$ was chosen. \\
\\
2. Any way of deleting an edge disconnects $G$. \\
But that means that $G$ itself is a tree. (Second definition of tree). \\
So $G$ does have a spanning tree (itself).  Contradiction.
\end{proof}

Example: \\
The notion of a spanning tree arises in computer network graphs. \\
A network graph generally connects nodes by multiple paths, in order
to tolerate failures, changes in the network, and congestion. \\
But during relatively stable, lightly-loaded periods of time, it's
desirable to minimize the amount of communication, and conduct the
communication on predictable paths. \\
For this purpose, a spanning tree of the portion of the network
involved in some application is generally constructed (e.g., IP
Multicast does this) and used for communication. \\
\\
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}
Example \\
%\\
%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. \\
%\\
Thus, a spanning forest $G$ is just a collection of trees,
one spanning each connected component of $G$.

% 3:45

\subsection{Rooted 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.) \\
\\
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. \\
Note different roots yield different directed trees (could even have
different heights). \\
\\
Example \\
\\
Terminology: \\
{\em Parent}, {\em sibling}, {\em ancestor}, {\em descendent}.  
From genealogy. \\
{\em Subtree}. \\
\\
Note:  Changing the order of siblings doesn't change the tree. \\
\\
Examples of uses of rooted trees: \\
\\
Representing organization structure (who reports to whom). \\
\\
Representing computer file systems (UNIX, almost) \\
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. \\
\\
See more later. \\
\\
Some special kinds of rooted trees: $m$-ary, full $m$-ary, complete $m$-ary \\
\\
Definition:  An $m$-ary tree, $m \geq 1$, is a rooted tree in which
every internal vertex has no more than $m$ children. \\
\\
Special case where $m = 2$ is binary tree. \\
Almost the same as we defined earlier in term (as an example to
illustrate recursive definitions and structural induction). \\
Slight difference:  Now we're not distinguishing left and right. \\
(If we want to do this, we should call the structure an
{\em ordered rooted tree} instead of just a rooted tree.) \\
\\
Definition:  A {\em full\/} $m$-ary tree is an $m$-ary tree in which
each internal node has exactly $m$ children. 
(However, all leaves need not be at the same level.) \\
A {\em complete} $m$-ary tree is a full $m$-ary tree in which all the
leaves are at the same level. \\
\\
Examples 

\subsection{Counting on rooted trees}

What can we say about number of vertices, edges, internal vertices,
leaves, etc., in $m$-ary trees? \\
Fix some values. \\
Suppose that $T$ is a full $m$-ary tree ($m \geq 2$) with $l$ leaves,
$i$ internal nodes, $e$ edges, and $n$ total nodes. \\
Start with the most restrictive case, complete $m$-ary trees:
\begin{theorem}
For a complete $m$-ary tree ($m \geq 2$):
\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 step: 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
Again, use induction on $h$.
\item
Again, use induction on $h$.
\item
Use the previous part and the fact that $e = n - 1$. 
\end{enumerate}
\end{proof}

For a full, but not necessarily complete, tree, things are a little
more complicated:
\begin{theorem}
For a full $m$-ary tree ($m \geq 2$):
\begin{enumerate}
\item
($n$ in terms of $i$.)
$n = mi + 1$.
\item
($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 the root is the child of an internal vertex. \\
So $n$ is equal to $1$ plus the number of child vertices. \\
Claim there are exactly $mi$ child 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.
\item
Solve previous for $i$.
\end{enumerate}
\end{proof}

These exact results can be used to get inequalities for arbitrary
$m$-ary trees, for example:
\begin{enumerate}
\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$
\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}$.
\end{enumerate}
Proof: LTTR.

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

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/bst.eps,height=2in}}
\caption{\em A binary search tree}
\label{fig:bst}
\end{figure}

Fast for searching. \\
E.g. to see if $m$ 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 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)) \\
Ordered tree. \\
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/expr.eps,height=2in}}
\caption{\em Parse tree for above arithmetic expression}
\label{fig:expr}
\end{figure}

Example: More interesting program structure: \\
\begin{verbatim}
if x > y then while x <= 5 do x := x+1; a:= a^2
\end{verbatim}

This kind of tree is called a {\em parse tree}.  \\
It is produced during the compilation process, by a compiler program. \\
\\
Besides containing such structural information, it gets decorated with other
information, 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) \\
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/decision.eps,height=2.5in}}
\caption{\em Decision tree for sorting}
\label{fig:decision}
\end{figure}

Answers at bottom. \\
Height of tree corresponds closely to worst-case running time.

\end{document}

\endinput












