\documentclass{article}%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Thursday, August 21, 2008 14:03:59}
%TCIDATA{LastRevised=Wednesday, September 17, 2014 10:53:13}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
%TCIDATA{Language=American English}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}

\title{Math 443/543 Graph Theory Notes 2: Transportation problems}
\author{David Glickenstein}
\maketitle

\section{Readings}

This is based on Chartrand Chapter 3 and Bondy-Murty 18.1, 18.3 (part on
Closure of a Graph).

\section{K\"{o}nigsberg bridge problem and Eulerian graphs}

See the figure for the graph corresponding to the K\"{o}nigsberg bridge
problem.%
%TCIMACRO{\FRAME{dtbpF}{2.6675in}{2.0033in}{0pt}{}{}{konigsberg2.wmf}%
%{\special{ language "Scientific Word";  type "GRAPHIC";
%maintain-aspect-ratio TRUE;  display "USEDEF";  valid_file "F";
%width 2.6675in;  height 2.0033in;  depth 0pt;  original-width 9.5998in;
%original-height 7.1996in;  cropleft "0";  croptop "1";  cropright "1";
%cropbottom "0";  filename 'pics/Konigsberg2.wmf';file-properties "XNPEU";}} }%
%BeginExpansion
\begin{center}
\includegraphics[
natheight=7.199600in,
natwidth=9.599800in,
height=2.0033in,
width=2.6675in
]%
{pics/Konigsberg2.wmf}%
\end{center}
%EndExpansion
The problem is whether one can traverse each edge exactly once.

Here is the answer: No.

Here is the argument. We must start and stop at one of the vertices (possibly
the same one). In particular, there must be at least one of the vertices B,C,D
of degree three which is neither the start nor the stop point. Since it has
degree three, the walker can enter along one edge (the walker does not start
there) then leave by a second edge, then return by the last edge. Then the
walker cannot move again. However, since this means the walker must stop
there, we have a contradiction with the fact that we do not stop at that vertex.

\begin{definition}
An \emph{eulerian circuit} (or eulerian tour) is a circuit containing all of
the edges and vertices of the (multi-)graph. An \emph{eulerian trail} is trail
containing all of the edges and vertices of the (multi-)graph. A graph which
contains an eulerian circuit is called an \emph{eulerian graph} and a graph
containing an eulerian trail that is not also a circuit is called a
\emph{traversable graph}.
\end{definition}

Recall that circuits and trails traverse each edge only once (but may traverse
vertices any number of times). \newline We can characterize both eulerian
circuits and trails:

\begin{theorem}
A (multi-)graph is eulerian if and only if it is connected and every vertex
has even degree. A (multi-)graph is traversable if and only if it is connected
and exactly two vertices have odd degree.
\end{theorem}

\begin{proof}
The two statements are proven almost the same way, so we only prove the first
statement. If a graph $G$ is eulerian, then it contains an eulerian circuit
$C$ which begins and ends at a vertex $v\in V\left(  G\right)  .$ Since the
circuit contains all vertices, there is a trail that connects any two vertices
(a subset of the circuit $C$), and hence a path (by removing repeated
occurrences of any vertices). Thus $G$ is connected. Now consider a vertex
$u\neq v.$ Since the circuit neither begins nor ends at $u,$ each time $u$ is
traversed, there must be an edge entering and an edge exiting. Thus the edges
occur in pairs for each time the circuit visits $u$ and $u$ must have even
degree. For the vertex $v,$ every time it is visited other than the first and
last time, there must be an edge entering and an edge exiting. Add to this one
for the initial edge leaving and one for the last edge entering, $v$ must have
even degree too. (Note how this is changed for the second statement in the theorem).

For the converse, we must show that an eulerian circuit exists if the graph
$G$ is connected and every vertex has an even degree. Pick an initial vertex
$v$ and begin constructing a trail $T$ until it can no longer be extended. The
trail $T$ must be a circuit (i.e., end at $v$) since if it ended at any other
vertex, that vertex would have odd degree since it has entered and exited an
even number of times and then finally entered with nowhere to go. Since all
vertices have even degree, $T$ is a circuit. Now we must extend $T$ to be
eulerian, i.e., to traverse all of the edges. Consider the graph $G^{\prime}$
gotten by removing the edges in the circuit $T.$ Notice that $G^{\prime}$ also
has the property that each vertex has even degree. If there are no edges in
$G^{\prime},$ then $T$ is eulerian. Otherwise, there must be an edge connected
to a vertex $v^{\prime}$ which is covered by $T$ (since $G$ is connected). We
may now construct a new circuit $T^{\prime}$ in the same way, beginning and
ending at $v^{\prime}.$ Furthermore, we may append $T^{\prime}$ to the trail
$T$ to get a new circuit $T^{\prime\prime}$ which covers more edges. We may
then continue the procedure of removing the edges of $T^{\prime\prime}$ in $G$
until we get an eulerian circuit. We know this procedure will terminate since
we are always adding edges to the trail $T$ and their are a finite number of
edges in $G.$
\end{proof}

Example 3.2 gives an interesting application of eulerian graphs.

Also note that the proof gives an algorithm for finding eulerian circuits and trails.

\section{Salesman problem and hamiltonian graphs}

The traveling salesman problem is the following:

A salesman has to visit each city in his territory. The cities are connected
by certain highways (or even by certain plane routes). Is it possible to plan
a round trip so that he visits each city exactly once?

\begin{definition}
A cycle containing all of the vertices of $G$ is called a \emph{hamiltonian
cycle}. A graph containing a hamiltonian cycle is called a \emph{hamiltonian
graph}.
\end{definition}

It turns out that the problem of finding a hamiltonian cycle is NP-complete,
which essentially means it is quite difficult. First, here is a condition
satisfied by a hamiltonian graph:

\begin{theorem}
If $G$ is a hamiltonian graph, then for any nonempty, proper subset $S\subset
V\left(  G\right)  ,$ $G-S$ has at most $\left\vert S\right\vert $ components.
\end{theorem}

\begin{proof}
Let $\omega\left(  G\right)  $ denote the number of components of $G.$ We know
$G$ contains a hamiltonian cycle $C,$ and for a cycle, we have that
\[
\omega\left(  C-S\right)  \leq\left\vert S\right\vert ,
\]
since removing one vertex leaves it connected, removing a second produces two
components, removing a third produces another component, etc. However, since
$C$ is a subgraph of $G$ which contains all of the vertices of $G,$ we see
that
\[
\omega\left(  G-S\right)  \leq\omega\left(  C-S\right)
\]
(since $G-S=C-S$ union some edges).
\end{proof}

Example: Show this graph is not hamiltonian (From BM):%

%TCIMACRO{\FRAME{dtbpF}{4.1594in}{3.1233in}{0pt}{}{}{graph3-3.wmf}%
%{\special{ language "Scientific Word";  type "GRAPHIC";
%maintain-aspect-ratio TRUE;  display "USEDEF";  valid_file "F";
%width 4.1594in;  height 3.1233in;  depth 0pt;  original-width 9.5998in;
%original-height 7.1996in;  cropleft "0";  croptop "1";  cropright "1";
%cropbottom "0";  filename 'pics/graph3-3.wmf';file-properties "XNPEU";}}}%
%BeginExpansion
\begin{center}
\includegraphics[
natheight=7.199600in,
natwidth=9.599800in,
height=3.1233in,
width=4.1594in
]%
{pics/graph3-3.wmf}%
\end{center}
%EndExpansion


We give one sufficient condition for a graph to be hamiltonian.

\begin{theorem}
Suppose $G$ is a graph of order $p\geq3$ such that $\deg v\geq p/2$ for every
$v\in V\left(  G\right)  .$ Then $G$ is hamiltonian.
\end{theorem}

Note that this is certainly not necessary, since we may consider a simple
cycle, in which ever vertex has degree 2 but it is certainly hamiltonian.

\begin{proof}
If $p=3,$ then every vertex has degree larger than $3/2,$ so $G$ is the
complete graph (a triangle) and that is hamiltonian. Now assume $p\geq4.$ Let
$P=u_{0},u_{1},\ldots,u_{k}$ be a path which visits the most vertices (there
may be several of these paths, but all visit the same number of vertices). We
notice the following:

\begin{enumerate}
\item All vertices adjacent to $u_{0}$ must be in $P,$ since otherwise we
could make $P$ larger. The same is true for $u_{k}.$

\item The path must have $k+1\geq p/2+1$ since $\deg u_{0}\geq p/2.$

\item There exists a number $i,$ $1\leq i\leq k,$ such that $u_{0}$ is
adjacent to $u_{i}$ and $u_{k}$ is adjacent to $u_{i-1}.$ Suppose this were
not the case, then for each $u_{i}$ adjacent to $u_{0}$ (there are at least
$p/2$ of these), there is another vertex not adjacent to $u_{k},$ which means
there are $p/2+1$ vertices (including $u_{k}$) not adjacent to $u_{k}.$
However, this is impossible since it would mean that $\deg u_{k}\leq p-\left(
p/2+1\right)  <p/2.$

\item Thus there is a cycle $C=u_{0},u_{i},u_{i+1},\ldots,u_{k},u_{i-1}%
,u_{i-2},\ldots,u_{0}.$
\end{enumerate}

\noindent We claim that $C$ is hamiltonian. Suppose that $v\in V\left(
G\right)  $ is not in $C.$ We know that $v$ is not connected to any vertex on
$C$ since if it were, then we would have a path longer than $P$ (using the
cycle $C$). Thus $v$ is not connected to $1+p/2$ of the vertices, which means
that $\deg v\leq p-\left(  p/2+1\right)  <p/2.$ A contradiction.
\end{proof}

Notice that we only used in step 3 that $\deg u_{k}+\deg u_{0}\geq p.$ Here is
an analogue:

\begin{lemma}
\label{lemma add graph}Suppose $G$ is a $\left(  p,q\right)  $-graph (NOT
multi-graph) such and $u,v\in V\left(  G\right)  $ are nonadjacent and $\deg
u+\deg v\geq p.$ Then $G$ is hamiltonian if and only if $G+uv$ is hamiltonian.
\end{lemma}

\begin{proof}
[Proof (Sketch)]Certainly if $G$ is hamiltonian, so is $G+uv.$ If $G+uv$ is
hamiltonian, then we take a hamiltonian cycle $C.$ If $C$ does not contain
$uv,$ we are done. If $C$ does, then there is a path $P$ from $u=u_{0}$ to
$v=u_{k}$ in $G$ as in the proof of the theorem above. We can turn this into a
cycle in the same way as above, and it must be hamiltonian.
\end{proof}

This motivates the following definition:

\begin{definition}
The closure of a $\left(  p,q\right)  $-graph $G,$ denoted $c\left(  G\right)
,$ is the graph obtained by recursively joining vertices $u,v\in V\left(
G\right)  $ which satisfy $\deg u+\deg v\geq p$ until all such pairs are
joined by an edge.
\end{definition}

\begin{proposition}
$c\left(  G\right)  $ is well defined, i.e., if we had joined vertices in
another order, then we obtain the same graph.
\end{proposition}

\begin{proof}
Let $G_{1}$ and $G_{2}$ be two graphs obtained from $G$ as in the definition
of the closure. Say $G_{1}$ is gotten by adding edges $\left\{  e_{1}%
,e_{2},\ldots,e_{n}\right\}  $ in that order. Let $e_{k+1}=uv$ be the first
such edge which is not in $G_{2}$ (if one exists). Then the graph
$H=G+e_{1}+\cdots+e_{k}$ must be a subgraph of $G_{2}.$ By the way we defined
$G_{1},$ we must have that
\[
\deg_{H}u+\deg_{H}v\geq p.
\]
However, since $H$ is a subgraph of $G_{2},$ we must have
\begin{align*}
\deg_{H}u  &  \leq\deg_{G_{2}}u\\
\deg_{H}v  &  \leq\deg_{G_{2}}v
\end{align*}
and thus
\[
\deg_{G_{2}}u+\deg_{G_{2}}v\geq p.
\]
However, this is a contradiction, since $G_{2}$ contains no such pairs of
vertices. Thus every edge in $G_{1}$ is in $G_{2}.$ A similar argument shows
that $G_{2}$ is in $G_{1}$ and so $G_{1}=G_{2}.$
\end{proof}

We now get another condition for a graph to be hamiltonian.

\begin{theorem}
A graph $G$ is hamiltonian if and only if $c\left(  G\right)  $ is hamiltonian.
\end{theorem}

\begin{proof}
Apply Lemma \ref{lemma add graph} each time an edge is added to construct the closure.
\end{proof}

\begin{corollary}
A graph with at least 3 vertices is hamiltonian if its closure is complete.
\end{corollary}

Show the following is a hamiltonian graph.%
%TCIMACRO{\FRAME{dtbpF}{3.5425in}{2.66in}{0pt}{}{}{graph4-2.wmf}%
%{\special{ language "Scientific Word";  type "GRAPHIC";
%maintain-aspect-ratio TRUE;  display "USEDEF";  valid_file "F";
%width 3.5425in;  height 2.66in;  depth 0pt;  original-width 9.5998in;
%original-height 7.1996in;  cropleft "0";  croptop "1";  cropright "1";
%cropbottom "0";  filename 'pics/graph4-2.wmf';file-properties "XNPEU";}}}%
%BeginExpansion
\begin{center}
\includegraphics[
natheight=7.199600in,
natwidth=9.599800in,
height=2.66in,
width=3.5425in
]%
{pics/graph4-2.wmf}%
\end{center}
%EndExpansion



\end{document}