Continuing Training Program for Mathematics Teachers in

Northern Luzon - Part IV

Saint Marys University
Bayombong, Nueva Vizcaya
October 26-27, 2010
SELECTED TOPICS IN GRAPH THEORY
Phoebe Chloe F. Ramos
University of the Philippines Baguio
Chapter 1
Introduction
1.1 Why Study Graphs?
The best way to illustrate the utility of graphs is via a Cooks tour of several simple problems that
can be stated and solved via graph theory. We do this in an intuitive manner prior to presenting
formal denitions. Graph theory has many practical applications in various disciplines, including,
to name a few, biology, computer science, economics, engineering, informatics, linguistics, mathe-
matics, medicine, and social science. As will become evident after reading this chapter, graphs are
excellent modeling tools. We now look at some several classic problems.
The Bridges of Konigsberg
Euler (1707- 1782) became the father of graph theory as well as topology when in 1736 he
settled a famous unsolved problem of his day called the K onigsberg Bridge Problem.
The river Pregel separates the city of Konigsberg into 4 separate regions and the regions are
connected by 7 bridges. In the summer evenings, the citizens of the country would like to have
a walk around the whole city. Some curious citizens wondered whether it is possible to begin at
one of the regions, cross each bridge exactly once and return to the same starting point. Can the
citizens suggestion be made possible?
Figure 1.1: The Seven Bridges of K onigsberg
3
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
...........................................................................................................................................................................................................
............................................................................................................................................................
............................................................................................................................................................

.
.
.
.
Figure 1.2: The graph of the seven bridges of Konigsberg
The next problem we discuss concerns discovering communities on the World Wide Web (WWW).
World Wide Web Communities
The World Wide Web can be modeled as a graph, where the web pages are represented by dots or
vertices and the hyperlinks between them are represented by lines or edges in the graph. One can
discover interesting information by examining this Web Graph. As an example, the graph shown
is termed a Web community. This name is bestowed because the vertices represent two dierent
classes of objects, and each vertex representing one type of object is connected to every vertex
representing the other kind of objects.
Such web communities can be discovered by nding complete bipartite subgraphs in the Web graph.
Web community information can be used for marketing purposes or for examining the relationships
among companies in a given industry.
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
. . . . . . . . ................. . . . . . . .
......................................................................................................................................................................
.......................................................................................................................................................................................................
.............................................................................................................................................................................................................................................
...............................................................................................................................................
......................................................................................................................................................................
.......................................................................................................................................................................................................
...................................................................................................................................... ...............................................................................................................................................
......................................................................................................................................................................
...............................................................................................................................................
...................................................................................................................................... ............................................................................................................................................... ......................................................................................................................................................................
...............................................................................................................................................
......................................................................................................................................
.......................................................................................................................................................................................................
......................................................................................................................................................................
...............................................................................................................................................
.............................................................................................................................................................................................................................................
.......................................................................................................................................................................................................
......................................................................................................................................................................
Job Assignments
A certain company has ve dierent jobs labeled by J
i
, where 1 i 5, and wants to hire
people for these positions. The seven applicants, labeled by A
j
for 1 j 7, are qualied for
some of the positions, but not for others. An edge between an applicant A
j
and a job J
i
means
that applicant A
j
is qualied for job J
i
. This graph is an example of a bipartite graph, where the
vertices represent two kinds of objects. The question in this problem is : Can the company ll all
its open positions with qualied applicants?
Figure 1.3: Bipartite graph describing job qualications
Storing Volatile Chemicals
A particular chemical factory produces seven dierent kinds of chemicals, labeled as C
1
, C
2
, , C
7
.
For security reasons some of the chemicals should not be stored in the same warehouse. The graph
depicted shows the situation of volatility between the chemicals, where an edge between chemicals
C
i
and C
j
indicates a grave danger in storing these chemicals in the same warehouse, whereas lack
of an edge indicates it is safe to store the chemicals in the same warehouse. Here is the question:
What is the minimum number of warehouse the factory needs in order to store its chemical products
safely?
Chapter 2
Basic Concepts in Graph Theory
2.1 The Denition of a Graph
A graph G consists of a nite nonempty set V (G) of objects called vertices together with a set
E(G) of unordered pairs of vertices; the elements of E(G) are called edges. The sets V (G) and
E(G) are called the vertex set and edge set of G respectively. So a graph G is a pair (actually
an ordered pair) of two sets V (G) and E(G). For this reason, some write G = (V, E). Vertices are
sometmes called points or nodes and edges are sometimes called lines. Two graphs G and H are
equal if V (G) = V (H) and E(G) = E(H), in which case we write G = H.
It is common to represent a graph by a diagram in the plane where the vertices are repre-
sented by points and whose edges are indicated by the presence of a line segment or curve between
the two points in the plane corresponding to the appropriate vertices. The diagram itself is referred
to as a graph.
Figure 2.1: A Graph G
7
For the graph G above, the vertex set V (G) and the edge set E(G) are
V (G) = c
1
, c
2
, c
3
, c
4
, c
5
, c
6
, c
7

E(G) = c
1
, c
2
, c
1
, c
3
, c
1
, c
5
, c
1
, c
7
, c
2
, c
3
, c
2
, c
4
, c
2
, c
7
,
c
3
, c
4
, c
3
, c
5
, c
4
, c
5
, c
4
, c
6
, c
4
, c
7
, c
6
, c
7

When dealing with graphs, it is customary and simpler to write a 2-element set or an edge
u, v in G as uv (or vu). If uv is an edge of G, then u and v are said to be adjacent in G. The
number of vertices in G is often called the order of G while the number of edges is its size. Since
the vertex set of every graph is nonempty, the order of every graph is at least 1. A graph with
exactly one vertex is called a trivial graph, implying that the order of a nontrivial graph is at
least 2.
Figure 2.2: A trivial graph
The graph G in Figure 2.1 has order 7 and size 13. We often use n and m for the order and size,
respectively, of a graph. So for the graph in Figure 1.3, n = 7 and m = 13.
A graph G with V (G) = u, v, w, x, y and E(G) = uv, uw, vw, vx, wx, xy is shown in Figure
1.4. There are occasions when we are interested in the structure of the graph and not in what the
vertices are called. In this case a graph is drawn without labeling its vertices. For this reason, the
graph G of Figure 2.3 (a) is a labeled graph and Figure 1.4 (b) represents an unlabeled graph.
Figure 2.3: A labeled graph and an unlabeled graph
Exercises
1. Let S = 2, 3, 4, 7, 11, 13. Draw the graph G whose vertex set is S and such that ij E(G)
for i, j S if i + j S or [i j[ S.
2. Suppose that we have a collection of 3-letter English words, say
ACT, AIM, ARC, ARM, ART, CAR, CAT, OAR, OAT, RAT, TAR.
We say that a word W
1
can be transformed into a word W
2
if W
2
can be obtained from W
1
by performing exactly one of the following two steps:
(a) interchanging two letters of W
1
;
(b) replacing a letter in W
1
by another letter.
Therefore, if W
1
can be transformed into W
2
, then W
2
can be transformed into W
1
. This
situation can be modeled by a graph G, where the given words are the vertices of G and two
vertices are adjacent in G if the corresponding words can be transformed into each other.
This graph is called the word graph of the set of words. Draw the graph G.
3. Give an example of ve 3-letter words whose word graph is shown below.(with the vertices
appropriately labeled).
Figure 2.4: The graph for exercise 3
4. Give a set of ve 3-letter words whose word graph is shown below.(with the vertices appro-
priately labeled)
Figure 2.5: The graph for exercise 4
5. The gure below illustrates the trac lanes at the intersection of two streets. When a vehicle
approaches this intersection, it could be in one of the seven lanes: L1, L2, L3,L4,L5, L6, L7.
Draw a graph G that models this situation, where V (G) = L1, L2, L3, L4, L5, L6, L7 and
where two vertices are joined by an edge if vehicles in these two lanes cannot safely enter this
intersection at the same time.
2.2 Subgraphs
In order to analyze certain situations that can be modeled by graphs, we must have a better un-
derstanding of graphs. As with all areas of mathematics, there is a certain amount of terminology
Figure 2.6: Trac lanes
.
with which we must be familiar in order to discuss graphs and their properties. Learning this
fundamental terminology is our current goal.
Let us review some concepts and introduce others. If e = uv is an edge of G, then u and v
are adjacent vertices. We also say u and v are joined by the edge e. The vertices u and v are
referred to as neighbors of each other. In this case, the vertex u and the edge e (as well as v
and e) are said to be incident with each other. Distinct edges incident with a common vertex are
adjacent edges.
A graph H is called a subgraph of a graph G, written H G, if V (H) V (G) and
E(H) E(G). We also say that G contains H as a subgraph. If H G and either V (H) is a
proper subset of V (G) or E(H) is a proper subset of E(G), then H is a proper subgraph of G.
So the graph H of Figure 2.4 is a subgraph of the graph of G shown in the gure; indeed, H is
a proper subgraph of G. If a subgraph of a graph G has the same vertex set as G, then it is a
spanning subgraph of G.
A subgraph F of a graph G is called an induced subgraph of G if whenever u and v are
vertices of F and uv is an edge of G, then uv is an edge of F as well.
If S is a nonempty set of vertices of a graph G, then the subgraph of G induced by S
is the induced subgraph with vertex set S. The induced subgraph is denoted by S). To emphasize
that this is an induced subgraph of G, we sometimes denote the subgraph by S)
G
.
Figure 2.7: A graph G and some of its subgraphs
For a nonempty set X of edges , the subgraph X) induced by X has edge set X and
consists of all vertices that are incident with at least one edge in X. This subgraph is called an
edge-induced subgraph of G. Sometimes G[S] and G[X] are used for S) and X) , respectively.
Any proper subgraph of a graph G can be obtained by removing vertices and edges from G. For
an edge e of G, we write Ge for the spanning subgraph of G whose edge set consists of all edges
of G except e. More generally, if X is a set of edges of G, then GX is the spanning subgraph of G
with E(GX) = E(G)X. If X = e
1
, e
2
, , e
k
, then we also write GX as Ge
1
e
2
e
k
.
For a vertex v of a nontrivial graph G, the subgraph G v consists of all vertices of G ex-
cept v and all edges of G except those incident with v. For a proper subset U of V (G), the
subgraph G U has vertex set V (G) U and its edge set consists of all edges of G joining two
vertices in V (G) U. Necessarily, GU is an induced subgraph of G; indeed GU = V (G)).
If u and v are nonadjacent vertices of a graph G, then e = uv / E(G). By G+e, we mean the
graph with vertex set V (G) and edge set E(G) e. Thus, G is a spanning subgraph of G + e.
2.3 Walks, Paths and Cycles
Many of the concepts that occur in graph theory and which we will investigate in detail later con-
cern various ways in which one can move about in a graph.
Lets start at some vertex u of a graph G. If we proceed from u to a neighbor of u and
then to a neighbor of that vertex, and so on, until we nally come to a stop at a vertex v, then we
have just described a walk from u to v in G. More formally, a u v walk W in G is a sequence of
vertices in G, beginning with u and ending at v such that consecutive vertices in the sequence are
adjacent (or they form an edge), that is, we can express W as
W : u = v
0
, v
1
, , v
k
= v,
where k 0 and v
i
and v
i+1
are adjacent for i = 0, 1, 2, , k 1. Each vertex v
i
(0 i k)
and each edge v
i
v
i+1
(0 i k) is said to lie on or belong to W. Notice that the denition of the
walk W does not require the listed vertices to be distinct; in fact, even u and v are not required to
be distinct. However, every two consecutive vertices in W are distinct since they are adjacent. If
u = v, then the walk is closed; while if u ,= v, then W is open.
The number of edges encountered in a walk (including multiple occurrences of an edge) is called
the length of the walk.
For the graph G above,
Figure 2.8: Illustrating walks in a graph G
W : x, y, w, y, v, w
is an x w walk of length 5 ( one less than the number of occurrences of vertices in the walk). A
walk of length 0 is a trivial walk. So
W : v
is a trivial walk.
We dene a u v trail in a graph G to be a u v walk in which no edge is traversed more
than once. Thus, the x w walk W is not an x w trail as the edge wy is repeated. On the other
hand
T : u, w, y, x, w, v
is a u v trail. Notice that this trail repeats the vertex w.
A u v walk in a graph in which no vertices are repeated is a u v path. While the u v
trail T is not a u v path,
P : u, w, y, v
is a u v path. If no vertex in a walk is repeated (thereby producing a path), then no edge is
repeated either. Hence, every path is a trail.
If a u v walk in a graph is followed by a v w path, then a u w walk results. In particu-
lar, a u v path followed by a v w path is a u w walk W, but not necessarily a u w path, as
vertices in W may be repeated. While not every walk is a path, if a graph contains a u v walk,
then it must also contain a u v path.
Theorem 1. If a graph G contains a uv walk of length l, then G contains a uv path of length
at most l.
A walk is closed when the rst and the last vertices, x
0
and x
n
are the same. Closed walks are
also called circuits. Sometimes, they also refer to a circuit in a graph G as a closed trail of length
3 or more. Hence a circuit begins and ends at the same vertex but repeats no edge. For the graph
in Figure 2.5, the following are circuits:
C : y, w, u, v, w, x, y
: x, y, w, u, v, w, x
: w, x, y, w, u, v, w
A cycle of length n is a closed walk of length n, n 3, in which no vertex is repeated. A k cycle
is a cycle of lenth k. A 3-cycle is also referred to as a triangle. A cycle of odd length is called an
odd cycle; while a cycle of even length is called an even cycle. The following is an example of a
cycle, namely a 4-cycle.
C

: x, y, v, w, x
The vertices ad edges of a trail, path, cicuit, or cycle in a graph G form a subgraph of G, also called
a trail, path, circuit or cycle. Hence a path, for example is used to describe both a manner of
traversing certain vertices and edges of G and a subgraph consisting of those vertices and edges.
The subgraphs G
1
, G
2
, G
3
, G
4
of the graph G in Figure 2.5 are a trail, path, circuit, and cycle,
respectively.
We will have special interest in graphs G in which it is possible to travel from each vertex of G
to any other vertex of G. If G contains a u v path, then u and v are said to be connected and
u is connected to v (and v is connected to u). So, saying that u and v are connected only means
that there is some u v path in G; it doesnt say that u and v are joined by an edge. Of course,
if u is joined to v, then u is connected to v as well. A graph G is connected if every two ver-
tices of G are connected, that is, if G contains a uv path for every pair u, v of distinct vertices of G.
A graph that is not connected is called disconnected. A connected subgraph of G that is not
a proper subgraph of any other connected subgraph of G is a component of G. A graph G is
connected if and only if it has exactly one component.
The graph G in Figure 2.5 is connected, while graph H below is disconnected since, there is
no s w path in H. There is no x z path either.The graph H has three components namely H
1
,
H
2
and H
3
.
Figure 2.9: Trails, paths, circuits and cycles as subgraphs of a graph
Figure 2.10: A disconnected graph and its components
Let G be a connected graph of order n, and let u and v be two vertices of G. The distance between
u and v is the smallest length of any u v path in G and is denoted by d
G
(u, v) or simply d(u, v)
if the graph G under consideration is clear. Hence, if d(u, v) = k, then there exists a u v path
P : u = v
0
, v
1
, , v
k
= v
of length k in G but no u v path of smaller length exists in G. A u v path of length d(u, v)
is called a u v geodesic. In fact, since the path P above is a u v geodesic, not only is
d(u, v) = d(u, v
k
) = k, but d(u, v
i
) = i for every i with 0 i k.
If u = v, then d(u, v) = 0. If uv E(G), then d(u, v) = 1. In general, 0 d(u, v) n 1
for every two vertices u and v (distinct or not) in a connected graph of order n. For the vertices
u and y in the graph in Figure 2.5, d(u, y) = 2. If G is disconnected, then there are some pairs
x, y of distinct vertices of G such that there is no xy path in G. In this case, d(x, y) is not dened.
The greatest distance between any two vertices of a connected graph G is called the diam-
eter of G and is denoted by diam(G).
Exercises
1. Let G be the graph shown below, let X = e, f, where e = ru and f = vw, and let
U = u, w. Draw the subgraphs GX and GU of G.
Figure 2.11: The graph G for items 1-2
2. For the graph G of Figure 2.8, give an example of each of the following or explain why no
such example exists.
(a) An x y walk of length 6.
(b) A v w trail that is not a v w path.
(c) An r z path of length 2.
(d) An x z path of length 3.
(e) An x t path of length d(x, t).
(f) A circuit of length 10.
(g) A cycle of length 8.
(h) A geodesic whose length is diam(G).
3. Prove that if P and Q are two longest paths in a connected graph, then P and Q have at
least one vertex in common.
4. Prove or disprove: Let G be a connected graph of diameter k. If P and Q are two geodesics
of length k in G, then P and Q have at least one vertex in common.
2.4 Common Classes of Graphs
As we continue to study graphs, we will see that there are certain graphs that are encountered often
and it is useful to be familiar with them. In many instances, there is special notation reserved for
these graphs.
We have already seen that paths and cycles are certain kind of walks in graphs. These terms
are also used to describe certain kinds of graphs. If the vertices of a graph G of order n can be
labeled (or relabeled) v
1
, v
2
, , v
n
so that its edges are v
1
v
2
, v
2
v
3
, , v
n1
v
n
, then G is called a
path; while if the vertices of a graph G of order n 3 can be labeled (or relabeled ) v
1
, v
2
, , v
n
so that its edges are v
1
v
2
, v
2
v
3
, , v
n1
v
n
, and v
1
v
n
, then G is called a cycle.
A graph that is a path of order n is denoted by P
n
, while a graph that is a cycle of order
n 3 is denoted by C
n
. Several paths and cycles are shown below.
Figure 2.12: Paths and cycles
A graph G is complete if every two distinct vertices of G are adjacent. A complete graph of
order n is denoted by K
n
. Therefore, K
n
has the maximum possible size for a graph with n vertices.
Since every two distinct vertices of K
n
are joined by an edge, the number of pairs of vertices in K
n
is

n
2

and so
the size of K
n
is

n
2

=
n(n 1)
2
.
Therefore, the complete graph K
3
has three edges, K
4
has six edges, and K
5
has ten edges. The
rst ve complete graphs are shown in Figure . Notice that P
1
and K
1
represent the same graph,
as do P
2
and K
2
, as well as C
3
and K
3
. Although there are edges that cross in the drawings of K
4
and K
5
, the points of intersection do not represent vertices.
Although we have attempted to draw these graphs in a manner that makes them easy to visualize,
this is certainly not a requirement when drawing a graph, as its vertices can be placed in any
convenient location. The gure below shows a variety of ways to draw the path P
4
and complete
graph K
4
.
The complement G of a graph G is that graph whose vertex set is V (G) and such that for
each pair u, v of vertices of G, uv is an edge of G if and only if uv is not an edge of G. Observe that
if G is a graph of order n and size m, then G is a graph of order n and size

n
2

m. The graph
K
n
then has n vertices and no edges; it is called the empty graph of order n. Therefore, empty
graphs have empty edge sets. In fact, if G is any graph of order n, then G E(G) is the empty
Figure 2.13: Complete graphs
Figure 2.14: The graphs P
4
and K
4
graph K
n
. By denition, no graph can have an empty vertex set. A graph H and its complement
are shown below. Both of these graphs are connected. Although a graph and its complement need
not both be connected, at least one must be connected.
Theorem 2. If G is a disconnected graph, then G is connected.
We now turn to graphs whose vertex sets can be partitioned in special ways. A graph G is a
bipartite graph if V (G) can be partitioned into two subsets U and W, called partite sets, such
that every edge of G joins a vertex of U and a vertex of W. Its not always easy to tell at a glance
whether a graph is bipartite.
For example, the connected graphs G
1
and G
2
of Figure 2.13 are bipartite as every edge of G
1
joins a vertex of U
1
= u
1
, x
1
, y
1
and a vertex of W
1
= v
1
, w
1
, while every edge of G
2
joins a
vertex of U
2
= u
2
, w
2
, y
2
and a vertex of W
2
= v
2
, x
2
, z
2
. The bipartite nature of these graphs
is illustrated in Figure 2.13.
Figure 2.15: A graph and its complement
Figure 2.16: Bipartite graphs
Theorem 3. A nontrivial graph G is a bipartite graph if and only if G contains no odd cycles.
We know that if G is a bipartite graph, then V (G) can be partitioned into two subsets U and W,
called partite sets, such that every edge of G joins a vertex of U and a vertex of W. However,
this does not mean that every vertex of U is adjacent to every vertex of W. If this does happen,
however, then we call G a complete bipartite graph. A complete bipartite graph with [U[ = s
and [W[ = t is denoted by K
s,t
or K
t,s
. If either s = 1 or t = 1, then K
s,t
is a star.
2.5 Multigraphs and Digraphs
We can obtain similar structures by altering our denition in various ways. Here are some examples.
1. By replacing our set E(G) with a set of ordered pairs of vertices, we obtain a directed graph
or digraph . Each edge of a digraph has a specic orientation.
Figure 2.17: A digraph.
2. If we allow repeated elements in our set of edges, technically replacing our set E(G) with a
multiset, we obtain a multigraph.
Figure 2.18: A multigraph
3. By allowing edges to connect a vertex to itself (loops) , we obtain a ( pseudograph).
Figure 2.19: A pseudograph
.
4. Allowing our edges to be arbitrary subsets of vertices (rather than just pairs) gives us hyper-
graphs.
5. By allowing V (G) or E(G) to be an innite set, we obtain innite graphs.
If a graph has no loops or multiple edges, we call it a simple graph.
Exercise
1. Ten people are seated around a circular table. Each person shakes hands with everyone at
the table except the person sitting directly across the table. Draw a graph that models the
situation.
2.6 Degree of a Vertex
Definiton: The degree (or valence) of a vertex v in a graph G, denoted by deg(v), is the number
of proper edges incident on v plus twice the number of self-loops. ( Applications of graph theory
to physical chemistry motivate the use of the term valence).
Figure 2.20: A hypergraph
.
Terminology: A vertex of degree d is also called a d valent vertex.
Notation: The smallest and largest degrees in a graph G are denoted
min
and
max
(or
min
(G)
and
max
(G) when there is more than one graph under discussion). Some authors use instead of

min
and instead of
max
.
Definition. The degree sequence of a graph is the sequence formed by arranging the ver-
tex degrees in non-increasing order.
Proposition 1. A non-trivial simple graph G must have at least one pair of vertices whose degrees
are equal.
The work of Leonhard Euler (1707-1783) is regarded as the beginning of graph theory as a math-
ematical discipline. The following result of Euler establishes a fundamental relationship between
the vertices and edges of a graph.
Theorem 4. Eulers Degree-Sum Theorem.
The sum of the degrees of the vertices of the graph is twice the number of edges.
Corollary 1. In a graph, there is an even number of vertices having odd degree.
Corollary 2. The degree sequence of a graph is a nite,non-increasing sequence of nonnegative
integers whose sum is even.
Conversely, any non-increasing, nonnegative sequence of integers whose sum is even is the degree
sequence of some graph. The following theorem prescribes how to construct such a graph. The
following preliminary example illustrates the construction.
Theorem 5. Suppose that d
1
, d
2
, , d
n
) is a sequence of nonnegative integers whose sum is even.
Then there exists a graph with vertices v
1
, v
2
, , v
n
such that deg(v
i
) = d
i
, for i = 1, 2 , n.
Graphic Sequences
The construction in the above theorem is straightforward but hinges on allowing the graph
to be non-simple. A more interesting problem is determining when a sequence is the degree se-
quence of a simple graph.
Definition. A sequence d
1
, d
2
, , d
n
) is said to be graphic if there is a permutation of it that
is a degree sequence of some simple graph. Such a simple graph is said to realize the sequence.
Theorem 6. Let d
1
, d
2
, , d
n
) be a graphic sequence, with d
1
d
2
d
n
. Then there is a
simple graph with vertex-set v
1
, , v satisfying deg(v
i
) = d
i
for i = 1, 2, , n, such that v
1
is
adjacent to vertices v
2
, , v
d
1
+1
.
Corollary 3. [Havel (1955) and Hakimi (1961)]
A sequence d
1
, d
2
, , d
n
) of nonnegative integers such that d
1
d
2
d
n
is graphic if
and only if the sequence d
2
1, , d
d
1
+1
1, d
d
1
+2
, , d
n
) is graphic.
EXERCISES
1. Draw a graph with the given degree sequence.
(a) 8, 7, 3) (b) 9, 8, 8, 6, 5, 3, 1).
2. Draw a simple graph with the given degree sequence.
(a) 6, 4, 4, 3, 3, 2, 1, 1) (b) 5, 5, 5, 3, 3, 3, 3, 3).
3. Given a group of nine people, is it possible for each person to shake hands with exactly three
other people?
If d(x) = 0, then x is called an isolated vertex while a vertex of degree 1 is called a pendant.
The edge incident with a pendant is called a pendant edge. A graph is called regular if all its
vertices have the same degree. If the common degree is r, it is called r-regular. In particular, a
3-regular graph is called a cubic. We write (G) for the smallest of all degrees of vertices of G,
and (G) for the largest.
Theorem 7. In any graph or multigraph G , the sum of the degrees of the vertices equals twice the
number of edges.

uV (G)
d(u) = 2 [E(G)[ .
The above theorem is also known as Hand-Shaking Theorem, from the following party analogy:
Consider a collection of guests at a party. Suppose some guests shook hands with some other
guests. If we asked everyone at the party how many guests they shook hands with and added those
numbers all up, this sum would be equal to twice the number of total hand shakes. In graph theory
terms, each vertex represents a guest, and an edge between two guests represents a handshake
between them.
Corollary 4. In any graph or multigraph, the number of vertices of odd degree is even. In partic-
ular, a regular graph of odd degree has an even number of vertices.
By the Hand-Shaking theorem, we obtain the following result.
Corollary 5. Every k regular graph on n vertices has kn/2 edges. In particular, the complete
graph K
n
has (n 1)n/2 edges.
Exercises:
1. Draw a portion of your academic departments Web page as a graph by modeling Web pages
as vertices and hyperlinks as edges. Include at least ten dierent Web pages and draw edges
for all of the existing hyperlinks between the Web pages you select. Label the vertices with
their uniform resource locators.
2. Refer to the job assignments dicussed earlier. Is the company able to meet its hiring needs?
If so, providr a possible set of hires that meet their needs.
3. For n 1, 2, 3, 4, 5, draw the following graphs : N
n
, P
n
, C
n
, K
n
, and K
n,n
. Which of the
graphs are the same?
4. Construct a table whose entries are formulas for the number of vertices and edges for the
graphs N
n
, P
n
, C
n
, K
n
and K
m,n
for arbitrary values of n and m.
5. Express both the maximum and minimum degree of vertices in the graphs N
n
, P
n
, C
n
, K
n
and K
m,n
in terms of n and m.
6. For what kind of vertices u in a graph G do we have N
G
(u) = N
G
[u]?
7. For every k regular graph, is there a (k + 1)- regular graph that contains the k regular
graph as a subgraph?
8. Let m
30
(n) be the maximum number of edges that a simple graph on n vertices can have,
if each vertex of the graph is connected to at most 30% of the other vertices. Determine a
quadratic polynomial p(x) = Ax
2
+ Bx + C such that
(a) m
30
(n) p(n) for every n ^.
(b) m
30
(n) = p(n) holds for innitely many n ^.
Is p(n) uniquely determined by the two conditions above?
9. Let G be the simple graph, where the vertices correspond to each of the squares of an 8 8
chess board, and where two squares are adjacent if,and only if , a knight can go from one
square to the other in one move. What is/are teh possible degree(s) of a vertex in G? How
many vertices have each degree? How many edges does G have?
2.7 Connectivity
Given any graph G, the set of all edges of K
V (G)
that are not edges of G will form a graph with
V (G) as vertex set; this new graph is called the complement of G, and written G. More generally,
if G is a subgraph of H, then the graph formed by deleting all edges of G from H is called the
complement of G in H denoted by HG ( or the complement of G relative to H). The complement
of the complete graph K
s
on vertex set S is called a null graph; we also write K
v
for a null graph
with v vertices.
A graph is called disconnected if its vertex set can be partitioned into two subsets, V
1
and
V
2
, that have no common element, in such a way that there is no edge with one endpoint in V
1
and
the other in V
2
; if a graph is not disconnected then it is connected.
A disconnected graph consists of a number of disjoint subgraphs; a maximal connected subgraph is
called a component. In a way, connectedness generalizes adjacency. In a connected graph, not all
vertices are adjacent, but if x and y are not adjacent, then there must exist vertices x
1
, x
2
, , x
n
such that x is adjacent to x
1
, x
1
is adjacent to x
2
, and x
n
is adjacent to y; such a sequence is
called an xy walk. Conversely, if every pair of nonadjacent vertices is joined by such a walk, the
graph is connected.
Theorem 8. For a simple graph G with n vertices and k components we have
[E(G)[
(n k)(n k + 1)
2
.
Chapter 3
Distance in Graphs
How far is it from one vertex to another? In this section we dene distance in graphs, and we
consider several properties, interpretations, and applications.
Distance functions, called metrics, are used in many dierent areas of mathematics, and they
have three dening properties.
If d is a metric, then
d(x, y) 0, for all x, y, and d(x, y) = 0 if and only if x = y;
d(x, y) = d(y, x) for all x, y;
d(x, y) d(x, z) + d(z, y) for all x, y, z.
The distance concept in the graph sense is in fact a metric.
Distance in graphs is dened in a natural way: in a connected graph G, the distance from vertex
u to vertex v is the length (number of edges) of the shortest u v path in G. We denote this
distance by d(u, v), and in situations where clarity of context is important, we may write d
G
(u, v).
In Figure 4.1 , d(b, k) = 4 and d(c, m) = 6.
Figure 3.1: A graph G
For a given vertex v of a connected graph, the eccentricity of v, denoted ecc(v), is dened to be
the greatest distance from v to any other vertex. That is
ecc(v) = max
xV (G)
d(v, x)
25
In Figure 4.1 ecc(a) = 5 since the farthest vertices from a (namely k,m,n) are at a distance of 5
from a.
Of the vertices in this graph, vertices c, k, m and n have the greatest eccentricity (6), and ver-
tices e, f and g have the smallest eccentricity (3). These values and types of vertices are given
special names.
In a connected graph G, the radius of G, denoted rad(G), is the value of the smallest eccen-
tricity. Similarly, the diameter of G, denoted diam(G), is the value of the greatest eccentricity.
The center of the graph G is the set of vertices v, such that ecc(v) = rad(G). The periphery
of G is the set of vertices u, such that ecc(u) = diam(G). In Figure, the radius is 3, the diameter
is 6, and the center and periphery of the graph are, respectively, e, f, g and c, k, m, n.
You may have noticed that the diameter of our graph G is twice the radius of G. While this
does seem to be a natural relationship, such is not the case for all graphs. Take a quick look at a
cycle or a complete graph. For either of these graphs, the radius and diameter are equal!
The following theorem describes the proper relationship between the radii and diameters of graphs.
While not as natural, tight or circle-like as you might hope, this relationship does not have the
advantage of being correct.
Theorem 9. For any connected graph G, rad(G) diam(G) 2rad(G).
Theorem 10. Every graph is (isomorphic to) the center of some graph.
Exercises.
1. Find the radius, diameter and center of the graph shown below.
2. Find the radius and diameter of each of the following graphs: P
2k
, P
2k+1
, C
2k
, C
2k+1
, K
n
, K
m,n
.
3. If x is in the periphery of G and d(x, y) = ecc(x), the prove that y is in the periphery of G.
4. Prove that if G is regular and diam(G) = 3, then diam(G) = 2.
Chapter 4
Trees
A tree is a connected graph that contains no cycles. Graph-theoretic trees resemble the trees we
see outside our windows. Trees do not have cycles, just as the branches of trees in nature do not
split and rejoin.
Figure 4.1: Which one are trees?
The graph D in Figure is not a tree; rather, it is a forest. A forest is a collection of one or more
trees. A vertex of degree 1 in a tree is called a leaf. K
1
and K
2
are considered as trees. In the
spirit of our terminology, perhaps we should call K
1
a stump and K
2
a twig!
It is clear that K
1
and K
2
are the only trees of order 1 and 2, respectively. P
3
is the only tree of
order 3.
The Figure below shows the dierent trees of order 6 or less.
Trees sprout up as eective models in a wide variety of applications.
Example
1. Trees are useful for modeling the possible outcomes of an experiment. Consider an experiment
in which a coin is ipped and a 6-sided die is rolled. Tne leaves in the tree in Figure correspond
27
Figure 4.2: Trees of order 6 or less.
to the outcomes in the probability space for this experiment.
Figure 4.3: Outcomes of a coin/die experiment
2. Programmers often use tree structures to facilitate searches and sorts and to model logic of
algorithms. For instance, the logic for a program that nds the maximum of four number5s
(w,x,y,z) can be represented by the tree shown in Figure. This type of tree is a binary
decision search tree.
3. Chemists can use trees to represent, among other things, saturated hydrocarbons- chemical
compounds of the form C
n
H
2n+2
(propane, for exmple). The bonds between between the
carbon and hydrogen atoms ate depicted in the trees of Figure. The vertices of degree 4 are
carbon atoms, and the leaves represent the hydrogen atoms.
Figure 4.4: Logic of a program
Figure 4.5: A few saturated hydrocarbons.
Exercises
1. Draw all unlabeled trees of order 7. (Hint: There are a prime number of them.)
2. Draw all unlabeled forests of order 6.
3. Let T be a tree of order n 2. Prove that T is bipartite.
4.1 The Minimum Spanning Tree Problem
Suppose that initially, no roads existed between any pair of the villages v
1
, v
2
, , v
7
. Then we
need to construct roads between pairs of dormitories. Which roads will be constructed is quite
possibly a nancial decision here as well. Before proceeding further, let us consider a new concept.
If a connected graph G of order n has no cycles, then of course, G is a tree. On the other hand,
suppose that G contains cycles. Recall that a subgraph H of a graph G is a spanning subgraph
of G if H contains every vertex of G. A spanning subgraph H of a connected graph G such that H
is a tree is called a spanning tree of G. For the connected graph G, two dierent spanning trees
T
1
and T
2
of G are shown.
Figure 4.6: Two spanning trees in a graph
Figure 4.7: Villages and roads
Once again, let us return to the example we considered in Figure 4.7, where there are seven villages
and six roads. The graph describing this situation is a tree. Hence it is possible to travel between
every two villages. Indeed, there is a unique path between every two villages. To travel between
villages v
1
and v
6
, we are forced to pass through v
2
, v
3
, and v
4
, even if we didnt want to. Therefore,
the trip between v
1
and v
6
may be inconvenient. Of course, to make the trip between pairs of the
villages more convenient , we could always build a new road (between v
1
and v
6
, say). However,
this would cost more money (possibly a great deal of money). But how was it decided initially that
the six roads in Figure 5.7 were the ones to be constructed? Certainly whichever roads were chosen
should produce a connected graph. If the resulting graph contains a cycle, then there are edges in
the graph that are not bridges. That is, if producing a connected graph was our primary goal, the
we could have accomplished this for less money by constructing roads so that the resulting graph
is a tree. But how did we chose those particular roads to build?
Figure 4.8: A graph model of villages and roads.
Suppose that we have a number of villages (such as v
1
, v
2
, , v
7
) and we would like to build
roads as cheaply as possible so that, at the conclusion, the resulting graph is connected. How do
we do this?
Assume that we have an accurate estimate of the cost of building a road between each pair of
villages. If the cost of building a road between some pair of villages is exorbitant ( because any
such road would have to pass through quicksand, private property, or through or over a mountain,
for example), then we do not even consider building such a road. This problem can be stated in
terms of graphs.
Let G be a connected graph each of whose edges is assigned a number (called the cost or
weigth of the edge). We denote the weight of an edge e of G by w(e). Recall that such a graph
is called a weighted graph. For each subgraph H of G, the weight w(H) of H is dened as the
sum of the weights of its edges, that is
w(H) =

eE(H)
w(e).
We seek a spanning tree G whose weight is minimum among all spanning trees of G. Such a span-
ning tree is called a minimum spanning tree. The problem of nding a minimum spanning tree
in a connected weighted graph is called the Minimum Spanning Tree Problem.
The importance of the Minimum Spanning Tree Problem is due to its applications in the design
of the computer, communications, and transportation networks.
Over the years, this problem has been solved in a variety of ways using a number of algorithms.
One of the best known was discovered by John Bernard Kruskal.
Kruskals Algorithm
For a connected weighted graph G, a spanning tree T of G is constructed as follows: For
the rst edge e
1
of T, we select any edge of G of minimum weight and for the second edge e
2
of T,
we select any remaining edge of G of minimum weight. For the third edge e
3
of T, we choose any
remaining edge of G of minimum weight that does not produce a cycle with the previously selected
edges. We continue in this manner until a spanning tree is produced.
Illustration
Chapter 5
Eulerian Trails and Circuits
Recall that a trail in a graph is a walk that does not repeat any edges, and that a closed trail (one
that begins and ends at the same vertex) is called a cicrcuit.
If a trail in a graph G includes every edge of G, then that trail is said to be an Eulerian trail.
Similarly, an Eulerian circuit in a graph is a circuit that includes every edge of the graph. A
graph that contains an Eulerian circuit is said to be an Eulerian graph.
There are two-well-known characterizations of Eulerian graphs. One involves vertex degrees, and
the other concerns the existence of a special collection of cycles.
Theorem 11. For a connected graph G, the following statements are equivalent.
1. G is Eulerian.
2. Every vertex of G has even degree.
3. The edges. of G can be partitioned into (edge-disjoint) cycles
Corollary 6. The connected graph G contains an eulerian trail if and only if there are at most
two vertices of odd degree.
37
Chapter 6
Modeling Using Graph Theory
6.1 Graph as Models
The Seven Bridges of Konigsberg
Eulers Problem (restated)
Given a graph, under what conditions is it possible to nd a closed walk that traverses every edge
exactly once?
We will call graphs for which this kind of walk is possible Eulerian.
What graphs are Eulerian? If you think for a moment, it is pretty clear that the graph has to
be connected- that is, there must be a path between every pair of vertices. Another observation
you might make is that whenever you walk over bridges between land masses and return to the
starting point, the number of times you enter a a land mass is the same as the number of times
you leave it. If you add the number of times you enter a specic land mass to the number of times
you leave it. If you add the number of times you enter a specic land mass to the number of times
you leave it, you therefore get an even number of eges incident with each vertex is needed. In the
language of graph theory, we say that every vertex has even degree or that the graph has even degree.
Thus we have reasoned that Eulerian graphs must be connected and must have even degree. In
other words, for a graph to be Eulerian, it is necessary that it both be connected and have an even
degree. But it is also true that for a graph to be Eulerian, it is sucient that it be connected with
even degree. Establishing necessary and sucient conditions between two concepts- in this case,
Eulrian graphs and all connected graphs with even degree - is an important idea in mathe-
matics with practical consequences. Once we establish that being connected with even degree is
necessary and sucient for a graph to be Eulerian, we need only model a situation with a graph,
and then check to see whether the graph is connected and each vertex of the graph has even degree.
Graph Coloring
Four-Color Problem Given a geographic map, is it possible to color it with four colors so that
any two regions that share a common border (of length greater than 0) are assigned dierent colors?
39
Figure 6.1: United States map
The four-color problem can be modeled with a graph. Figure 6.2 shows a map with a vertex rep-
resenting each state in the continental United States and an edge between every pair of vertices
corresponding to states that share a common (land) border. Note that Utah and New Mexico, for
example, are not considered sdjacent because their common border is only a point.
Figure 6.2: United States map with graph superimposed
The gure below shows the graph only. Now the original question we posed about the map of
the United States has been transformed into a question about a graph.
Four-Color Problem (restated) Using only four colors, can you color the vertices of a graph so
that no vertex gets the same color as an adjacent vertex?
Well call a coloring proper if no two adjacent vertices share the same color.
Figure 6.3 shows a solution to the four-color problem on the graph in Figure 6.2.
Figure 6.3: Graph-coloring solution
Application of Graph Coloring
One problem typically modeled with graph coloring is nal exam scheduling. Suppose that a
university has n courses in which a nal exam will be given and that it desires to minimize the
number of exam periods used, while avoiding conicts. A conict happens when a student is
scheduled for two exams at the same time. We can model this problem using a graph as follows.
We start by creating a vertex for each course. Then we draw an edge between two vertices when-
ever there is a student enrolled in both courses corresponding to those vertices. Now we solve the
graph-coloring problem; that is, we properly color the vertices of the resulting graph in a way that
minimizes the number of colors used. The color classes are the time periods. If some vertices are
colored blue in a proper coloring, then there can be no edges between any pair of them. This means
that no student is enrolled in more than one of the classes corresponding to these vertices. Then
each color class can be given in its own time slot.
Problems
1. Solve the softball managers problem (both versions) from the Introduction to this chapter.
2. The bridges and land masses of a certain city can be modeled with the graph G shown below.
(a) Is G Eulerian? Why or why not?
(b) Suppose we relax the requirement of the walk so that the walker need not start
and end at the same land mass but still must traverse every bridge exactly once. Is this
type of walk possible in a city modeled by the graph? If so, how? If not, why not?
3. Consider the graph shown below.
(a) Color the graph with three colors.
(b) Now suppose that vertices 1 and 6 must be colored red. Can you still color the graph
with three colors (including red) ?
4. The Mathematics Department at a small college plans to schedule nal exams. The class
rosters for all the upper-class math courses are listed in the table below. Find an exam
schedule that minimizes the number of time periods used.
Course Students
Math 350 Jimi B.B. Eric
Math 365 Ry Jimmy P. Carlos
Math 385 Jimi Chrissie Bonnie Brian
Math 420 Bonnie Robin Carlos
Math 430 Ry B.B. Buddy Robin
Matn 445 Brian Buddy
Math 460 Jimi Ry Brian Mark
Miscellaneous Problems
1. Consider the graph in the gure.
(a) Write down the set of edges of E(G).
(b) Which edges are incident with vertex b?
(c) Which vertices are adjacent to vertex c?
(d) Compute deg(a).
(e) Compute [E(G)[.
2. At a large meeting of business executives, lots of people shake hands. Everyone at the meeting
is asked to keep track of the number of times she or he shook hands, and as the meeting ends,
these data are collected. Explain why you will obtain an even number if you add up all the
individual handshake numbers collected. What does this have to do with graphs? Express
this idea using the notation introduced in this section.
Chapter 7
Selected Topics
7.1 Domination in Graphs
TERMINOLOGY. A vertex is said to dominate itself and each of its neighbors.
The applicability of domination theory to such elds as network design and analysis, linear
algebra, and optimization has attracted researchers from a broad range of disciplines. The origins
are ascribed to C. Berge and O. Ore.
Definition. Let G be a graph and let D V (G). A vertex subset D dominates a graph G
(or is a dominating set) if every vertex of G if every vertex of G is in D or is adjacent to at least
one vertex in D.
Definition. A minimal dominating set of a graph G is a dominating set such that every
proper subset is non-dominating.
Definition. The domination number of a graph G, denoted dom(G) ( elsewhere, often (G)))),
is the cardinality of a minimum dominating set of G.
Example. Figure shows a graph with minimal dominating sets (the solid vertices) of two dif-
ferent cardinalities. It is straightforward to show that the dominating set on the left is a minimum
one (i.e, there are no 2-vertex dominating sets). Thus, the dominating number of the graph is 3.
Figure 7.1: Two minimal dominating sets for a graph.
45
Example. For the 5-vertex path graph P
5
, we have dom(P
5
) = 2. The second and fourth vertices
on the path form the unique minimum dominating set.
Application. Chess.
Consider the problem of placing queens on a chessboard so that every square is either occupied by
a queen or can be reached in one move by a queen. Determining the minimum number of queens is
equivalent to nding the domination number of a 64 vertex graph, where two vertices are adjacent
if and only their corresponding squares lie on the same diagonal, same row, or same column.
Remark: Both dominating set in Figure are minimial, because each vertex in each set domi-
nates at least one vertex that no other vertex in that set dominates.
Exercises.
1. Find all minimum dominating sets of the following graph, and argue why there are no smaller
ones.
2. Determine the domination number of (a) the n-vertex path graph P
n
, (b) The n-vertex cycle
graph C
n
.
Answer: dom(P
n
) =

n
3

, since each vertex can dominate at most three vertices.

3. Determine the minimum number of knights that can be placed on a chessboard so that each
square is either occupied by a knight or can be reached in one move by a knight.
References
1. Harris, J., Hirst, J.,Mossingho, M.,Combinatorics and Graph Theory, Second Edition, Springer,
2008.
2. Agnarsson, G. and Greenlaw, R., Graph Theory: Modeling, Applications and Algorithms,
Pearson Education,Inc., 2007.
3. Wallis, W.D., A Beginners Guide to Graph Theory, 2nd Ed., Birkhauser Boston, 2007.
4. Gross, J. and Yellen, J., Graph Theory and Its Applications 2nd Ed., Chapman and Hall/CRC,
2006.
5. Chartrand, G. and Zhang, P. Introduction to Graph Theory, McGraw Hill, International
Edition, 2005.