\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightnames}{Prof.~Abert~R.~Meyer}

\begin{document}
\lecturenotes{5}{Graphs}

As in Week 4 Notes, we'll refer to undirected graphs simply as ``graphs.''

\section{Counting by Degrees}

\subsection{Sex in America}

A 1994 University of Chicago study entitled \textit{The Social
Organization of Sexuality} found that on average men have 74\% more
opposite-gender partners than women, confirming a view that men are more
promiscuous.  But whoever reported this finding was lying or confused!
We'll show you how to use the properties of vertex degrees in a graph to
prove this.

Let's recast opposite-gender partnering in graph theoretic terms.  Let $G$
be a graph where the set of vertices $V$ consists of everyone in America.
Now each vertex either represents either a male or a female, so we can
partition $V$ into two subsets: $M$, which contains all the male vertices,
and $F$, which contains all the female vertices.  Let's draw all the $M$
vertices on the left and the $F$ vertices on the right:

\mfigure{!}{1.75in}{figures/sex-blankF}

\noindent Now, without getting into a lot of specifics,
\textit{sometimes an edge appears} between an $M$ vertex and a $F$
vertex:

\mfigure{!}{1.75in}{figures/sex-edgesF}

Since we're only considering opposite-gender relationships, every edge
connects an $M$ vertex on the left to a $F$ vertex on the right.  So the
sum of the degrees of the $M$ vertices equals the number of edges and so
does the sum of the degrees of the $F$ vertices.  So these sums are equal:
%
\[
\sum_{x \in M} \degr{x} = \sum_{y \in W} \degr{y}
\]
%
Now suppose we divide both sides of this equation by the product of
the sizes of the two sets, $\card{M} \cdot \card{F}$:
%
\[
\left(\frac{\sum_{x \in M} \degr{x}}{\card{M}}\right) \cdot \frac{1}{\card{F}} =
\left(\frac{\sum_{y \in W} \degr{y}}{\card{F}}\right) \cdot \frac{1}{\card{M}}
\]
%
The terms above in parentheses are the \textit{average degree of an
$M$ vertex} and the \textit{average degree of a $F$} vertex.  So we
know:
%
\begin{align*}
\frac{\text{Avg. deg in $M$}}{\card{F}} = 
\frac{\text{Avg. deg in $F$}}{\card{M}} \\
\text{Avg. deg in $M$} = \frac{\card{F}}{\card{M}} \cdot \text{Avg. deg in $F$}
\end{align*}

In other words, we've proved that the average number of opposite-gender
partners of males in the population compared to those of females is
determined solely by the relative number of males and females in the
population.

Now the Census Bureau reports that there are slightly more females than
males in America; in particular $\card{F} / \card{M}$ is about 1.035.  So
we know that on average, males have 3.5\% more opposite-gender partners
than females, and this tells us nothing about any sex's predilection
toward promiscuity.  We can only wonder where the University of Chicago
researchers got their 74\% difference.

\subsection{Handshaking Lemma}

The previous argument hinged on the connection between a sum of degrees
and the number edges.  There is a simple connection between these in any graph:

\begin{theorem}\label{sumedges}
The sum of the degrees of the vertices in a graph equals twice the number
of edges.
\end{theorem}

\begin{proof}
Every edge contributes two to the sum of the degrees, one for each of its
endpoints.
\end{proof}

Theorem~\ref{sumedges} is sometimes called the \emph{Handshake Theorem}:
if we total up the number of people each person at a party shakes hands
with, the total will be twice the number of handshakes that occurred.

\section{Connectedness}

\subsection{Paths and Simple Cycles}

Paths in graphs are defined in pretty much that same way as for digraphs,
but they are going to be particularly important, so let's define them
precisely.

\begin{definition}
Let $G$ be a graph with vertices, $V$, and edges, $E$.  A \emph{path} in
$G$ is a sequence of vertices
\[
v_0,\dots,v_k
\]
with $k \ge 0$ such that $\edge{v_i}{v_{i+1}}$ is an edge in $E$ for $0
\le i < k$.  The path is \emph{simple} iff all the $v_i$'s are different,
that is, $v_i = v_j$ only if $i=j$.

The path is said to \emph{start} at $v_0$, to \emph{end} at $v_k$, and
\emph{length} of the path is defined to be $k$.  An edge, $e$, is
\emph{traversed} $n$ times by the path if there are $n$ different values
of $i$ such that edge $\edge{v_i}{v_{i+1}}$ is $e$.
\end{definition}

For example, the graph in Figure~\ref{dg} has a length~6 simple path
A,B,C,D,E,F,G.  This is the longest simple path in the graph.

\begin{figure}[htbp] 
\mfigure{!}{1.75in}{figures/distance-graph}
\label{dg}
\caption{\em A graph with 3 simple cycles.}
\end{figure}

Notice that the {\em length} of a path is the total number of times it
traverses edges, which is \emph{one less} than its length as a sequence of
vertices.  The length~6 path A,B,C,D,E,F,G is actually a sequence of seven
vertices.

\emph{Cycles} are paths that begin and end with the same vertex, same as
for digraphs.  \emph{Simple} cycles will be cycles that don't cross
themselves.  For example, the graph in Figure~\ref{dg}
has three simple cycles B,H,E,C,B and C,D,E,C and B,C,D,E,H,B

A simple cycle is can be described by any of the paths that go around it.
For example, the path B,H,E,C,B describes the cycle as beginning and going
clockwise around to end at B, while the path E,H,B,C,E, describes the same
cycle as beginning and ending at E going counterclockwise.

To capture this precisely, we'll define a simple cycle to be a
\emph{subgraph} isomorphic to the simple cycle graph, $C_n$.  A subgraph
is obtained by restricting a graph to a subset of its vertices and then
possibly deleting some additional edges.  Formally:

\begin{definition}
A subgraph, $G'$, of a graph, $G$, is a graph whose vertices, $V'$, are a
nonempty subset of the vertices of $G$ and whose edges are a subset of the
edges of $G$.
\end{definition}
Notice that since a subgraph is itself a graph, the endpoints of every
edge of $G'$ must be vertices in $V'$.

\begin{definition}
For $n \ge 3$, let $C_n$ be the graph with vertices $1,\dots, n$ and
edges
\[
\edge{1}{2}, \edge{2}{3}, \dots, \edge{(n-1)}{n}, \edge{n}{1}.
\]
A graph, $C$, is a \emph{simple cycle of length} $n$ iff it is isomorphic
to $C_n$ for some $n \ge 3$.  A \emph{simple cycle of} a graph, $G$, is a
subgraph of $G$ that is a simple cycle.
\end{definition}

If we describe a simple cycle with a path around it, then the {\em length}
of a cycle is the number of times the path traverses an edge which is
\emph{the same} as the number of distinct vertices on the path.  For
example, the cycle with 5~vertices described by the path B,C,D,E,H,B has
length~5.

\subsection{Connected Components}

\begin{definition}
Two vertices in a graph are said to be \emph{connected} if there is a path
that begins at one and ends at the other.
\end{definition}

Now if there is a path from vertex $u$ to vertex $v$, then $v$ is
connected to $u$ by the reverse path, so connectedness is a symmetric
relation.  Also, if there is a path from $u$ to $v$, and also a path from
$v$ to $w$, then these two paths can be combined to form a path from $u$
to $w$.  So the connectedness relation is transitive.  It is also
reflexive, since every vertex is by definition connected to itself by a
path of length zero.  This proves;
\begin{lemma*}
Connectness is an equivalence relation on the vertices of any graph.
\end{lemma*}

The diagram in Figure~\ref{fig:3comp} looks like a picture of three
graphs, but is intended to be a picture of \emph{one} graph.  This graph
consists of three connected pieces, with no paths between vertices in
different pieces.

\iffalse
\begin{figure}[htbp]
\mfigure{!}{1.5in}{figures/3comp}
% \centerline{\psfig{figure=figures/3comp.eps,height=1.5in}}
\caption{\em A graph with 3 connected components.}
\label{fig:3comp}
\end{figure}
\fi

\begin{figure}[htbp] \label{fig:3comp}
\mfigure{!}{1.5in}{figures/connectivity-graphs}
\caption{\em A graph with 3 connected components.}
\end{figure}

\begin{definition}
A graph is said to be \term{connected} if every pair of vertices are
connected.
\end{definition}

These connected pieces of a graph are called its \term{connected
components}.  A rigorous definition is easy: a connected component is the
set of all the vertices connected to some single vertex.  That is, the
connected components of a graph are the \emph{equivalence classes} of its
connectedness relation.

So a graph is connected iff it has exactly one connected component.  The
empty graph on $n$ vertices has $n$ connected components.

\subsection{How Well Connected?}

If we think of a graph as modelling cables in a telephone network, or oil
pipelines, or electrical power lines, then we not only want connectivity,
but we want connectivity that survives component failure.  This lead us to
the following definition:
\begin{definition}
Two vertices in a graph are $k$-connected if they remain connected in any
subgraph obtained by deleting $k-1$ edges.  A graph is $k$-connected if
every pair of its vertices are $k$-connected.
\end{definition}
So 1-connected is the same as connected for both vertices and graphs.
Another way to say that a graph is $k$-connected is that every subgraph
obtained from it by deleting at most $k-1$ edges is connected.

For example, in the graph in Figure~\ref{dg}, vertices B and E are
2-connected, G and E are 1-connected, and no vertices are 3-connected.
The graph as a whole is only 1-connected.

More generally, any simple cycle is 2-connected, and the complete graph,
$K_n$, is $(n-1)$-connected.

If two vertices are connected by $k$ edge-disjoint paths (that is, no two
paths traverse the same edge), then they are obviously $k$-connected.  A
fundamental fact, whose ingenious proof we omit, is Menger's theorem which
confirms that the converse is also true: if two vertices are
$k$-connected, then there are $k$ edge-disjoint paths connecting them.  It
takes some ingenuity to prove even for the case $k=2$.


\subsection{Connection by Simple Path}

Where there's a path there's a simple path.  This is sort of obvious, but
proving it carefully provides a nice illustration of the Least Number
Principle.

\begin{lemma}\label{simplepath}
If vertex $u$ is connected to vertex $v$ in a graph, then there is a
simple path from $u$ to $v$.
\end{lemma}

\begin{proof}
Since there is a path from $u$ to $v$, there must, by the Least Number
Principle, be a minimum length path from $u$ to $v$.  If the minimum
length is zero or one, this minimum length path is itself a simple path
from $u$ to $v$.

Otherwise, there is a minimum length path
\[
v_0, v_1,\dots, v_k
\]
from $u = v_0$ to $v = v_k$ where $k \geq 2$.  We claim this path must be
simple.

To prove the claim, suppose to the contrary that the path is not simple,
that is, some vertex on the path occurs twice.  This means that there are
integers $i,j$ such that $0 \leq i < j \leq k$ with $v_i= v_j$.  Then deleting
the subsequence
\[
v_{i+1}, \dots v_j
\]
yields a strictly shorter path from $u$ to $v$, contradicting the
minimality of the given path.
\end{proof}

Actually, we proved something stronger:
\begin{corollary}\label{ss}
For any path of length $k$ in graph, there is a simple path 
of length \emph{at most} $k$ with the same endpoints.
\end{corollary}

\subsection{The Minimum Number of Edges in a Connected Graph}

The following theorem says that a graph with few edges must have many
connected components.  To be interesting, there must be fewer edges than
vertices.

\begin{theorem} \label{th:connectivity}
Every graph with $k$ vertices and $n$ edges has at least $k - n$ connected
components.
\end{theorem}

\begin{proof}
We use induction on the number of edges.  Let $P(n)$ be the proposition
that
\begin{quote}
for every $k$, every graph with $k$ vertices and $n$ edges has at least $k
- n$ connected components.
\end{quote}

\textbf{Base case:} In a graph with 0 edges and $k$ vertices, each vertex
is itself a connected component, and so there are exactly $k = k - 0$.
connected components.

\textbf{Inductive step:} Now we assume that the induction hypothesis holds
for every $n$-edge graph in order to prove that it holds for every
$(n+1)$-edge graph, where $n \geq 0$.

Consider a graph, $G$, with $n + 1$ edges and $k$ vertices.  We want to
prove that $G$ has at least $k - (n+1)$ connected components.

To do this, remove an arbitrary edge $\edge{u}{v}$ and call the resulting
graph $G'$.  By the induction assumption, $G'$ has at least $k - n$
connected components.

Now add back the edge $\edge{u}{v}$ to obtain the original graph $G$.  If
$u$ and $v$ were in the same connected component of $G'$, then $G$ has the
same connected components as $G'$, so $G$ has at least $k-n > k - (n+1)$
components.  Otherwise, if $u$ and $v$ were in different connected
components of $G'$, then these two components are merged into one in $G$,
but all other components remain unchanged, reducing the number of
components by 1.  Therefore, $G$ has at least $(k - n) - 1 = k - (n+1)$
connected components.

The theorem follows by induction.
\end{proof}

\begin{corollary}
\label{cor:n-1}
Every connected graph with $n$ vertices has at least $n - 1$ edges.
\end{corollary}

A couple of points about the proof of Theorem~\ref{th:connectivity} are
worth noting.  First, notice that we used induction on the number of edges
in the graph.  This is very common in proofs involving graphs, and so is
induction on the number of vertices.  When you're presented with a graph
problem, these two approachs should be among the first you consider.

The second point is more subtle.  Notice that in the inductive step, we
took an arbitrary $(n+1)$-edge graph, threw out an edge so that we could
apply the induction assumption, and then put the edge back.  You'll see
this shrink-down, grow-back process very often in the inductive steps of
proofs related to graphs.  This might seem like needless effort; why not
start with an $n$-edge graph and add one more to get an $(n+1)$-edge
graph?  That would work fine in this case, but opens the door to a very
nasty logical error in similar arguments.  You'll see an example in class.
Always use shrink-down, grow-back arguments, and you'll never fall into
this trap.



\section{Trees}

Trees are a fundamental data structure in Computer Science, and there are
many kinds, for example rooted, ordered, or binary trees.  In this section
we focus on the purest kind of tree.  Namely, we use the \term{tree} to
mean a connected graph without simple cycles.

A graph with no simple cycles is called \emph{acyclic}; so trees are
acyclic connected graphs.

\subsection{Tree Properties}
Here is an example of a tree:

\mfigure{!}{1.5in}{figures/tree-example}

A vertex of degree one is called a \term{leaf}.  In this example,
there are 5~leaves.

The graph shown above would no longer be a tree if any edge were removed,
because it would no longer be connected.  The graph would also not remain
a tree if any edge were added between two of its vertices, because then it
would contain a simple cycle.  Furthermore, note that there is a unique
path between every pair of vertices.  These features of the example tree
are actually common to all trees.

\begin{theorem}
Every tree has the following properties:
\begin{enumerate}
\item Any connected subgraph is a tree.
\item There is a unique simple path between every pair of vertices.
\item Adding an edge between two vertices creates a cycle.
\item Removing any edge disconnects the graph.
\item If it has at least two vertices, then it has at least two leaves.
\item The number of vertices is one larger than the number of edges.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}
\item\label{asub} A simple cycle in a subgraph is also a simple cycle in
the whole graph, so any subgraph of an acyclic graph must also be acyclic.
If the subgraph is also connected, then by definition, it is a tree.

\item There is at least one path, and hence one simple path, between every
pair of vertices, because the graph is connected.  Suppose that there are
two different simple paths between vertices $u$ and $v$.  Beginning at
$u$, let $x$ be the first vertex where the paths diverge, and let $y$ be
the next vertex they share.  Then there are two simple paths from $x$ to
$y$ with no common edges, which defines a simple cycle.  This is a
contradiction, since trees are acyclic.  Therefore, there is exactly one
simple path between every pair of vertices.

\mfigure{!}{1in}{figures/unique-path}

\item An additional edge $\edge{u}{v}$ together with the unique path
between $u$ and $v$ forms a simple cycle.

\item Suppose that we remove edge $\edge{u}{v}$.  Since a tree
contained a unique path between $u$ and $v$, that path must have been
$\edge{u}{v}$.  Therefore, when that edge is removed, no path remains,
and so the graph is not connected.

\item Let $v_1, \dots, v_m$ be the sequence of vertices on a longest
simple path in the tree.  Then $m \geq 2$, since a tree with two vertices
must contain at least one edge.  There cannot be an edge $\edge{v_1}{v_i}$
for $2 < i \leq m$; otherwise, vertices $v_1, \dots, v_i$ would from a
simple cycle.  Furthermore, there cannot be an edge $\edge{u}{v_1}$ where
$u$ is not on the path; otherwise, we could make the path longer.
Therefore, the only edge incident to $v_1$ is $\edge{v_1}{v_2}$, which
means that $v_1$ is a leaf.  By a symmetric argument, $v_m$ is a second
leaf.

\item We use induction on the number of vertices.  For a tree with a
single vertex, the claim holds since it has no edges and $0 + 1 = 1$.

Now suppose that the claim holds for all $n$-vertex trees and consider an
$(n+1)$-vertex tree, $T$.  Let $v$ be a leaf of the tree.

We will let the reader verify that deleting a vertex of degree 1 (and its
incident edge) from any connected graph leaves a connected subgraph.  So
by~\eqref{asub}, deleting $v$ and its incident edge gives a smaller tree,
and this smaller tree has one more vertex than edge by induction.  If we
reattach the vertex, $v$, and its incident edge, then the equation still
holds because the number of vertices and number of edges both increase by
1.  Thus, the claim holds for $T$ and, by induction, for all trees.
\end{enumerate}
\end{proof}

Various subsets of these properties provide alternative characterizations
of trees, though we won't prove this.  For example, a \emph{connected}
graph with a number of vertices one larger than it number of edges is
necessarily a tree.  Also, a graph with unique paths between every pair of
vertices is necessarily a tree.


\subsection{Spanning Trees}

Trees are everywhere.  In fact, every connected graph contains a a
subgraph that is a tree with the same vertices as the graph.  This is a
called a \term{spanning tree} for the graph.  For example, here is a
connected graph with a spanning tree highlighted.

\mfigure{!}{1.5in}{figures/spanning-tree}

\begin{theorem}
Every connected graph contains a spanning tree.
\end{theorem}

\begin{proof}
Let $T$ be a connected subgraph of $G$ with the smallest
number of edges.  We show that $T$ is acyclic by contradiction.  So
suppose that $T$ has a cycle with the following edges:
\[
\edge{v_0}{v_1}, \edge{v_1}{v_2}, \dots, \edge{v_n}{v_0}
\]
Suppose that we remove the last edge, $\edge{v_n}{v_0}$.  If a pair of
vertices $x$ and $y$ was joined by a path not containing
$\edge{v_n}{v_0}$, then they remain joined by that path.  On the other
hand, if $x$ and $y$ were joined by a path containing $\edge{v_n}{v_0}$,
then they remain joined by a path containing the remainder of the cycle.
This is a contradiction, since $T$ was defined to be a connected subgraph
of $G$ with the smallest number of edges.  Therefore, $T$ is acyclic.
\end{proof}


\iffalse

\subsection{Tree Variations}

Trees come up often in computer science.  For example, information is
often stored in tree-like data structures and the execution of many
recursive programs can be regarded as a traversal of a tree.

There are many varieties of trees.  For example, a \term{rooted tree}
is a tree with one vertex identified as the \term{root}.  Let
$\edge{u}{v}$ be an edge in a rooted tree such that $u$ is closer to
the root than $v$.  Then $u$ is the \term{parent} of $v$, and $v$ is
a \term{child} of $u$.

\mfigure{!}{1.5in}{figures/rooted-tree}

In the tree above, suppose that we regard vertex $A$ as the
root.  Then $E$ and $F$ are the children of $B$, and $A$ is the parent
of $B$, $C$, and $D$.

A \term{binary} tree is a rooted tree in which every vertex has at most
two children.  Here is an example, where the topmost vertex is the
root.

\mfigure{!}{1.5in}{figures/binary-tree}

In an \term{ordered, binary} tree, the children of a vertex $v$ are
distinguished.  One is called the \term{left child} of $v$, and the
other is called the \term{right child}.  For example, if we regard the
two binary trees below as unordered, then they are equivalent.
However, if we regard these trees as ordered, then they are different.

\mfigure{!}{1.5in}{figures/ordered-trees}
\fi



\iffalse
\section{Traversing a Graph}

Can you walk every hallway in the Museum of Fine Arts {\em exactly
once}?  If we represent hallways and intersections with edges and
vertices, then this reduces to a question about graphs.  For example,
could you visit every hallway exactly once in a museum with this
floorplan?

\mfigure{!}{1.5in}{figures/euler-tour}

\subsection{Euler Tours and Hamiltonian Cycles}

A \term{walk} in a graph $G$ is an alternating sequence of vertices and
edges of the form:
%
\[
v_0, \edge{v_0}{v_1}, v_1, \edge{v_1}{v_2}, v_2, 
\dots, 
v_{n-1}, \edge{v_{n-1}}{v_n}, v_n
\]
%
If $v_0 = v_n$, then the walk is \term{closed}.  Walks are
similar to paths.  However, a walk can cross itself, traverse the same
edge multiple times, etc.  There is a walk between two vertices if and
only if there is a path between the vertices.

The entire field of graph theory began when Euler asked whether the
seven bridges of K\"onigsberg could all be traversed exactly once---
essentially the same question we asked about the Museum of Fine Arts.  In
his honor, an \term{Euler walk} is a walk that contains every edge in
a graph exactly once.  Similarly, an \term{Euler tour} is an Euler
walk that starts and finishes at the same vertex; that is, $v_0 =
v_n$.  Graphs with Euler tours and Euler walks both have simple
characterizations.

\begin{theorem}
A graph has an Euler tour iff it is connected and every vertex has even
degree.
\end{theorem}

\begin{proof}
Suppose a graph has an Euler tour.  Every pair of vertices must appear in
the tour, so the graph is connected.  Moreover, a vertex visited $k$ times
by the tour must have degree $2k$, so every vertex of the graph has even
degree.

Conversely, suppose every vertex in a graph, $G$, has even degree.  Let
$W$ be the longest walk in $G$ that traverses every edge \textit{at most}
once:
%
\begin{align*}
W & = v_0, \edge{v_0}{v_1}, v_1, \edge{v_1}{v_2}, v_2, 
        \dots, 
        v_{n-1}, \edge{v_{n-1}}{v_n}, v_n
\end{align*}
%
The walk $W$ must traverse every edge incident to $v_n$; otherwise,
the walk could be extended.  In particular, the walk traverses two of
these edges each time it passes through $v_n$ and traverses
$\edge{v_{n-1}}{v_n}$ at the end of the walk.  This accounts for an
odd number of edges, but the degree of $v_n$ is even by assumption.
Therefore, the walk must also begin at $v_n$; that is, $v_0 = v_n$.

Suppose that $W$ is not an Euler tour.  Because $G$ is a connected
graph, we can find an edge not in $W$ but incident to some vertex in
$W$.  Call this edge $\edge{u}{v_i}$.  But then we can construct a
longer walk:
%
\[
u, \edge{u}{v_i}, v_i, \edge{v_i}{v_{i+1}}, 
\dots, 
\edge{v_{n-1}}{v_n}, v_n, \edge{v_0}{v_1}, 
\dots, 
\edge{v_{i-1}}{v_i}, v_i
\]
%
This contradicts the definition of $W$, so $W$ must be an
Euler tour after all.
\end{proof}

\begin{corollary}
A connected graph has an Euler walk if and only if either 0 or 2
vertices have odd degree.
\end{corollary}

\term{Hamiltonian cycles} are the unruly cousins of Euler tours.  A
\term{Hamiltonian cycle} is walk that starts and ends at the same
vertex and visits every \textit{vertex} in a graph exactly once.
There is no simple characterization of all graphs with a Hamiltonian
cycle.  (In fact, determining whether a given graph has a Hamiltonian
cycle is ``NP-complete''.)
\fi

\section{Coloring Graphs}

Each term, the MIT Schedules Office must assign a time slot for each
final exam.  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 to make the exam period as short as possible.

We can recast this scheduling problem as a question about coloring the
vertices of a graph.  Create a vertex for each course with a final
exam.  Put an edge between two vertices if some student is taking both
courses.  For example, the scheduling graph might look like this:

\mfigure{!}{1.5in}{figures/finals-uncolored}

Next, identify each time slot with a color.  For example,
Monday morning is red, Monday afternoon is blue, Tuesday morning is
green, etc.

Assigning an exam to a time slot is now equivalent to coloring the
corresponding vertex.  The main constraint is that adjacent vertices
must get different colors; otherwise, some student has two exams at
the same time.  Furthermore, in order to keep the exam period short,
we should try to color all the vertices using as few different colors
as possible.  For our example graph, three colors suffice:

\mfigure{!}{1.5in}{figures/finals-colored}

This coloring corresponds to giving one final on Monday
morning (red), two Monday afternoon (blue), and two Tuesday morning
(green).

\subsection{k-Coloring}

Many other resource allocation problems boil down to coloring some
graph.  In general, a graph $G$ is \term{$k$-colorable} if each vertex
can be assigned one of $k$ colors so that adjacent vertices get
different colors.  The smallest sufficient number of colors is called
the \term{chromatic number} of $G$.  The chromatic number of a graph is
generally difficult to compute, but the following theorem provides an
upper bound:

\begin{theorem}
A graph with maximum degree at most $k$ is $(k+1)$-colorable.
\end{theorem}

\begin{proof}
We use induction on the number of vertices in the graph, which we
denote by $n$.  Let $P(n)$ be the proposition that an $n$-vertex graph
with maximum degree at most $k$ is $(k+1)$-colorable.  A 1-vertex
graph has maximum degree 0 and is 1-colorable, so $P(1)$ is true.

Now assume that $P(n)$ is true, and let $G$ be an $(n+1)$-vertex graph
with maximum degree at most $k$.  Remove a vertex $v$ and its incident
edges, leaving an $n$-vertex graph $G'$.  The maximum degree of $G'$ is at
most $k$, and so $G'$ is $(k+1)$-colorable by our assumption $P(n)$.  Now
put back vertex $v$ and its incident edges.  We can assign $v$ a color
different from all adjacent vertices, since $v$ has degree at most $k$ and
$k+1$ colors are available.  Therefore, $G$ is $(k+1)$-colorable.  The
theorem follows by induction.
\end{proof}

\subsection{Bipartite Graphs}

The 2-colorable graphs are important enough to merit a special name;
they are called \term{bipartite graphs}.  Suppose that $G$ is
bipartite.  This means we can color every vertex in $G$ either black
or white so that adjacent vertices get different colors.  Then we can
put all the black vertices in a clump on the left and all the white
vertices in a clump on the right.  Since every edge joins
differently-colored vertices, every edge must run between the two
clumps.  Therefore, every bipartite graph looks something like this:

\mfigure{!}{2in}{figures/bipartite}

Bipartite graphs are both useful and common.  For example, every path,
every tree, and every even-length cycle is bipartite.  In turns out, in
fact, that every graph not containing an odd length cycle is bipartite and
vice verse.

\begin{theorem}
A graph is bipartite if and only if it contains no odd length cycle.
\end{theorem}

\iffalse

\section{The King Chicken Theorem}

There are $n$ chickens in a farmyard.  For each pair of distinct
chickens, either the first pecks the second or the second pecks the
first, but not both.  We say that chicken $u$ {\em virtually pecks}
chicken $v$ if either:

\begin{itemize}

\item Chicken $u$ pecks chicken $v$.

\item Chicken $u$ pecks some other chicken $w$ who in turn pecks
chicken $v$.

\end{itemize}

\noindent A chicken that virtually pecks every other chicken is called
a {\em king chicken}\footnote{But if a chicken is a king, isn't it
male?  And if it is male, isn't it a rooster?  Oh well.}.

We can model this situation with a tournament digraph.  The vertices
are chickens, and an edge $u \rightarrow v$ indicates that chicken $u$
pecks chicken $v$.  In the tournament below, three of the four
chickens are kings.
%
\begin{center}
\rotatebox{-90}{\includegraphics[height=2in]{lec11-graph3}}
\end{center}

Now we're going to prove a theorem about chicken tournaments.  The
result is not very useful, but the proof involves both induction and
digraphs, two of the most common mathematical tools in computer
science.

\begin{theorem}[King Chicken Theorem]
Every $n$-chicken tournament has a king, where $n \geq 1$.
\end{theorem}

\begin{proof}
The proof is by induction on $n$, the number of chickens in the
tournament.  Let $P(n)$ be the proposition that in every $n$-chicken
tournament, there is at least one king.

First, we prove $P(1)$.  In this case, we can safely say that the lone
chicken virtually pecks every other chicken, since there are no
others.  Therefore, the only chicken in the tournament is a king, and
so $P(1)$ is true.

Next, we must show that $P(n)$ implies $P(n+1)$ whenever $n \geq 1$.
Suppose there is a chicken tournament with chickens $v_1, \ldots,
v_{n+1}$.  If we ignore the last chicken for the moment, then we are
left with a tournament among the first $n$ chickens.  By our induction
hypothesis, $P(n)$, this tournament has a king chicken, $v_k$.

Let $D_1$ be the set of chickens pecked by the king, $v_k$.  Let $D_2$
be the set of chickens virtually pecked by the king, but not pecked
directly.  Thus, each chicken in $D_2$ was pecked by some chicken in
$D_1$.  Since $v_k$ is a king, this accounts for all the chickens;
that is, $\{ v_k \}$, $D_1$, and $D_2$ form a partition of the set of
chickens $\{ v_1, \ldots, v_n\}$.  The situation is represented
schematically below.
%
\begin{center}
\rotatebox{-90}{\includegraphics[height=2.25in]{lec11-king}}
\end{center}

Now we reintroduce the last chicken, $v_{n+1}$, and show that the full
tournament on $n+1$ chickens has a king.  There are two cases:

\begin{enumerate}

\item Suppose that $v_k$ pecks $v_{n+1}$.  Then $v_k$ is a king of the
full tournament.

\item Otherwise, $v_{n+1}$ pecks $v_k$.  There are then two subcases:

\begin{enumerate}

\item If some chicken in $D_1$ pecks $v_{n+1}$, then $v_k$ virtually
pecks $v_{n+1}$ and so $v_k$ is again a king of the full tournament.

\item Otherwise, $v_{n+1}$ pecks every chicken in $D_1$.  In this
case, $v_{n+1}$ is a king of the full tournament; he directly pecks
$v_k$ and all the chickens in $D_1$, and he virtually pecks all the
chickens in $D_2$.
\end{enumerate}
\end{enumerate}

\noindent In every case, a chicken tournament with $n+1$ chickens has
a king, and so $P(n+1)$ holds.  Thus, by the principle of induction,
the claim is proved.
\end{proof}
\fi

\section{Planar Graphs}

Here are three dogs and three houses.

\mfigure{!}{1.5in}{figures/dog-houses}

\noindent Can you find a path from each dog to each house such that no
two paths intersect?

A \textit{quadapus} is a little-known animal similar to an octopus,
but with four arms.  Here are five quadapi resting on the seafloor:

\mfigure{!}{1.5in}{figures/quadapi}

\noindent Can each quadapus simultaneously shake hands with every
other in such a way that no arms cross?

Informally, a \term{planar graph} is a graph that can be drawn in the
plane so that no edges cross.  Thus, these two puzzles are asking
whether the graphs below are planar; that is, whether they can be
redrawn so that no edges cross.

\mfigure{!}{1in}{figures/nonplanar}

\noindent In each case, the answer is, ``No--- but almost!''  In fact,
each drawing \textit{would} be possible if any single edge were
removed.

Planar graphs have applications in circuit layout and are helpful in
displaying graphical data, for example, program flow charts,
organizational charts, and scheduling conflicts.  We will use them to
prove a wonderful mathematical fact that was first proved by the ancient
Greeks.

\iffalse
One is rooted
in human pyschology: many kinds of information can be presented as a
graph (family relations, chemical structures, computer data
structures, contact data for study of disease spread, flow of cash in
money laundering trials, etc.).  Big graphs are typically
incomprehensible messes, but planar graphs are relatively easy for
humans to grasp since there are no crisscrossing edges.  Sometimes the
advantages of planarity are more concrete; for example, when wires are
arranged on a surface, like a circuit board or microchip, crossings
require troublesome three-dimensional structures.  When Steve Wozniak
designed the disk drive for the early Apple II computer, he struggled
mightly to achieve a nearly planar design:
%
\begin{quotation}
For two weeks, he worked late each night to make a satisfactory
design. When he was finished, he found that if he moved a connector he
could cut down on feedthroughs, making the board more reliable. To
make that move, however, he had to start over in his design. This time
it only took twenty hours. He then saw another feedthrough that could
be eliminated, and again started over on his design. "The final design
was generally recognized by computer engineers as brilliant and was by
engineering aesthetics beautiful. Woz later said, 'It's something you
can only do if you're the engineer and the PC board layout person
yourself. That was an artistic layout. The board has virtually no
feedthroughs.'"\footnote{From apple2history.org which in turn quotes
\textit{Fire in the Valley} by Freiberger and Swaine.}
\end{quotation}

Finally, as we'll see shortly, planar graphs reveal a fundamental
truth about the structure of our three-dimensional world.
\fi

\subsection{Euler's Formula}

A graph is planar if it has a \term{planar embedding} (or \term{drawing}).
This is a way of assigning each vertex to a distinct point in the plane
and each edge to a smooth, non-self-intersecting curve between the points
assigned to the vertices incident to the edge.  None of the curves may
``cross,'' no point other than a single common endpoint can appear on two
of the curves.

This unattractive definition hints at a theoretical problem associated
with planar graphs: while the idea seems intuitively simple, rigorous
arguments about planar graphs must start off with reasoning about regions
of the plane bounded by smooth curves.  We'll get around this simply by
\emph{assuming} a few intuitive properties of planar graphs.\footnote{A
way to avoid all these assumptions is described in an Appendix.}  To
start, we'll assume that a drawing of a planar graph divides the plane
into \term{faces}, connected regions bounded by edges of the graph.  For
example, the drawing below has four faces:

\mfigure{!}{1in}{figures/embedding}

Face 1, which extends off to infinity in all directions, is called the
\term{outside face}.  Notice that each edge that is on a cycle in a planar
graph serves as a boundary between two faces.

It turns out that the number of vertices and edges in a connected planar
graph determine the number of faces in every drawing:

\begin{theorem}[Euler's Formula]
For every drawing of a connected planar graph
%
\[
v - e + f = 2
\]
%
where $v$ is the number of vertices, $e$ is the number of edges, and
$f$ is the number of faces.
\end{theorem}

For example, in the drawing above, $\card{V} = 4$, $\card{E} = 6$, and
$f = 4$.  Sure enough, $4 - 6 + 4 = 2$, as Euler's Formula claims.

\begin{proof}
We use induction on the number of edges in the graph.  Let $P(e)$ be
the proposition that $v - e + f = 2$ for every drawing of a graph $G$
with $e$ edges.

\noindent \textit{Base case:} A connected graph with $e = 0$ edges has
$v = 1$ vertices, and every drawing of the graph has $f = 1$ faces
(the outside face).  Thus, $v - e + f = 1 - 0 + 1 = 2$, and so $P(0)$
is true.

\noindent \textit{Inductive step:} Now we assume that $P(e)$ is true
in order to prove $P(e+1)$ where $e \geq 0$.  Consider a connected
graph $G$ with $e + 1$ edges.  There are two cases:

\begin{enumerate}

\item If $G$ is acylic, then the graph is a tree.  Thus, there are $e
+ 2$ vertices and every drawing has only the outside face.  Since $(e
+ 2) - (e +1) + 1 = 2 - 1 + 1 = 2$, $P(n+1)$ is true.

\item Otherwise, $G$ has at least one cycle.  Select a spanning tree and
an edge $\edge{u}{v}$ in the cycle, but not in the tree.  (The spanning
tree can not contain all edges in the cycle, since trees are acyclic.)
Removing $\edge{u}{v}$ merges the two faces on either side of the edge and
leaves a graph $G'$ with only $e$ edges and some number of vertices $v$
and faces $f$.  Graph $G'$ is connected, because there is a path between
every pair of vertices within the spanning tree.  So $v - e + f = 2$ by
the induction assumption $P(e)$.  Thus, the original graph $G$ had $v$
vertices, $e + 1$ edges, and $f + 1$ faces.  Since $v - (e + 1) + (f + 1)
= v - e + f = 2$, $P(e+1)$ is again true.

\end{enumerate}

The theorem follows by the principle of induction.
\end{proof}

In this argument, we implicitly assumed two geometric facts: a drawing of
a tree has only one face, and removing an edge on a cycle merges two faces
into one.

\mfigure{!}{1in}{figures/planar-assumptions}

\subsection{Number of Edges versus Vertices}

\begin{lemma}\label{3v}
Suppose a connected, planar graph has $v > 2$ vertices, $e$ edges.
Then
\[
e \leq 3v-6.
\]
\end{lemma}

\begin{proof}
Suppose the graph is drawn in the plane with $f$ faces.  Every edge is
traversed exactly twice by the cycles that are the face boundaries, as
will be proved in a class problem.  So the sum of the length of the face
boundaries is exactly $2e$.  Also, when $v > 2$, each face boundary
traverses at least 3 edges, so this sum is at least $3f$.  So we have
\begin{equation}\label{e3f}
2e \geq 3f.
\end{equation}
But $f = e-v+2$ by Euler's formula, and substituting into~\eqref{e3f} gives
\begin{align*}
2e & \geq 3(e-v+2)\\
0 & \geq e-3v + 6\\
3v - 6 & \geq e
\end{align*}
\end{proof}

Euler's formula lets us prove that the quadapi can't all shake hands
without crossing.  Representing quadapi by vertices and the necessary
handshakes by edges, we get the complete graph, $K_5$.  Shaking hand
without crossing amounts to drawing $K_5$ in the plane.  But $K_5$ is
connected with 5 vertices and 10 edges, and $10 > 3 \cdot 5-6$, so
violates the condition of Lemma~\ref{3v} necessary for planarity.


\subsection{Classifying Polyhedra}

The Pythagoreans had two great mathematical secrets, the irrationality
of 2 and a geometric construct that we're about to rediscover!

A \term{polyhedron} is a convex, three-dimensional region bounded by a
finite number of polygonal faces.  If the faces are identical regular
polygons and an equal number of polygons meet at each corner, then the
polyhedron is \term{regular}.  Three examples of regular polyhedra are
shown below: the tetraheron, the cube, and the octahedron.

\mfigure{!}{1.25in}{figures/polyhedra}

How many more polyhedra are there?  Imagine putting your eye very
close to one face of a translucent polyhedron.  The edges of that face
would ring the periphery of your vision and all other edges would be
visible within.  For example, the three polyhedra above would look
something like this:

\mfigure{!}{1.25in}{figures/polyhedra-blowup}

Thus, we can regard the corners and edges of these polyhedra as the
vertices and edges of a planar graph.  (This is another logical leap
based on geometric intuition.)  This means Euler's formula for planar
graphs can help guide our search for regular polyhedra.

Let $m$ be the number of faces that meet at each corner of a
polyhedron, and let $n$ be the number of sides on each face.  In the
corresponding planar graph, there are $m$ edges incident to each of
the $v$ vertices.  Since each edge is incident to two vertices, we
know:
%
\[
m v = 2 e
\]
%
Also, each face is bounded by $n$ edges.  Since each edge is on the
boundary of two faces, we have:
%
\[
n f = 2 e
\]
%
Solving for $v$ and $f$ in these equations and then substituting into
Euler's formula gives:
%
\begin{gather*}
\frac{2e}{m} - e + \frac{2e}{n} = 2 \\
\frac{1}{m} + \frac{1}{n} = \frac{1}{e} + \frac{1}{2}
\end{gather*}
%
The last equation places strong restrictions on the structure of a
polyhedron.  Every nondegenerate polygon has at least 3 sides, so $n
\geq 3$.  And at least 3 polygons must meet to from a corner, so $m
\geq 3$.  On the other hand, if either $n$ or $m$ were 6 or more, then
the left side of the equation could be at most $\frac{1}{3} +
\frac{1}{6} = \frac{1}{2}$, which is less than the right side.
Checking the finitely-many cases that remain turns up five solutions.
For each valid combination of $n$ and $m$, we can compute the
associated number of vertices $v$, edges $e$, and faces $f$.
And polyhedra with these properties do actually exist:
%
\[
\begin{array}{cc|ccc|c}
n & m & v  & e  &  f & \text{polyhedron} \\ \hline
3 & 3 & 4  & 6  &  4 & \text{tetrahedron} \\
4 & 3 & 8  & 12 &  6 & \text{cube} \\
3 & 4 & 6  & 12 &  8 & \text{octahedron} \\
3 & 5 & 12 & 30 & 20 & \text{icosahedron} \\
5 & 3 & 20 & 30 & 12 & \text{dodecahedron}
\end{array}
\]
%
The last polyhedron in this list, the dodecahedron, was the other
great mathematical secret of the Pythagorean sect!

\section{Hall's Marriage Theorem}

A class contains some girls and some boys.  Each girl likes some boys
and does not like others.  Under what conditions can each girl be
paired up with a boy that she likes?

We can model the situation with a bipartite graph.  Create a vertex on
the left for each girl and a vertex on the right for each boy.  If a
girl likes a boy, put an edge between them.  For example, we might
obtain the following graph:

\mfigure{!}{2in}{figures/hall-graph}

In graph terms, our goal is to find a \term{matching} for the girls; that
is, a subset of edges such that exactly one edge is incident to each girl
and at most one edge is incident to each boy.  (If there or more boys than
girls, some boys won't be paired up, which means no edge is incident to
them.)  For example, here is one possible matching for the girls:

\mfigure{!}{2in}{figures/hall-graph-matched}

Hall's Marriage Theorem states necessary and sufficient conditions for the
existence of a matching in a bipartite graph.  It turns out to be a
remarkably useful mathematical tool.
\iffalse
, a hammer that bashes many problems.
Moreover, it is the tip of a conceptual iceberg, a special case of the
``max-flow, min-cut theorem'' which is in turn a byproduct of ``linear
programming duality,'' one of the central ideas of algorithmic theory.
\fi

We'll state and prove Hall's Theorem using girl-likes-boy terminology.
Define {\em the set of boys liked by a given set of girls} to consist
of all boys liked by at least one of those girls.  For example, the
set of boys liked by Martha and Jane consists of Tom, Michael, and
Mergatroid.

For us to have any chance at all of matching up the girls, the
following \term{marriage condition} must hold:

\bigskip
\centerline{{\em Every subset of girls likes at least as large a set of boys.}}
\bigskip

For example, we can not find a matching if some 4~girls
like only 3~boys.  Hall's Theorem says that this necessary
condition is actually sufficient; if the marriage condition holds,
then a matching exists.

\begin{theorem}
A matching for a set of girls $G$ with a set of boys $B$ can be found
if and only if the marriage condition holds.
\end{theorem}

\begin{proof}
First, let's suppose that a matching exists and show that the marriage
condition holds.  Consider an arbitrary subset of girls.  Each girl
likes at least the boy she is matched with.  Therefore, every subset
of girls likes at least as large a set of boys.  Thus, the marriage
condition holds.

Next, let's suppose that the marriage condition holds and show that a
matching exists.  We use strong induction on $\card{G}$, the number of
girls.  If $\card{G} = 1$, then the marriage condition implies that
the lone girl likes at least one boy, and so a matching exists.  Now
suppose that $\card{G} \geq 2$.  There are two possibilities:

\begin{enumerate}

\item Every proper subset of girls likes a {\em strictly larger} set of
boys.  In this case, we have some latitude: we pair an arbitrary girl
with a boy she likes and send them both away.  The marriage condition
still holds for the remaining boys and girls, so we can match the rest
of the girls by induction.

\item Some proper subset of girls $X \subset G$ likes an {\em equal-size}
set of boys $Y \subset B$.  We match the girls in $X$ with the boys in
$Y$ by induction and send them all away.  We will show that the
marriage condition holds for the remaining boys and girls, and so we
can match the rest of the girls by induction as well.

To that end, consider an arbitrary subset of the remaining girls $X'
\subseteq G - X$, and let $Y'$ be the set of remaining boys that they
like.  We must show that $\card{X'} \leq \card{Y'}$.  Originally, the
combined set of girls $X \cup X'$ liked the set of boys $Y \cup Y'$.
So, by the marriage condition, we know:
%
\[
\card{X \cup X'}  \leq  \card{Y \cup Y'}
\]
%
We sent away $\card{X}$ girls from the set on the left (leaving $X'$)
and sent away an equal number of boys from the set on the right
(leaving $Y'$).  Therefore, it must be that $\card{X'}
\leq \card{Y'}$ as claimed.

\end{enumerate}

In both cases, there is a matching for the girls.  The theorem follows
by induction.
\end{proof}

The proof of this theorem gives an algorithm for finding a matching in
a bipartite graph, albeit not a very efficient one.  However,
efficient algorithms for finding a matching in a bipartite graph do
exist.  Thus, if a problem can be reduced to finding a matching, the
problem is essentially solved from a computational perspective.

\subsection{A Formal Statement}

Let's restate Hall's Theorem in abstract terms so that you'll not
always be condemned to saying, ``Now this group of little girls likes
at least as many little boys...''  Suppose $S$ is a set of vertices in
a graph.  Define $N(S)$ to be the set of all neighbors of $S$; that
is, all vertices that are adjacent to a vertex in $S$, but not
actually in $S$.

\begin{theorem}[Hall's Theorem]
Let $G$ be a graph whose vertices can be partitioned into two sets, $L$ and
$R$, such that every edge has one endpoint in $L$ and one endpoint in $R$.
There is a matching for the $L$ vertices if and only if $\card{N(S)} \geq
\card{S}$ for every set $S \subseteq L$.
\end{theorem}

\appendix 

\section{Appendix: Drawing Planar Graphs}

\begin{optional}

A \emph{planar drawing script}, PDS for short, defines how to draw a
connected graph in the plane.  It specifies the order in which to draw the
edges, and, as each edge is drawn, which face of the current drawing that
the edge goes into.  It also specifies the one or two new faces that
result from drawing the edge.  This is illustrated in animated slides at
\begin{center}
\href{http://theory.csail.mit.edu/classes/6.042/fall05/planar-animation.pdf}
{\texttt{http://theory.csail.mit.edu/classes/6.042/fall05/planar-animation.pdf}}.
\end{center}
It's worth viewing these slides before trying to study the following
formal definitions.

Formally a PDS will consist of a sequence of distinct edges, and a set of
cycles called \emph{boundaries}.  Intuitively, the edges are listed in the
order in which they should be drawn in the plane, and the boundaries of
the PDS describe the successive vertices on the boundaries of each of the
faces of the planar drawing.

PDS's are officially defined recursively as follows:

\begin{enumerate}

\item A single edge $\edge{v}{w}$ is a PDS.  It has one boundary, namely
the length two cycle described by the path $v,w,v$.

\item (Attaching an edge with a new endpoint to a face.)  Suppose $S$ is a
PDS, and a boundary of $S$ is described by a path of the form $vxv$,
where $v$ is a vertex and $x$ is a positive length sequence of vertices.
If $w$ is a ``fresh'' vertex to which none of the edges of $S$ are
incident, then we can obtain another PDS, $T$, by adding edge
$\edge{v}{w}$ to the list of edges of $S$.  The boundaries of $T$ will be
the same as those of $S$, except that boundary described by $vxv$ is
replaced by a boundary described by the path $vxvwv$.  (Notice that two
traversals of the new edge are actually added to the cycle.)

\item (Attaching an edge between two vertices on a face.)  Suppose $S$ is
a PDS and the edge $\edge{v}{w}$ is not in the edge-list of $S$.  Also
suppose some boundary of $S$ is represented by a path of the form $vxwyv$,
where $x$ and $y$ are positive length sequences of vertices.  Then we can
obtain another PDS, $T$, by adding edge $\edge{v}{w}$ to the list of edges
of $S$.  The boundaries of $T$ will be the same as those of $S$, except
that boundary described by $vxwyv$ is replaced by two boundaries described
by the two paths $vxwv$ and $wyvw$.\footnote{There is one minor exception
to this rule.  If $vxwv$ and $wyvw$ turn out to be the same cycle, then
both ``copies'' of this cycle must be considered boundaries of $T$.
Technically, this means that the set of boundaries must be a ``multiset''
which can contain elements more than once.  But the only situation in
which this occurs is when there is when the graph is a simple cycle, $C_n$
whose embedding wil have two faces ---an ``inside'' face and an
``outside'' face ---that share the same boundary.  This exception is so
special that it is better handled in a footnote.}
\end{enumerate}

The \emph{graph of a PDS} is defined to be the graph whose edges are those
listed in the PDF and whose vertices are exactly those to which these
edges are incident.

There are a bunch of properties of any PDS that can be proved easily by
induction on the length of its edge-list.
\begin{lemma*}
\item No edge appears more than once in the edge-list.

\item Every boundary is a cycle that traverses only edges in the
edge-list.

\item Every edge in the edge-list is traversed exactly twice by one
boundary, or exactly once by each of two boundaries, and is not traversed
by any other boundaries.

\item If the graph of the PDS has 3 or more vertices, then every boundary
traverses at least three edges.

\item The graph of the PDS is connected.

\item If $e$ is the length of the edge-list, $v$ is the number of distinct
vertices to which these edges are incident, and $f$ is the number of
boundaries, then
\[
v-e+f = 2.
\]
\end{lemma*}

These properties support the intuitive claim that all connected planar
drawings are captured by PDS's.  We will accept this without proof:
\begin{theorem*}
A graph is connected and planar iff it is the graph of a PDS.
\end{theorem*}

PDS's are a data structure based only on the connection properties of a
graph, and they are nicely suited to proving planar properties by
induction without the need for any geometric facts or assumptions.
However, there are still some important properties of planarity that are
awkward to prove using PDS's.  An example is the fact noted earlier that
any subgraph of a planar graph is planar.

\end{optional}
\end{document}



