\documentclass{article}
\usepackage{amsmath}
\usepackage[dvipdfm]{graphicx}
\usepackage[dvipdfm,designi,tight]{web} % dvipsone, dvips, pdftex, dvipdfm
\usepackage{exerquiz}
\title{Introduction to Graph Theory}
\author{J. E. Fields}
\subject{Graph Theory}
\keywords{}
\university{Southern Connecticut State University\\
Department of Mathematics}
\email{fields@southernct.edu}
\version{1.0}
\copyrightyears{2001-2003}
\marginsize{1in}{1in}{1in}{1in}
\screensize{8.5in}{11in}
\newcounter{probno}[section]
\renewcommand{\theprobno}{\thesection.\arabic{probno}}
%
% Define a problem environment with its own counter.
\newenvironment{problem}{%
\renewcommand\exlabel{Problem}
\renewcommand\exlabelformat{\textbf{\exlabel\ \theprobno.}}
\renewcommand\exsllabelformat
{\noexpand\textbf{\exlabel\ \theprobno.}}
\renewcommand\exrtnlabelformat{$\blacktriangleleft$}
\renewcommand\exsecrunhead{Solutions to Problems}
\begin{exercise}[probno]}
{\end{exercise}}
% Define an example environment with no counter
\newenvironment{example}{%
\renewcommand\exlabel{Example}
\renewcommand\exlabelformat{\textbf{\exlabel.}}
\renewcommand\exrtnlabelformat{$\square$}
\SolutionsAfter
\begin{exercise}[0]}%
{\end{exercise}}
\begin{document}
\maketitle
\tableofcontents
\listoffigures
\newpage
\section{Introduction}
A {\em graph} is a mathematical object that captures
the notion of connection. Most people are familiar
with the children's puzzle of trying to connect 3 utilites
(water, telephone and electricity) to 3 houses without
having any of the ``wires'' cross. See Figure~\ref{f:3_utils}.
\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale=.5]{3_utils.eps}
\end{center}
\caption{The 3 utilities problem.} \label{f:3_utils}
\end{figure}
A somewhat less familiar, but actually more germaine example
(this is widely thought to be how graph theory originated)
is found in a puzzle that was posed by the townsfolk of
K\"{o}nigsberg, Prussia in the early 1700's. K\"{o}nigsberg
(now known as Kaliningrad) was built largely on an island
in the Pregel river, this island sits near where two branches
of the river join, and the borders of the town spread over
to the banks of the river as well as a nearby promontory.
Between these four land masses, seven bridges had been
erected. See Figure~\ref{f:kon}.
\begin{figure}[!hbtp]
\includegraphics[scale=.4]{konigsberg.eps}
\caption[K\"{o}nigsberg]{The town of K\"{o}nigsberg and its seven
bridges.}
\label{f:kon}
\end{figure}
The townspeople supposedly posed the question ``Is it possible
to take a walk through town, crossing each of the seven bridges
just once, and ending up wherever you started?''
The famous swiss mathematician Leonhard Euler (pronounced ``Oiler'')
heard of the problem, solved it (it's not possible) and in the
process invented Graph Theory.
Since the question involved the connection of land masses by
bridges, Euler realized that all the points on the island
(for example) were equivalent as far the question was concerned,
so the island as well as the banks and the promontory could
be represented with single points. In Figure~\ref{f:graph}
we see what K\"{o}nigsberg and its bridges look like in
Euler's abstracted version.
\begin{figure}[!hbtp]
\begin{center}
\includegraphics{kon_graph.eps}
\end{center}
\caption[K\"{o}nigsberg as a graph]{The graph that corresponds to
K\"{o}nigsberg and its seven bridges.} \label{f:graph}
\end{figure}
\clearpage
\section{Notation}
To formalize our discussion of graph theory, we'll need to
introduce some terminology.
A graph $G$ is a pair of sets $V$ and $E$ together with a
function $f:E \mapsto V\times V$. The elements of $V$ are the
{\em vertices} (a.k.a. nodes or points) of $G$. The elements
of $E$ are the {\em edges} of $G$. The function $f$ sends an
edge to the pair of vertices that are its endpoints, thus
$f$ is known as the {\em edge--endpoint function}. This
terminology is unfortunate since $f$ is generally only a relation.
Informally, we usually forget about the edge--endpoint function and
simply identify $E$ with a sub-multiset of $V\times V$. We
need to think of $E$ as a sub-multiset because there may be more than
one edge between a given pair of vertices.
Connections generally come in two forms,
those that are non-directional (e.g. the bridges of K\"{o}nigsberg)
and those that have an implicit direction (e.g. the utility
hookups -- water flows from the utility {\em to} one's home,
not vice versa). To distinguish these two cases we really
need to define two different kinds of graphs. We will use
the term {\em graph} to indicate a graph where the connections
are non-directional -- if we need to really emphasize this
point we might say {\em ordinary graph} or {\em undirected graph}.
For situations in which
the connections are directional, we use the term {\em digraph} --
a contraction of {\em directed graph}. Note that in our original
definition, the codomain of the edge--endpoint function was the
set $V\times V$ of ordered pairs of vertices, or, equivalently
in the informal version, we think of $E$ as consisting of a
sub-multiset of these ordered pairs. Now we can explain the
comment that $f$ is only a relation. Suppose $e_k$ is an
edge in an ordinary graph that connects vertices $v_i$ and
$v_j$, then {\em both} of the ordered pairs $(v_i,v_j)$ and
$(v_j,v_i)$ should be images of $e_k$ under $f$ -- i.e. $f$ is
many-valued.
The problem discussed in the previous paragraph {\em could} be assuaged
by making the codomain of $f$ be the set of all 2-subsets of $V$,
but this introduces its own problem: shouldn't it be possible for
a vertex to be connected to itself? The answer is that for some
problem types one would like to have graphs that allow for the
possibility of a vertex being connected to itself. Such edges
are called {\em loops} in the graph $G$ and while $(v_i,v_i)$ is
an element of $V\times V$, it is not true that $\{v_i,v_i\}$
is a 2-subset of $V$.
The most general definition for an ordinary graph would be to identify
$E$ with a sub-multiset of the set of all 2-sub-multisets of $V$
(multisets containing either 2 distinct elements of $V$ or 2 copies of
the same element). In practice, such a high level of correctness is
not necessary.
In many applications, one deals with graphs that have neither
loops nor multiple copies of the same edge (these are known
as {\em parallel edges}). Such graphs are
called {\em simple graphs}.
All in all, there are four types of graphs we'd like to distinguish.
\begin{enumerate}
\item Graphs (no restrictions on loops and parallel edges)
\item Simple graphs (may {\em not} have loops or parallel edges)
\item Digraphs (no restrictions)
\item Simple digraphs (no loops, no parallel edges)
\end{enumerate}
Note that in a simple digraph edges that run between the
same vertices but in opposite directions are not considered
parallel.
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=1]{ns_graph.eps}
\end{center}
\caption[Undirected graph]{An undirected graph without restrictions. %
Graphs such as this may have loops and parallel edges. } \label{f:ns_graph}
\end{figure}
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=1]{und_graph.eps}
\end{center}
\caption[Simple undirected graph]{A simple undirected graph. %
Graphs of this type may not have loops or parallel edges. } \label{f:und_graph}
\end{figure}
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=1]{ns_digraph.eps}
\end{center}
\caption[Directed graph]{A non-simple directed graph.} \label{f:ns_digraph}
\end{figure}
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=1]{digraph.eps}
\end{center}
\caption[Simple directed graph]{A simple directed graph. Note %
that edges having the same endpoints but going in opposite directions %
are allowed.} \label{f:digraph}
\end{figure}
\clearpage
\begin{quiz}*{qz:graph-l} Answer each of the following.
\begin{questions}
\item Can there be edges having the same endpoints
in a simple digraph?
\begin{answers}2
\Ans1 Yes &\Ans0 No
\end{answers}
\item Can there be edges having the same endpoints
in a simple (undirected) graph?
\begin{answers}2
\Ans0 Yes &\Ans1 No
\end{answers}
\end{questions}
\end{quiz}\quad\ScoreField{qz:graph-l}\eqButton{qz:graph-l}
\noindent
Answers: \AnswerField{qz:graph-l}
\newpage
\section{A compendium of graphs}
Certain graphs occur frequently enough that they deserve names.
A {\em complete graph} on $n$ vertices is a simple (undirected)
graph having the
maximum possible number of edges. Complete graphs are denoted $K_n$
(probably because complete is spelled with a `K' in German). The
complete graphs on 1 through 5 vertices are shown in
Figure~\ref{f:K_n}.
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=.5]{complete_graphs.eps}
\end{center}
\caption[Some complete graphs]{The complete graphs $K_n$ for $1 \leq n
\leq 5$.} \label{f:K_n}
\end{figure}
\clearpage
\begin{quiz}*{qz:graph-2} Answer each of the following.
\begin{questions}
\item How many edges are there in a complete graph on 5 vertices?
\begin{answers}4
\Ans0 none & \Ans0 5 & \Ans1 10 & \Ans0 all
\end{answers}
\item Are there parallel edges in a complete graph?
\begin{answers}2
\Ans0 Yes &\Ans1 No
\end{answers}
\item
How many edges are there in general in a complete graph that
has $x$ vertices? \newline
\RespBox{x*(x-1)/2}{4}{.001}01\hfill
%\CorrAnsButton{x*(x-1)/2}%\kern1bp\sqTallyBox
\end{questions}
\end{quiz}\quad\ScoreField{qz:graph-2}\eqButton{qz:graph-2}
\newpage
In certain situations, graphs which have connections
that only go between 2 ``clumps'' of vertices are studied.
For example, a famous problem in discrete math is the
assignment problem in which workmen are assigned to
operate machines. Each person can only competently
operate some subset of the machines. There is a graph that
is used in solving the problem, the vertices fall into
2 groups, the people and the machines -- edges are placed between
a person and the machines s/he can operate.
A more whimsical version of this problem is known as the
``Marriage problem'' -- in a small town, there are several
young women and young men of the appropriate age to marry.
Each woman has a list of men who she would find acceptable as a
spouse. Is it possible for a matchmaker to pair-up these
people so that each women gets a husband she finds acceptable?
Graphs such as those involved in the assignment problem
are called bipartite. A graph $G$ is {\em bipartite}
if there is a partition of $V(G)$ into two disjoint
sets and there are no edges such that both of their endpoints
are in one of these sets.
A {\em complete bipartite graph} is a bipartite graph having
the maximum possible number of edges. Complete bipartite
graphs are denoted $K_{m,n}$ where $m$ and $n$ are the sizes
of the sets in the partition. Some complete bipartite graphs
are shown in Figure~\ref{f:K_mn}.
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=.75]{complete_bipartite.eps}
\end{center}
\caption[Some complete bipartite graphs]{The complete bipartite %
graphs $K_{3,3}$ and $K_{2,4}$.} \label{f:K_mn}
\end{figure}
\clearpage
Another interesting family of graphs consists of $n$ dimensional
hypercubes. In two dimensions, this means a square. In three
dimensions, an ordinary cube. The ``hyper'' prefix only becomes
appropriate in dimension greater than 3. This family of graphs
is defined recursively. To make a $n$-dimensional hypercube,
take two copies of an $n-1$-dimensional hypercube and connect
corresponding vertices in the copies. See Figure~\ref{f:hypercubes}.
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=.5]{hypercubes.eps}
\end{center}
\caption[Hypercube graphs]{The first several hyercubes -- dimensions %
1 through 4.} \label{f:hypercubes}
\end{figure}
\clearpage
Our finally example of a ``named'' graph is the Petersen graph.
This graph is interesting for many reasons, one of which is the way
it can be constructed from another graph. Consider the complete
graph $K_5$ which has 10 edges. The vertices of the Petersen
graph correspond to those edges (of $K_5$), two vertices are
connected by an edge in the Petersen graph if the corresponding
edges in $K_5$ meet at a vertex (of $K_5$).
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=.5]{petersen.eps}
\end{center}
\caption[The Petersen graph]{The Petersen graph, named for its %
discoverer, the Danish mathematician Julius Petersen.} \label{f:petersen}
\end{figure}
\clearpage
\section{Isomorphism}
The word {\em isomorphism} cames from Greek roots, its
meaning is roughly ``equal shapes.'' We say that two
graphs are isomorphic if there is a function $\phi$ that maps the
vertex set of one graph to the vertex set of the other;
additionally, this function must be a bijection (one-to-one
and onto) and it
must respect the edge-endpoint relation. That is,
if $v_i$ and $v_j$ are connected by some number of edges
in the first graph then $\phi(v_i)$ and $\phi(v_j)$ are connected
by the same number of edges in the second.
In a more formal treatment we would require $\phi$ to map both
the vertex set {\em and} the edge set, and the phrase ``respect the
edge-endpoint relation'' would mean that
\[
f(e) = v \; \iff \; f(\phi(e)) = \phi(v)
\]
\noindent where $f$ denotes the edge endpoint relation.
There are a great number of properties called {\em graph invariants}
that can be used to decide whether graphs are {\em not} isomorphic.
For instance if two graphs have a different number of nodes,
they cannot possibly be isomorphic ($\phi$ couldn't be a bijection
in that case). Similarly, two isomorphic graphs must have the same
number of edges.
Clearly these conditions are not sufficient. Consider the
two graphs in Figure~\ref{f:non-iso_graphs}, they both have 5 vertices
and 5 edges, but obviously there is something different about them.
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=.5]{non-iso_graphs.eps}
\end{center}
\caption[Non-isomorphic graphs.]{Non-isomorphic graphs that have the %
same number of vertices as well as edges.} \label{f:non-iso_graphs}
\end{figure}
\clearpage
One feature that can be used to distinguish the graphs in
Figure~\ref{f:non-iso_graphs} is the degrees of their vertices.
The {\em degree} of a vertex $v$ in a graph $G$ is the number
of edges that are incident with it. (Note that since a loop
is incident twice with the same vertex, it will add two to
the degree of that vertex.) There is a vertex having degree
1 in the graph on the left in the figure, whereas all the vertices
in the right-hand graph have degree 2.
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=.3,angle=-90]{graph_iso.eps}
\end{center}
\caption[Isomorphic?]{Are these pairs of graphs isomorphic?} \label{f:graph_iso}
\end{figure}
\begin{shortquiz}
Which of the pairs of graphs in Figure~\ref{f:graph_iso} are isomorphic?
\begin{answers}[qz:graph_iso]{4}
\Ans0 none &\Ans1 1st but not 2nd &\Ans0 2nd but not first &\Ans0 both
\end{answers}
\begin{solution}
\begin{quote}
The first pair of graphs are isomorphic (both are the Petersen
graph). The second pair can be differentiated, the left graph
has only even cycles, the graph on the right has some odd cycles.
\end{quote}
\end{solution}
\end{shortquiz}
\clearpage
Another graph invariant that is easily used to detect the difference
between non-isomorphic graphs is the number of cycles of a given
length. A {\em cycle} in a graph is a path along the edges
of $G$ that begins and ends in the same place and never hits
a vertex (other than the initial one) more than once -- it
must also not cross any edge more than once. Consider
the non-isomorphic graphs from the quiz. The graph on
the left in Figure~\ref{f:graph_iso} has only even length cycles,
whereas the graph on the right has cycles of length 5.
There are many other properties of graphs that are invariants.
\end{document}