\hyperdef{connect}{edness}{\section{Connectedness}}

\subsection{Paths and Simple Cycles}

A \emph{path} in a graph describes how to get from one vertex to another
following edges of the graph.  Formally,

\begin{definition}
A \term{path} in a graph, $G$, is a sequence of $k \geq 0$ vertices
\[
v_0,\dots,v_k
\]
such that $\edge{v_i}{v_{i+1}}$ is an edge of $G$ for all $i$ where $0
\leq i < k$ .  The path is said to \term{start} at $v_0$, to \term{end} at
$v_k$, and \term{length} of the path is defined to be $k$.  An edge,
$\edge{u}{v}$, is \term{traversed $n$ times} by the path if there are $n$
different values of $i$ such that $\edge{v_i}{v_{i+1}} = \edge{u}{v}$.

The path is \term{simple}\footnote{Heads up if you read another graph
  theory text: what amounts to paths are commonly referred to as
  ``walks,'' and simple paths are referred to as a just ``paths''.
  Likewise, what we will call \emph{cycles} and \emph{simple cycles}
  are commonly called ``closed walks'' and just ``cycles''.}  iff all
the $v_i$'s are different, that is, $v_i = v_j$ only if $i=j$.

\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.pdf}
\caption{\em A graph with 3 simple cycles.}
\label{dg}
\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.

A \emph{cycle} can be described by a path \iffalse of length two or
more\fi that begins and ends with the same vertex.  For example,
B,C,D,E,C,B is a cycle in the graph in Figure~\ref{dg}.  This path
suggests that the cycle begins and ends at vertex B, but a cycle isn't
intended to have a beginning and end, and can be described by \emph{any}
of the paths that go around it.  For example, D,E,C,B,C,D describes this
same cycle as though it started and ended at D, and D,C,B,C,E,D describes
the same cycle as though it started and ended at D but went in the
opposite direction.  (By convention, a single vertex is a length 0 cycle
beginning and ending at the vertex.)

All the paths that describe the same cycle have the same length which is
defined to be the {\em length} of the cycle.  (Note that this implies that
going around the same cycle twice is considered to be different than going
around it once.)

A \emph{simple} cycle is a cycle that doesn't cross or backtrack on
itself.  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.  More precisely, a simple cycle is
a cycle that can be described by a path of length at least three whose
vertices are all different except for the beginning and end vertices.  So
in contrast to simple \emph{paths}, the length of a simple \emph{cycle} is
the \emph{same} as the number of distinct vertices that appear in it.

From now on we'll stop being picky about distinguishing a cycle from a
path that describes it, and we'll just refer to the path as a cycle.
\footnote{Technically speaking, we haven't ever defined what a cycle
\emph{is}, only how to describe it with paths.  But we won't need an
abstract definition of cycle, since all that matters about a cycle is which
paths describe it.}

\iffalse

Simple cycles are especially important, so we will give a proper
definition of them.  Namely, we'll define a simple cycle in $G$ to be a
\emph{subgraph} of $G$ that looks like a cycle that doesn't cross itself.
Formally:

\begin{definition}
A \term{subgraph}, $G'$, of a graph, $G$, is a graph whose vertices, $V'$,
are a 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}.
\]
 graph is a \term{simple cycle of length $n$} iff it is isomorphic to
$C_n$ for some $n \ge 3$.  A \term{simple cycle of a graph}, $G$, is a
subgraph of $G$ that is a simple cycle.
\end{definition}
\fi


\subsection{Connected Components}

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

By convention, every vertex is considered to be connected to itself by a
path of length zero.

\iffalse

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

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 pieces (subgraphs).  Each piece by itself is connected,
but there are no paths between vertices in different pieces.

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

\begin{figure}[htbp] 
\mfigure{!}{1.5in}{figures/connectivity-graphs.pdf}
\caption{\em One graph with 3 connected components.}
\label{fig:3comp}
\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.  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.  A graph is
called \emph{$k$-edge connected} if it remains connected as long as fewer
than $k$ ``direct connections between components fail,'' that is, it stays
connected even if as many as $k-1$ edges are deleted.  More precisely:
\begin{definition}
  Two vertices in a graph are \term{$k$-edge connected} if they remain
  connected in every subgraph obtained by deleting $k-1$ edges.  A graph
  with at least two vertices is $k$-edge connected\footnote{The
    corresponding definition of connectedness based on deleting vertices
    rather than edges is common in Graph Theory texts and is usually
    simply called ``$k$-connected'' rather than ``$k$-vertex connected.''}
  if every two of its vertices are $k$-edge connected.
\end{definition}
So 1-edge connected is the same as connected for both vertices and graphs.
Another way to say that a graph is $k$-edge 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-edge connected, G and E are 1-edge connected, and no vertices are 3-edge connected.
The graph as a whole is only 1-edge connected.

More generally, any simple cycle is 2-edge connected, and the complete graph,
$K_n$, is $(n-1)$-edge 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$-edge 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$-edge connected, then there are $k$ edge-disjoint paths connecting
them.  It takes some ingenuity to prove this 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
it's easy enough to prove rigorously using the Well-ordering 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 Well-ordering
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
\[
v_0, v_1,\dots, v_i,v_{j+1},v_{j+2},\dots, v_k
\]
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 a 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.

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

Of course for Theorem~\ref{th:connectivity} to be of any use, there must
be fewer edges than vertices.

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

\textbf{Base case:}($e=0$).  In a graph with 0 edges and $v$ vertices,
each vertex is itself a connected component, and so there are exactly $v =
v - 0$ connected components.  So $P(e)$ holds.

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

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

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

Now add back the edge $\edge{a}{b}$ to obtain the original graph $G$.  If
$a$ and $b$ were in the same connected component of $G'$, then $G$ has the
same connected components as $G'$, so $G$ has at least $v -e > v - (e+1)$
components.  Otherwise, if $a$ and $b$ 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 $(v - e) - 1 = v - (e+1)$
connected components.  So in either case, $P(e+1)$ holds.  This completes
the Induction step.

The theorem now follows by induction.
\end{proof}

\begin{corollary}
\label{cor:n-1}
Every connected graph with $v$ vertices has at least $v - 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 approaches 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 nasty
logical error called \emph{buildup} error, illustrated in
Problem~\ref{buildup}.\ below.
\iffalse You'll see an example in class.\fi
Always use shrink-down, grow-back arguments, and you'll never
fall into this trap.

%S08, cp6m, S06 cp5f

%S06 cp5f


\begin{notesproblem}\label{buildup}
\bparts

\ppart Give a counterexample to the
\begin{falseclm*}
If every vertex in a graph has positive degree, then the graph is
connected.
\end{falseclm*}

\solution{There are many counterexamples; here is one:

\mfigure{!}{0.75in}{figures/false-connect-cx.pdf}
}

\ppart Since the Claim is false, there must be an logical mistake in the
following bogus proof of it.  Pinpoint the first logical mistake
(unjustified step) in this proof.

\begin{bogusproof}
  We prove the Claim above by induction.  Let $P(n)$ be the proposition
  that if every vertex in an $n$-vertex graph has positive degree, then
  the graph is connected.

\textbf{Base cases}: ($n \leq 2$).  In a graph with 1 vertex, that vertex
cannot have positive degree, so $P(1)$ holds vacuously.

$P(2)$ holds because there is only one graph with two vertices of positive
degree, namely, the graph with an edge between the vertices, and this
graph is connected.

\textbf{Inductive step}: We must show that $P(n)$ implies
$P(n+1)$ for all $n \geq 2$.  Consider an $n$-vertex graph in which every
vertex has positive degree.  By the assumption $P(n)$, this graph is
connected; that is, there is a path between every pair of vertices.  Now
we add one more vertex $x$ to obtain an $(n+1)$-vertex graph:

\mfigure{!}{1.75in}{figures/false-connect-pic.pdf}

All that remains is to check that there is a path from $x$ to every other
vertex $z$.  Since $x$ has positive degree, there is an edge from $x$ to
some other vertex; call it $y$.  Thus, we can obtain a path from $x$ to
$z$ by adjoining the edge $\edge{x}{y}$ to the path from $y$ to $z$.  This
proves $P(n+1)$.

By the principle of induction $P(n)$ is true for all $n \geq 0$, which
proves the Claim.

\end{bogusproof}

\solution{This one is tricky: the proof is actually a good proof of
something else.  The first error in the proof is only in the final
statement of the inductive step: ``This proves $P(n+1)$''.

The issue is that to prove $P(n+1)$, \emph{every} $(n+1)$-vertex
positive-degree graph must be shown to be connected.  But the proof
doesn't show this.  Instead, it shows that every $(n+1)$-vertex
positive-degree graph \emph{that can be built up by adding a vertex of
positive degree to an $n$-vertex connected graph}, is connected.

The problem is that \emph{not every} $(n+1)$-vertex positive-degree graph
can be built up in this way.  The counterexample above illustrates this:
there is no way to build that 4-vertex positive-degree graph from a
3-vertex positive-degree graph.

More generally, this is an example of ``buildup error''.  This error
arises from a faulty assumption that every size $n+1$ graph with some
property can be ``built up'' in some particular way from a size $n$ graph
with the same property.  (This assumption is correct for some properties,
but incorrect for others--- such as the one in the argument above.)

One way to avoid an accidental build-up error is to use a ``shrink
down, grow back'' process in the inductive step: start with a size
$n+1$ graph, remove a vertex (or edge), apply the inductive hypothesis
$P(n)$ to the smaller graph, and then add back the vertex (or edge)
and argue that $P(n+1)$ holds.  Let's see what would have happened if
we'd tried to prove the claim above by this method:

\noindent \textit{Inductive step:} We must show that $P(n)$ implies
$P(n+1)$ for all $n \geq 1$.  Consider an $(n+1)$-vertex graph $G$ in
which every vertex has degree at least 1.  Remove an arbitrary vertex
$v$, leaving an $n$-vertex graph $G'$ in which every vertex has
degree... uh-oh!

The reduced graph $G'$ might contain a vertex of degree 0, making the
inductive hypothesis $P(n)$ inapplicable!  We are stuck--- and
properly so, since the claim is false!}

\eparts
\end{notesproblem}

\endinput
