Graph Theory

(MATH342)
Lecture Notes
Compiled by:
Dr. Z.B. Shozi

University of KwaZulu-Natal
School of Mathematics, Statistics & Computer Science
College of Agriculture, Engineering & Science
Office 430, H1 Building
Westville Campus
shoziz1@ukzn.ac.za
About Me
I am a lecturer in the School of Mathematics, Statistics & Computer Science at the University of
KwaZulu-Natal. My research interest is mainly in graph theory and group theory.

i
Contents

1 An Introduction to Graphs 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 What is a graph? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Examples of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Operations in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 The Degree of a Vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Isomorphic Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Connectivity 18
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Connected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Distance in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Cut-vertices and Bridges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 The Shortest Path Algorithm 29

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Distance in Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Trees 36
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Constructing Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5 Eulerian Graphs 45
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2 Eulerian Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3 Fleury’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.4 The Chinese Postman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6 Planar Graphs 55
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2 Properties of Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.3 The Four Colour Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

7 Hamiltonian Graphs 63
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2 Which Graphs Are Hamiltonian? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.3 The Closure Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

8 Networks 70
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
8.2 Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
8.3 An Introduction to Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8.4 The Max-Flow Min-Cut Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

ii
 8.5 The Max-Flow Min-Cut Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

References 87
1. An Introduction to Graphs
1.1 Introduction
Recent years have seen increased demand for application of mathematics. Graph theory has proven
to be particularly useful to a large number of rather diverse fields. The exciting and rapidly growing
area of graph theory is rich in theoretical results as well as applications to real-word problems. With the
increasing importance of the computer, there has been a significant movement away from the traditional
calculus courses and towards courses on discrete mathematics, including graph theory.
One of the primary activities of an applied mathematician is modelling. In a mathematical model, we
represent or identify a real-life situation or problem with a mathematical system. One of the best-known
examples of this representation is plane Euclidean geometry which gives useful results for describing
small regions, such as measuring distances.
For graph theorists, the modelling process involves formulating a problem in such a way that it can
be attacked by techniques of graph theory. This is not always easy; the way in which the modelling is
carried out, and the degree to which the mathematical model accurately represents the original problem,
varies considerably from problem to problem.
Many real-life situations can be described by means of a diagram consisting of a set of points with lines
joining certain pairs of points. Loosely speaking (we shall be more precise shortly), such a diagram is
what we mean by a graph. Graph theory is one area of mathematics that is particularly well-studied to
model building. The two main themes of this course are the development of graph theory as a subject
in its own right, and the modelling of problems.
Instances of graphs abound: for example, the points might represent cities with lines representing direct
flights between certain pairs of these cities in some airline system, or perhaps the lines representing
pipelines between certain pairs of these cities in an oil network. On the other hand, points might
represent factories with lines representing communication links between them. Electrical networks,
multiprocessor computers or switching circuits may clearly be represented by graphs. In chemistry,
graphs may sometimes be helpful in describing the structure of molecules. A chemical molecule can
be represented as a graph whose ’points’ correspond to the atoms and whose ’lines’ correspond to
the chemical bonds connecting them. The problem of counting the alkanes (paraffins) Cn H2n+2 is
essentially a tree-counting problem. (Trees are a class of graphs which we will study in Chapter 4).
For the sociologist, a graph depict the manner in which people (or groups of people) exert influence
over one another. Graphs can arise in several seemingly unrelated contexts, such as genetics, ecology,
archaeology, music, and the phasing of traffic lights. In order to investigate such relationships more
deeply, we need to study the theory of graphs in greater detail.
An important part of learning graph theory is problem solving, and for this reason a number of problems
at the end of most sections have been included. Many of these are routine exercises, designed to test
understanding of the material in this text, but some are more challenging and less routine. The large
variety of proofs used in the course can help strengthen our use of mathematical techniques.

1.2 What is a graph?

The common feature in all the preceding examples is that we have a collection of ’objects’ (cities,
factories, atoms) which are interrelated in some way. These ideas are easily abstracted to produce the

1
Section 1.2. What is a graph? Page 2

concept of a graph.
Definition 1.2.1 (Graph).
A graph G is a finite nonempty set of objects, called vertices (the singular is vertex), together with
a (possibly empty) set of unordered pairs of distinct vertices, called edges. The set of vertices of the
graph G is called vertex set of G, denoted by V (G), and the set of edges is called edge set of G,
denoted by E(G). The edge e = {u, v} is said to join the vertices u and v. If e = {u, v} is an edge
of G, then u and v are adjacent vertices, while u and e are incident, as are v and e. Furthermore, if
e1 and e2 are distinct edges of G incident with a common vertex, then e1 and e2 are adjacent edges.
It is convenient to henceforth denote an edge by uv or vu rather than by {u, v}. The cardinality of
the vertex set of a graph G is called the order of G and is denoted by n(G), or more simply by n
when the graph under consideration is clear, while the cardinality of the edge set is the size, denoted
by m(G) or m. An (n, m) graph has order n and size m. The graph of order n = 1 is called a trivial
graph. A nontrivial graph has at least two vertices.

It is customary to define or describe a graph by means of a diagram in which each vertex is represented
by a point (which we draw as a small circle) and each edge edge e = uv is represented by a line segment
or curve joining the points corresponding to u and v.

Figure 1.1: A graph G.

To illustrate these definitions, consider the graph G defined by the sets V (G) = {v1 , v2 , v3 , v4 } and
E(G) = {v1 v2 , v2 v3 , v2 v4 , v3 v4 }. A diagram of this graph is shown in Figure 1.1. This graph has order
4 and size 4. Furthermore, observe that v1 and v2 are adjacent, but v1 and v3 are not adjacent. The
vertex v2 is incident to the edge v2 v3 , but v4 is not incident to v2 v3 . The edges v1 v2 and v2 v3 are
adjacent, but v1 v2 and v3 v4 are not adjacent.
We also need the concept of a subgraph of a graph. It is a common feature of mathematics that we
study complicated objects by looking at simpler objects of the same type contained inside them, and
these smaller objects are often indicated by the prefix “sub”. For example, we study subsets of sets,
subsystems of systems, and so on. In graph theory, we make the following definition.
Section 1.2. What is a graph? Page 3

Definition 1.2.2 (Subgraph).

A subgraph of a graph G is a graph all of whose vertices belong to V (G) and all of whose edges edges
belong to E(G). If H is a subgraph of G, then we write H ⊂ G. If a subgraph H of G contains all
the vertices of G, then H is called a spanning subgraph of G.

For example, if G is the graph shown in Figure 1.1, then the graphs H1 , H2 and H3 shown in Figure
1.2 are all subgraphs of G. (Note that G is regarded as a subgraph of itself)

Figure 1.2: Subgraphs of the graph G.

An important type of a subgraph that we shall encounter is the induced subgraph.

Definition 1.2.3 (Induced Subgraph).
If W is a nonempty subset of vertices of a graph G, then the subgraph G[W ] of G induced by W is
the graph having vertex set W and whose edge set consists of all those edges of G incident with two
vertices in W . A subgraph H of a graph G is called a vertex-induced subgraph, or simply induced
subgraph, of G if H = G[W ] for some subset W of V (G). Hence if H is an induced subgraph of
G, then every edge of G incident with two vertices in V (H) belongs to E(H) (so two vertices are
adjacent in H if and only if they are adjacent in G). Similarly, if F is a nonempty subset of edges of
G, then the subgraph G[F ] induced by F is the graph whose vertex set consist of all those vertices
of G incident with an edge in F and whose edge set is F . A subgraph H of a graph G is called an
edge-induced subgraph of G if H = G[F ] for some subset F of E(G).

For example, if G is the graph shown in Figure 1.1, and H1 and H2 are the subgraphs of G shown in
Figure 1.2, then H1 = G[F ] and H2 = G[W ], where F = {v1 v2 , v3 v4 } and W = {v2 , v3 , v4 }.
Section 1.2. What is a graph? Page 4

Learning Opportunities
1.1. Draw the graph with vertex set V = {v1 , v2 , v3 , v4 , v5 } and edge set E = {v1 v2 , v1 v4 , v1 v5 , v2 v3 ,
v3 v5 , v4 v5 }.
1.2. Write down the vertex set and the edge set of the following graph:

1.3. Which of the following graphs are subgraphs of the graoh G in Learning Opportunity 1.2.?

1.4. Six Sol Plaatje University teams A, B, C, D, E and F belong to the same league and have played
a number of matches: A has played C, D and E; B has played C and E; C has played A, B and
D; D has played A, C and E; E has played A, B and D; F has not yet played. Let G be a graph
with vertex set V (G) = {A, B, C, D, E, F } and let two vertices of G be adjacent if and only if
the corresponding teams have played a match.
1.4.1. Write down E(G), the set of edges of the graph G.
1.4.2. Draw the graph G.
Section 1.3. Examples of Graphs Page 5

1.5. What is the maximum possible size of a graph of

1.5.1. order 3?
1.5.2. order 4?
1.5.3. order 5?
1.5.4. order n, where n is a positive integer?
1.6. For each of the properties listed below, find a graph G that has the given property:
1.6.1. Every vertex of G is adjacent to two vertices and every edge of G is adjacent to two edges.
1.6.2. Every two vertices of G are adjacent and every two edges of G are adjacent.
1.5.3. Every vertex of G is incident with an edge, but no two edges of G are adjacent.

1.3 Examples of Graphs

There are a certain classes of graphs that occur so often that they deserve special mention and in some
cases, special notation.
Definition 1.3.1 (Complete Graph).
A complete graph or clique is a graph in which every two distinct vertices are adjacent. The complete
graph of order n is denoted by Kn and is called an n-clique.

Figure 1.3: Complete graphs

Definition 1.3.2 (Empty Graph).

The empty graph is a graph containing no edges. The empty graph of order n is denoted by Kn .

Figure 1.4: Empty graphs

Of particular importance in applications are bipartite graphs.

Section 1.3. Examples of Graphs Page 6

Definition 1.3.3 (Bipartite Graph).

A bipartite graph is a graph whose vertex set can be partitioned into two sets V1 and V2 (called
partite sets) in such a way that each edge of the graph joins a vertex of V1 to a vertex of V2 .

We can distinguish the vertices in V1 from those in V2 by drawing the former in blue and the latter in
white, so each edge is incident with a blue vertex and a white vertex. Some examples of bipartite graphs
are shown below.

Figure 1.5: Bipartite graphs

Definition 1.3.4 (Complete Bipartite Graph).

A complete bipartite graph is a bipartite graph with partite sets V1 and V2 having the added property
that every vertex of V1 is adjacent to a vertex of V2 (so each blue vertex is joined to each white vertex).
If |V1 | = r and |V2 | = s, then this graph is denoted by K(r, s), or more commonly, Kr,s . A complete
bipartite graph of the form K1,s is called a star graph. A complete bipartite graph Kn,n is called an
n-biclique.

Some examples of complete bipartite graphs are shown below.

Figure 1.6: Complete bipartite graphs

A graph G is k-partite, k ≥ 2 if its vertex set V (G) can be partitioned into k subsets V1 , V2 , . . . , Vk
(called partite sets) in such a way that each edge of G joins a vertex of Vi to a vertex of Vj , i ̸= j.
A complete k-partite graph is a k-partite graph with partite sets V1 , V2 , . . . , Vk having the added
property that every vertex of Vi is adjacent to every vertex of Vj for 1 ≤ i < j ≤ k. If |Vi | = ni , then
this graph is denoted by K(n1 , n2 , . . . , nk ). If ni = n for all i, then we denote this graph simply by
Kk (n). A graph is a complete multipartite graph if it is a complete k-partite graph for some k ≥ 2.
Section 1.4. Operations in Graphs Page 7

Learning Opportunities
1.7. Draw the following graphs:
1.7.1. K6
1.7.2. K4,4
1.7.3. K2,5
1.8. How many edges does a complete bipartite graph Km,s have?

1.4 Operations in Graphs

There are several operations we can perform om graphs in order to form new ones. The simplest of
these is to form their union. In the following definitions, we assume G1 and G2 are two graphs with
disjoint vertex sets.
Definition 1.4.1 (Union).
The union G = G1 ∪ G2 has V (G) = V (G1 ) ∪ V (G2 ) and E(G) = E(G1 ) ∪ E(G2 ). If a graph G
consists of k (≥ 2) disjoint copies of a graph H, then we write G = kH.

The graph 2K1 ∪ 3K2 ∪ K1,3 is shown in Figure 1.7:

Figure 1.7: The union of graphs

Definition 1.4.2 (Join).

The joint G = G1 + G2 has V (G) = V (G1 ) ∪ V (G2 ) and E(G) = E(G1 ) ∪ E(G2 ) ∪ {vw | v ∈
V (G1 ) and w ∈ V (G2 )}.

The graph G = G1 + G2 = K2 + K3 is shown in Figure 1.8:

Section 1.4. Operations in Graphs Page 8

Figure 1.8: The join of two graphs

Definition 1.4.3 (Cartesian Product).

The Cartesian product G = G1 × G2 has V (G) = V (G1 ) × V (G2 ) and two vertices (v1 , v2 ) and
(w1 , w2 ) are adjacent if, and only if, either

v1 = w1 and v2 w2 ∈ E(G2 )

or

v2 = w2 and v1 w1 ∈ E(G1 ).

The Cartesian product of G1 × G2 can be constructed by placing a copy of G2 at each vertex of G2

and adding the appropriate edges. For example, K2 × K3 is shown in Figure 1.9:

Figure 1.9: The Cartesian product of two graphs

Definition 1.4.4 (Complement).

If G is a graph, we form its complement G by taking the vertex set of G and joining two vertices by
an edge whenever they are not joined in G.
Section 1.5. The Degree of a Vertex Page 9

For example, the compliment of Kn is Kn . Figure 1.10 shows a graph G and its compliment G. Note
that if we take the complement of G, then we get back the original graph G.

Figure 1.10: A graph and its complement

Learning Opportunities
1.9. Draw the following graphs:
1.9.1. 3K3
1.9.2. K2,2 × K2
1.9.3. K2,3
1.10. For i = 1, 2, let Gi be an (ni , mi )-graph. Determine the order and size of G1 × G2 in terms of
n1 , n2 , m1 , m2 .

1.5 The Degree of a Vertex

We have already introduced two numbers associated with a graph G, namely the order and the size of
G. Now we define a collection of numbers associated with G.
Definition 1.5.1 (Degree).
Let v be a vertex of a graph G. The degree of v is the number of edges of G incident with v. The
degree of v is denoted by degG v, or simply deg v if G is clear from the context. The minimum degree
of G is the minimum degree among the vertices of G and is denoted by δ(G), while the maximum
degree of G is the maximum degree among the vertices of G and is denoted by ∆(G). A vertex is
called odd or even depending on whether its degree is odd or even. A vertex of degree 0 in G is called
an isolated vertex of G. A vertex of degree 1 in G is called an end-vertex of G. A vertex adjacent
to an end-vertex in G is called a remote vertex of G.

In Figure 1.11, a graph is shown together with the degrees of its vertices.
Section 1.5. The Degree of a Vertex Page 10

Figure 1.11: The degrees of the vertices of a graph.

Definition 1.5.2 (Regular Graph).

We say that a graph is regular if all its vertices have the same degree. In particular, if the degree of
each vertex is r, then the graph is called r-regular.

Figure 1.12: Some regular graphs

Observe that for the graph G in Figure 1.11, n(G) = 10 and m(G) = 11, while the sum of the degrees
of its vertices is 22. The fact that this last number equals 2m(G) is no mere coincidence, as we now
show.
Theorem 1.5.3 (Handshaking Lemma).
In any graph, the sum of all the vertex degrees is equal to twice the number of edges.
Proof. Every edge is incident with two vertices; hence, when the degrees of the vertices are summed,
each edge is counted twice.

The above theorem is sometimes called the handshaking lemma. This name arises from the fact that
a graph can be used to represent a group of people shaking hands at a party. In such a graph, the
people are represented by the vertices, and an edge is included whenever the corresponding people have
shaken hands. With this interpretation, the number of edges represents the total number of handshakes,
the degree of a vertex is the number of hands shaken by the corresponding person, and the sum of the
degrees is the total number of hands shaken. So the handshaking lemma states simply that the total
number of hands shaken is equal to twice the number of handshakes–the reason being, of course, that
Section 1.5. The Degree of a Vertex Page 11

exactly two hands are involved in each handshake. There are some important consequences of the
handshaking lemma.
Corollary 1.5.4.
In any graph, there is an even number of odd vertices.
Proof. Let G be a graph of order n and size m. If G has no odd vertices, then the result follows
immediately. Suppose that G contains k(≥ 1) odd vertices v1 , v2 , . . . , vk . If G contains even vertices
as well, then denote these by vk+1 , . . . , vn . By Theorem 1.5.3,
k
X n
X
deg vi + deg vi = 2m.
i=1 i=k+1
n
X
Since each of the numbers deg vk+1 , . . . , deg vn is even, deg vi is even, so
i=k+1

k
X n
X
deg vi = 2m − deg vi
i=1 i=k+1

is even. However, each of the numbers deg v1 , deg v2 , . . . , deg vk is odd. Since the sum of an odd
number of odd numbers is odd, it follows that k must be even; that is, G has an even number of odd
vertices. If G has no even vertices, then we have deg v1 , deg v2 + · · · + deg vk = 2m, from which we
again conclude that k is even.

It is often convenient to list the degrees of vertices of a graph; this is usually done by writing them in
nonincreasing order (that is, in decreasing order but allowing ’repeats’ where necessary). The resulting
list is called the degree sequence of a graph. Given a graph G, the degree sequence of G can be easily
determined (we simply find the degree of each of its vertices). For example, the graph in Figure 1.11
has degree sequence 5, 4, 3, 3, 2, 2, 1, 1, 1, 0. Several interesting questions about degree sequence now
come to mind.
The first question you might think of is, can we reverse this process? By this we mean, given a degree
sequence s, can we determine a graph with s as a degree sequence? Perhaps a better question is: Can
we determine when a sequence of integers represents the degree sequence of a graph? This leads us to
the following definition.
Definition 1.5.5 (Graphical).
A sequence of integers is said to be graphical if it is the degree sequence of some graph. A graph G
with degree sequence s is called a realization of s.

Let us begin with the question: When is a sequence s : d1 , d2 , . . . , dn of integers the degree sequence
of some graph? Certain conditions are clearly important. First, degrees are nonnegative integers, so
di ≥ 0 for all i. Next, di ≤ n − 1, because no vertex in a graph of order n can be adjacent to more
than n − 1 vertices. Furthermore, Theorem 1.5.3 tells us that the sum of the degrees of the vertices
n
X
in any graph must be an even number, so di is even. The above three conditions are all necessary
i=1
for a sequence to be graphical, but these conditions are not sufficient. The sequence 3, 3, 3, 1 is not
graphical, for example. A necessary and sufficient condition for a sequence to be graphical was found
by Havel [16] (1955) and later rediscovered by Hakimi [15] (1962).
Section 1.5. The Degree of a Vertex Page 12

Theorem 1.5.6 (Havel-Hakimi).

A nonincreasing sequence of nonnegative integers s : d1 , d2 , . . . , dn is graphical if and only if the
sequence s1 : d2 − 1, d3 − 1, . . . , dd1 +1 − 1, dd1 +2 , . . . , dn (n ≥ 2) is graphical.
Proof. Suppose that the sequence s1 is graphical. Let G1 be a graph of order n − 1 with degree
sequence s1 . Then the vertices of G1 can be labelled as v2 , v3 , . . . , vn in such a way that deg vi = di − 1
if 2 ≤ i ≤ d1 + 1 and deg vi = di if d1 + 2 ≤ i ≤ n. We can now construct a new graph G from G1 by
adding a new vertex v1 and then joining v1 with an edge to each of v2 , v3 , . . . , vd1 +1 . The degree of v1
is d1 , and the degree of the other vertices are the remaining values of s. Thus, we have constructed a
graph with degree sequence s, and so s is graphical.
We show next that if s is graphical, then s1 is graphical. Assume that s is a graphical sequence.
Therefore, there are one or more graphs of order n with degree sequence s. Among all such graphs, let
G be one such that V (G) = {v1 , v2 , . . . , vn }, where deg vi = di for all 1 ≤ i ≤ n, and the sum of the
degrees of the vertices adjacent with v1 is maximum.
We show that in G, the vertex v1 must be adjacent with the vertices having degrees d2 , d3 , . . . , dd1 +1 .
If this is not the case, then there must exist two vertices vj and vk with dj > dk such that v1 is adjacent
to vk , but not to vj . Since the degree of vj exceeds that of vk , there must be some vertex vl such
that vl is adjacent to vj , but not to vk . Removing the edges v1 vk and vj vl and adding the edges v1 vj
and vk vl produces a new graph G′ that also has degree sequence s. However, in G′ the sum of the
degrees of the vertices adjacent with v1 is larger than that in G, contradicting our choice of G. This
contradiction argument verifies that our initial assumption (namely, that v1 is not adjacent with vertices
having degrees d2 , d3 , . . . , dd1 +1 ) was false.
Thus, as claimed, v1 must be adjacent with vertices having degrees d2 , d3 , . . . , dd1 +1 . Hence, the graph
obtained from G by removing v1 , together with all the edges incident with v1 , produces a graph with
degree sequence s1 , so s1 is graphical.

With the aid of Theorem 1.5.6, we may now present a procedure, or algorithm, that allows us to
determine whether a finite sequence of nonnegative integers is graphical or not.
Algorithm 1.5.7 (Havel-Hakimi).
Given a sequence of n(≥ 1) nonnegative integers:
1. If some integer in the sequence exceeds n − 1, the the sequence is not graphical.
2. If all the integers in the sequence are 0, then the sequence is graphical.
3. If the sequence contains a negative integer, then the sequence is not graphical.
4. Reorder the sequence (if necessary) so that it is nonincreasing.
5. Delete the first number, say t, from the sequence and subtract 1 from the next t numbers in the
sequence to form a new sequence. Return to step 2.
To illustrate Algorithm 1.5.7, consider the sequence:

s : 4, 4, 4, 3, 3, 2.

Step 1 is satisfied, and we begin the loop of Step 2 to 5. The tests in Step 2 and 3 do not immediately
halt us. Proceeding to Step 5, we get

s′1 = 3, 3, 2, 2, 2
s1 = 3, 3, 2, 2, 2. re-orderring
Section 1.5. The Degree of a Vertex Page 13

Continuing to apply Algorithm 9.5.7, we have

s′2 = 2, 1, 1, 2
s2 = 2, 2, 1, 1. re-orderring

s′3 = 1, 0, 1
s3 = 1, 1, 0. re-orderring

s′4 = 0, 0
s4 = 0, 0. re-orderring

Algorithm 9.5.7 shows that s is graphical, since 0, 0 is the degree sequence of the empty graph K2 on
two vertices.
To construct a graph with degree sequence s1 , we proceed in reverse from s′2 to s1 , observing that a
vertex should be added to G2 so that it is adjacent to one vertex of degree 2 and two vertices of degree
1 in G2 . We therefore obtain a graph G1 with degree sequence s1 . Proceeding from s′1 to s, we again
add a new vertex joining it to two vertices of degree 3 and two vertices of degree 2 in G1 . This gives a
graph G with degree sequence s.

Figure 1.13: Construction of a a graph G with a given degree sequence.

It should be pointed out that the graph G in Figure 1.13 is not the only graph with degree sequence
s. The graphs G and H in Figure 1.14 both have the same degree sequence, namely 2, 2, 2, 2, 2, 2. So
degree sequences do not always provide enough information to uniquely describe a graph.

Figure 1.14: Two graphs with the same degree sequence 2, 2, 2, 2, 2, 2.

Learning Opportunities
1.11. For the graph G in the accompanying figure, write down the degrees of all the vertices and the
degree sequence of G. Verify the handshaking lemma for the graph G.
Section 1.6. Isomorphic Graphs Page 14

1.12. Suppose we know the degrees of the vertices of a graph G.

1.12.1. Is it possible to determine the order of G? Explain.
1.12.2. Is it possible to determine the size of G? Explain.
1.13. Show that in any group of at least two people, there must be two who have exactly the same
number of acquaintances in the group.
1.14. Suppose you and your partner attend a party with three other couples. Several handshakes took
place. No one shook hands with himself (or herself) or his (or her) partner, and no on shook hands
with the same person more than once. After all the handshaking was completed, suppose you
asked each person, including your partner, how many hands he or she had shaken. Each person
gave a different answer.
1.14.1. How many hands did you shake?
1.14.2. How many hands did your partner shake?
1.15. Prove that if G is a regular bipartite graph with partite sets V1 and V2 , then |V1 | = |V2 |.
1.16. Determine whether each the following sequences is graphical. If so, construct a graph with the
appropriate degree sequence.
1.16.1. 5, 5, 5, 3, 3, 2, 2, 2, 2, 2
1.16.2. 4, 4, 2, 1, 0
1.16.3. 3, 3, 2, 2, 2, 2, 1, 1
1.16.4. 7, 4, 3, 3, 2, 2, 2, 1, 1, 1
1.17. Show that the degree sequence d1 , d2 , . . . , dn is graphical if and only if the sequence n − d1 −
1, n − d2 − 1, . . . , n − dn − 1 is graphical. (Hint : Consider a graph and its complement.)

1.6 Isomorphic Graphs

In every area of mathematics, it is important to know whether two objects under investigation are the
same (in some sense) or are different. For example, the numbers 2 and 63 are considered to be the same,
or equal, but they are not identical. We now wish to determine what conditions must hold two graphs
to be the ’same’. Intuitively, two graphs G1 and G2 are the same if it is possible to redraw one of them,
Section 1.6. Isomorphic Graphs Page 15

say G2 , so it appears identical to G1 . For example, the graphs G1 and G2 of Figure 1.15 have this
property.

Figure 1.15: Isomorphic graphs.

Two graphs often have the same structures differing only in the way their vertices edges are labelled
or in the way they are drawn. To make this idea more exact, we introduce the following concept of
isomorphism.
Definition 1.6.1 (Isomorphism).
Two graphs G and H are isomorphic if H can be obtained from G by relabelling the vertices– that is,
there is a one-to-one correspondence between the vertices of G and those of H such that an edge joins
any pair of vertices in G if and only if the edge joins the corresponding pair of vertices in H. Hence
G is isomorphic to H if there exists a one-to-one mapping ϕ, called an isomorphism from V (G) to
V (H) such that ϕ preserves adjacency; that is, uv ∈ E(G) if and only if ϕ(u)ϕ(v) ∈ E(H). If G and
H are isomorphic, then we write G ∼ = H. Two graphs are nonisomporphic if they are not isomorphic.

Figure 1.16: Isomorphic and nonisomorphic graphs.

Section 1.6. Isomorphic Graphs Page 16

Example 1.6.2 (Isomorphism).

The graphs G1 and G2 in Figure 1.16 are isomorphic. For example, the mapping ϕ : V (G1 ) −→ V (G2 )
defined by

ϕ(v1 ) = v1 , ϕ(v2 ) = v3 , ϕ(v3 ) = v5 , ϕ(v4 ) = v2 , ϕ(v5 ) = v4 , ϕ(v6 ) = v6

is an isomorphism. On the other hand, although each of G1 and G3 is a (6, 9) graph, G1 ≇ G3 . To see
this, consider any one-to-one mapping ϕ from V (G1 ) to V (G3 ). The vertices v1 , v2 and v3 of G3 are
pairwise adjacent, and ϕ must map three vertices of G1 into v1 , v2 and v3 . If ϕ is an isomorphism, then
two vertices of G1 are adjacent if and only if the two image vertices of G3 under ϕ are adjacent. This
implies that the three vertices of G1 whose images are v1 , v2 and v3 also must be pairwise adjacent;
however, G1 does not contain three pairwise adjacent vertices. Hence there is no isomorphism from
V (G1 ) to V (G3 ). Thus G1 ≇ G3 .

Definition 1.6.3 (Identical Graphs).

Two graphs G and H are identical, denoted G = H, if V (G) = V (H) and E(G) = E(H).

Clearly, two graphs may be isomorphic yet not identical. The graphs G1 and G2 of Figure 1.16 are
not identical (even though V (G1 ) = V (G2 ) and G1 ∼= G2 ) since, for example v1 v5 ∈ E(G1 ) and
v1 v5 ∈
/ E(G2 ).

Learning Opportunities
1.18. Determine all (pairwise nonisomorphic) graphs of
1.18.1. order 3.
1.18.2. order 4.
1.19 Show that the graphs F1 and F2 are isomorphic by proving the existence of an isomorphism from
F1 to F2 or of an isomorphism from F2 to F1 .

1.20. Show that the following two graphs G and H are isomorphic.
Section 1.6. Isomorphic Graphs Page 17

1.21. Are the following graphs G and H isomorphic?

1.22. Classify each of the following statements as true or false.

1.22.1. If G and H are isomorphic graphs, then they have the same order and size.
1.22.2. If G and H have the same order and size, then they are isomorphic.
1.22.3. If G and H are isomorphic graphs, then they have the same degree sequence.
1.22.4. If G and H have the same degree sequence, then they are isomorphic.
2. Connectivity
2.1 Introduction
Many of the applications of graph theory involve getting from one vertex to another in a graph. For
example, how can you find the shortest route between the city of Kimberley and the city of Durban?
How do you determine the best route for postal deliveries? In order to formulate general methods for
solving such problems, we need to investigate the concept of connectedness in a graph; that is, a
property of a graph which enables us to proceed from one vertex to another by a sequence of edges.

2.2 Connected Graphs

We start this section by defining a walk in a graph.
Definition 2.2.1 (A Walk).
Let u and v be two (not necessarily distinct) vertices of a graph G. A u-v walk in G is a finite,
alternating sequence of vertices and edges that begins with the vertex u and ends with the vertex v
and in which each edge of the sequence joins the vertex that precedes it in the sequence to the vertex
that follows it in the sequence. The number of edges in the walk is called the length of the walk.

Note that we do not require all edges or vertices in a walk to be different. Often only the vertices of a walk
are listed, for the edges present are then obvious. For example, v3 , v3 v2 , v2 , v2 v6 , v6 , v6 v3 , v3 , v3 v4 , v4 , v4 v5 ,
v5 , v5 v4 , v4 is a v3 -v4 walk in the graph G of Figure 2.1. The walk just described can be expressed more
simply as v3 , v2 , v6 , v3 , v4 , v5 , v4 . This walk has length 6.

Figure 2.1

18
Section 2.2. Connected Graphs Page 19

Definition 2.2.2 (Trail, Path).

If all the edges (but not necessarily vertices) of a walk are different, then the walk is called a trail. If,
in addition, all the vertices are different, then the trail is called a path. We consider a single vertex as
trivial path (walk or trail).

The v3 -v4 walk described above is not a trail (since the edge v4 v5 occurs twice). However, v3 , v2 , v6 , v3 , v4
is a v3 -v4 trail in the graph G of Figure 2.1. This trail is not a path (since the vertex v3 is repeated).
However, v3 , v5 , v4 is a v3 -v4 path. It is useful to have a special terms for those walks or trails which
start and finish at the same vertex.
Definition 2.2.3 (Closed Walk, Closed Trail).
A u-v walk is closed if u = v and open otherwise. A closed walk in which all the edges are different is
a closed trail. A closed trail which contains at least three vertices is called a circuit. A circuit which
does not repeat any vertices (except the first and last) is called a cycle. An acyclic graph has no
cycles. The length of a cycle (or circuit) is the number of edges in the cycle (or circuit). A cycle of
length n is an n-cycle. A 3-cycle is called a triangle. A cycle is even if its length is even, otherwise
it is odd.

In the graph G of Figure 2.2, v1 , v2 , v3 , v4 , v5 , v2 , v6 , v1 is a circuit (of length 7) that is not a cycle,
while v2 , v4 , v3 , v5 , v2 is a cycle (as well as a circuit) of length 4.

Figure 2.2

By definition, every path is a trail and every trail is a walk. Although the converse of each of these
statements fails to hold, we do have a result that relates walks and paths.
Theorem 2.2.4 (Walks, Paths).
Every u-v walk in a graph contains a u-v path.
Proof. Let W be a u-v walk in a graph G. If W is closed, then the result is easy; we simply use the
trivial path u. Thus, assume W is an open walk, say W : u = u0 , u1 , u2 , . . . , uk = v. Note that a
vertex may have received more than one label if it occurs more than once in W . If no vertex is repeated,
Section 2.2. Connected Graphs Page 20

then W is already a path. Otherwise, there are vertices of G that occur in W twice or more. Let i and
j be distinct integers with i < j such that ui = uj . That is, the vertex ui is repeated as uj . If we now
delete the vertices ui , ui+1 , . . . , uj−1 from W , we obtain a u-v walk W1 which is shorter than W and
has fewer repeated vertices. If W1 is a path, we are done; if not, we continue this process until finally
we reach a stage where no vertices are repeated and a u-v path is obtained.

Before proceeding further, we mention two special classes of graphs.

Definition 2.2.5 (Path Graph).
A path graph is a graph consisting of a single path. The path of order n is denoted by Pn .

Figure 2.3

Definition 2.2.6 (Cycle Graph).

A cycle graph is a graph consisting of a single cycle. The cycle of order n is denoted by Cn (n ≥ 3).

Figure 2.4

Definition 2.2.7 (Connected, Disconnected).

A graph G is connected if there exists a path in G between any two of its vertices, and it is dis-
connected otherwise. Every disconnected graph can be split up to a number of connected subgraphs
called components. A component of a graph G is a maximal connected subgraph of G. Two vertices
u and v in a graph G are connected if u = v, or if u ̸= v and a u-v path exists in G. The number of
components of G is denoted by k(G); of course, k(G) = 1 if and only if G is connected.

For the graph G of Figure 2.5, k(G) = 6.

Section 2.2. Connected Graphs Page 21

Figure 2.5: A graph G with six components.

Learning Opportunities
2.1. Give an example of a disconnected graph with four components where each component is complete.
2.2. Give an example of a disconnected graph with three components where every two components are
isomorphic.
2.3. Consider the graph G below:

Give an example of
2.3.1. a circuit which is not a cycle;
2.3.2. a trail which is not a path;
2.3.3. a path;
2.3.4. a cycle.
2.4. Show that if G is a graph with minimum degree δ ≥ 2, then G contains a cycle of length at least
δ + 1. (Hint: Consider a longest path P in G. Let u be an end-vertex of P and consider the
vertices adjacent to u in G.)
2.5. Show that if G is a bipartite graph with minimum degree δ ≥ 1, then G contains a path of order
at least 2δ.
2.6. Prove that a graph and its complement cannot be both disconnected.
2.7. A graph is self-complementary if it is isomorphic to its complement.
Section 2.3. Distance in Graphs Page 22

2.7.1. Show that C5 is self-complementary.

2.7.2. Prove that a self-complementary graph has 4k or 4k + 1 vertices, for some integer k (that
is, if G is self-complementary of order n, then n ≡ 0 mod 4 or n ≡ 1 mod 4).
2.8. Let G be a graph of even order n (i.e., n = 2k for some positive integer k) such that G has two
complete components. Prove that the minimum size possible for G is

n2 − 2n
m= .
4
(Hint : Try a calculus argument). If G has this size, what does G look like?
2.9. Let G be a graph of order n such that deg v ≥ n−1
2 for every v ∈ V (G). Prove that G is connected
(Hint: Try a proof by contradiction: Assume, to the contrary, that G is disconnected. This
means that G has two or more components. What can be said about the number of vertices in
each component?)
n−2
2.10. Let G be a graph of order n ≥ 2 such that deg v ≥ 2 for every v ∈ V (G). Show that G need
not be connected if n is even.
2.11. Suppose that G is a graph having no vertex of degree 0 and no induced subgraph with exactly
two edges. Prove firstly that G is connected. Hence prove that G is a complete graph.
2.12. Suppose that G is a connected graph having no vertex of degree 0 and no induced subgraph with
exactly three edges. Prove that G has maximum degree 2. Hence prove that G has at most four
vertices.

2.3 Distance in Graphs

The distance between two vertices in a graph is defined as follows:
Definition 2.3.1 (Distance in Graphs).
For a connected graph G, we define the distance d(u, v) between two vertices u and v as the minimum
of the lengths of the u − v paths of G. If G is a disconnected graph, then the distance between two
vertices of the same component of G is defined as above. However, if u and v belong to different
components of G, then d(u, v) is undefined (or we could define d(u, v) = ∞).

For the graph G of Figure 2.6, d(x, u) = 2, d(x, w) = 3 while d(x, v) = 5.

Figure 2.6
Section 2.3. Distance in Graphs Page 23

The distance function d(u, v) on pairs of vertices is a metric, that is, it satisfies the following fundamental
properties:
Theorem 2.3.2 (The Distance Function).
Let G be a graph and let u, v, w ∈ V (G). Then
(i) d(u, v) ≥ 0 and d(u, v) = 0 if and only if u = v;
(ii) d(u, v) = d(v, u) (symmetric property);
(iii) d(u, v) ≤ d(u, w) + d(w, v) (triangle inequality).

The proof of Theorem 2.3.2 is left as an exercise (see Learning Opportunity 2.13). We now present a
useful characterization of bipartite graphs.
Theorem 2.3.3 (Characterization of Bipartite Graphs).
A nontrivial graph is bipartite if and only if it contains no odd cycles.
Proof. Let G be a bipartite graph with partite sets V1 and V2 . Suppose C : v1 , v2 , . . . , vk , v1 is a cycle
of G. Without loss of generality, we may assume that v1 ∈ V1 . However, then v2 ∈ V2 , v3 ∈ V1 ,
v4 ∈ V2 , and so on. In general, v2i ∈ V2 and v2i−1 ∈ V1 . This implies that, since vk ∈ V2 , k = 2s for
some positive integer s; hence, C has even length.
For the converse, it suffices to prove that every nontrivial connected graph G without odd cycles is
bipartite, since a nontrivial graph is bipartite if and only if each of its components is bipartite. Let
v ∈ V (G) and denote by V1 the subset of V (G) consisting of v and all vertices u of G with the property
that any shortest u − v path of G has even length. Let V2 = V (G) − V1 . Thus

V1 = {u ∈ V (G) | d(u, v) is even}

and
V2 = {u ∈ V (G) | d(u, v) is odd}.

We now prove that the partition V1 ∪ V2 of V (G) has the appropriate properties to show that G is
bipartite. Let u and w be elements of V1 , and suppose uw ∈ E(G). Necessarily, then, neither u nor w
is the vertex v. Let P : v = u1 , u2 , . . . , v2r+1 = u, r ≥ 1, and Q : v = w1 , w2 , . . . , w2s+1 = w, s ≥ 1,
be a shortest v − u path and a shortest v − w path of G, respectively. Now let w′ denote the last vertex
that the two paths P and Q have in common (possibly, w′ = v). This means that the w′ − u subpath
of P and the w′ − w subpath of Q have only the vertex w′ in common. The two v − w′ subpaths so
determines are then the shortest v − w′ paths (for otherwise, we may find a shorter v − u path or v − w
path than P or Q, respectively.) This means that there exists an i such that w′ = ui = wi . However,
proceeding for ui to u along the path P , and then from u to w along the edge uw, and following the
path Q from w back to wi (= ui ) produces a cycle of G, namely

ui , ui+1 , . . . , u2r+1 , w2s+1 , w2s , . . . , wi = ui .

This cycle has length (2r + 1 − i) + (2s + 1 − i) = 2(r + s + 1 − i) + 1, which is odd. We have
shown, therefore, that G contains an odd cycle, which is a contradiction to our hypothesis. We deduce,
therefore, that no two vertices of V1 are adjacent. Similarly, no two vertices of V2 are adjacent. Hence
G is a bipartite graph with partite sets V1 and V2 .

Applications of distance in graphs abound. For example, suppose a town planning committee wishes to
locate certain facilities, such as a fire or police station, in such a way as to minimise the response time
Section 2.3. Distance in Graphs Page 24

between the facility and the location of a possible emergency. How would the committee determine
the most convenient sites for these facilities? To attempt to answer such questions, we introduce the
following concepts.
Definition 2.3.4 (Eccentricity, Radius, Diameter).
The eccentricity e(v) of a vertex v in a graph G is the maximum distance of a vertex from v; that
is, e(v) is the distance from v to a vertex furthest from v. The radius rad(G) of G is the minimum
eccentricity among the vertices of G, while the diameter diam(G) is maximum eccentricity. A vertex
v is a central vertex if e(v) = rad(G), while v is a peripheral vertex if e(v) = diam(G).

Notice that the diameter of G is maximum distance between any two vertices in G. Furthermore, if
rad(G) = 1, then G contains a vertex that is adjacent to every other vertex. In Figure 2.7, the vertices
of the graph G are labelled with their eccentricities. For this graph G, rad(G) = 3 and diam(G) = 5.

Figure 2.7: Eccentricities of vertices.

The next result shows that the diameter of a graph is at most twice its radius.
Theorem 2.3.5 (Diameter, Radius).
For every connected graph G, rad(G) ≤ diam(G) ≤ 2 rad(G).

Proof. The inequality rad(G) ≤ diam(G) follows directly from the definitions. To verify the inequality
diam(G) ≤ 2 rad(G), let u and v be vertices in G satisfying d(u, v) = diam(G). Furthermore, let w
be a central vertex of G. Since the distance function satisfies the triangle inequality (see Property (iii)
of Theorem 2.3.2), diam(G) = d(u, v) ≤ d(u, w) + d(w, v) ≤ e(w) + e(w) = 2 e(w) = 2 rad(G).

The lower bound of Theorem 2.3.5 is sharp; that is, there exists a graph G for which rad(G) = diam(G).
In fact, the family Kn (n ≥ 2), of complete graphs satisfies this equation, as does the family of all
cycles. The upper bound is also sharp. To see this, let G belong to the family of paths of odd order;
that is, G ∼
= P2k+1 , k ≥ 1. Then rad(G) = k and diam(G) = 2k. Hence for each positive integer k,
there exists a graph G such that diam(G) = 2 rad(G).

Definition 2.3.6 (The Centre).

The centre C(G) of G is the subgraph induced by central vertices.
Section 2.3. Distance in Graphs Page 25

Returning to our facility location problem, a possible location for the emergency facility is a vertex in
the centre of the graph that models the street system.
The centre of a graph need not consider a single vertex. For example, the centre of the graph G of
Figure 2.7 is the subgraph induced by the three vertices of eccentricity 3, i.e., C(G) ∼
= P3 . Thus P3 is
the centre of some graph. In fact, Hedetnieml showed that every graph is the centre of some graph.
Theorem 2.3.7 (Centre).
Every graph is the centre of some connected graph.
Proof. Let H be a given graph. Let G be the graph constructed from H by adding four new vertices
v1 , v2 , w1 , w2 and, for i = 1, 2, joining vi to every vertex of H and to wi . For each vertex v in H,
eG (v) = 2, while for i = 1, 2, e(vi ) = 3 and e(wi ) = 4. Thus rad(G) = 2 and the centre of G is the
subgraph induced by the vertices of H; that is, C(G) = H.

Learning Opportunities
2.13. Prove Properties (i), (ii) and (iii) of Theorem 2.3.2.
2.14. Consider the graph G below:

Find
2.14.1. the eccentricity of each vertex.
2.14.2. the radius and diameter of G.
2.14.3. the centre of G.
2.15. If u and v are adjacent vertices in a graph G, then show that |e(u) − e(v)| ≤ 1.
2.16. Show that if G is a graph of order n and size n4 , then either G contains an odd cycle or G ∼
2
= K n2 , n2 .
(Hint: Suppose G contains no odd cycles. Then by Theorem 2.3.3, G is bipartite. Show that
G∼= K n2 , n2 .)
2.17. Given a positive integer r and d with r ≤ d ≤ 2r, construct a graph G with rad(G) = r and
diam(G) = d. (Hint: construct such a graph with one cycle.)
Section 2.4. Cut-vertices and Bridges Page 26

2.4 Cut-vertices and Bridges

Some graphs are connected so slightly that they can be disconnected by deleting a single vertex or a
single edge. Such vertices and edges play a special role in graph theory. and we discuss these next.
Definition 2.4.1 (Slightly Connected Graphs).
If e is an edge of a graph G, then G − e is the subgraph of G possessing the same vertex set as G
and having all the edges except e. If v is a vertex of a graph G containing at least two vertices, then
G − v is the subgraph of G whose vertex set consists of all vertices of G except v and whose edge set
consists of all edges of G except those incident with v. Figure 2.8 illustrates these concepts.

Figure 2.8

Definition 2.4.2 (Cut-vertices and Bridges).

A vertex v in a graph G is called a cut-vertex of G if k(G − v) > k(G). So, if G is a connected
graph, then v is cut-vertex if G − v is disconnected. Analogous to the cut-vertex is the concept of a
bridge. An edge e is a bridge if k(G − e) > k(G). Therefore, if G is a connected graph, then e is a
bridge if G − e is disconnected.

The vertex v3 of the graph G in Figure 2.8 is cut-vertex; however, no other vertex of the graph is
a cut-vertex. The edge e4 of the graph of the graph G in Figure 2.8 is a bridge, but no other edge
of that graph is a bridge. If v is a cut-vertex of a connected graph G, then G − v contains two or
more components. However, if e is a bridge of a connected graph G, then G − e contains exactly two
components.
Theorem 2.4.3 (Cut-vertex).
A vertex v of a connected graph G is a cut-vertex of G if and only if there exists vertices u and w
(u ̸= w) such that v is on every u − w path.
Proof. Let v be a cut-vertex of G so that G − v is disconnected. If u and w are vertices in different
components of G − v, then there are no u − w paths in G − v, However, since G is connected, there are
u − w paths in G. Thus, v must lie on every u − w path. Conversely, suppose that there exists vertices
u and w such that v lies on every u − w path in G. Then, in G − v, there are no u − w paths, and so
G − v is disconnected. Thus, v is a cut-vertex of G.
Section 2.4. Cut-vertices and Bridges Page 27

Bridges are characterised in a manner similar to that of cut-vertices; the proof too is similar to that of
Theorem 2.4.3 and is left as an exercise (see Learning Opportunity 2.19).

Theorem 2.4.4 (Bridge).

An edge e of a connected graph G is a bridge of G if and only if there exists vertices u and w (u ̸= w)
such that e is on every u − w path of G.

For bridges, there is another useful characterization.

Theorem 2.4.5 (Useful characterization for bridges).
Let G be a connected graph. An edge e of G is a bridge if and only if e does not lie on any cycle of
G.
Proof. Let e be a bridge of G. We prove the desired result by a contradiction argument. Suppose
e = uv and e does lie on a cycle, say C : u, v, w, . . . , x, u (that is, w follows v on C and x precedes u).
The graph G − e contains a u − v path, namely u, x, . . . , w, v, so that u is connected to v. We now
show that G − e is connected.
Let u1 and v1 be any two vertices of G − e; we show that G − e contains a u1 − v1 path. Since G is
connected, there is a u1 − v1 path P in G. If the edge e does not lie on P , then P is also a path in G − e
and u1 is connected to v1 in G − e. Suppose the edge e lies on P . Then the path P can be expressed
as v1 , . . . , u, v, . . . , v1 , or u1 , . . . , v, u, . . . , v1 . In the first case, replace e on P by the u − v path on C
not containing e, i.e., the path u, x, . . . , w, v, to produce a u1 − v1 walk in G − e. In the second case,
replace e on P by the v − u path v, w, . . . , x, u to produce a u1 − v1 walk in G − e. Therefore if e
belongs to a cycle, then G − e is connected and e is not a bridge. This produces a contradiction.
Conversely, suppose e = uv is an edge which lies on no cycle of G. Again, we give a proof by
contradiction. Assume that e is not a bridge. Then G − e is connected, and thus, there is a u − v
path P in G − e. However, P together with e produces a cycle in G containing e. Hence, we have a
contradiction.

Definition 2.4.6 (Cycle Edge).

A cycle edge of a graph G is an edge that belongs to a cycle in G.

By Theorem 2.4.5, every edge of a graph G is either a bridge or a cycle edge.

Section 2.4. Cut-vertices and Bridges Page 28

Learning Opportunities
2.18. In the graph G shown below, determine the cut-vertices and the bridges of G.

2.19. Prove Theorem 2.4.4.

2.20. Give an example of a connected graph containing more cut-vertices than bridges.
2.21. Give an example of a connected graph containing more bridges than cut-vertices.
2.22. Prove that every graph containing only even vertices cannot contain a bridge.
2.23. Let G be a connected graph containing only even vertices. Show that it is possible for G to
contain a cut-vertex.
2.24. Prove that if v is a cut-vertex of a connected graph G, then v is not a cut-vertex of G.
2.25. Give an example of a connected, 3-regular graph containing a bridge.
3. The Shortest Path Algorithm
3.1 Introduction
Consider the following problem: A traveller wishes to drive from Kimberley (Northern Cape) to Cape
Town (Western Cape). Given that the traveller has a map of South Africa that shows the distance
between particular pairs of cities or towns, how does the traveller determine the shortest possible route?
In this particular example, it may not be too difficult to find the solution by intelligent guesswork, but
such an approach is less likely to succeed as the road network becomes more and more complicated. In
the section we describe an efficient algorithm which can be used to find the shortest path between any
two vertices in a graph.

3.2 Distance in Weighted Graphs

Before introducing the shortest path algorithm, we will need to generalise the concept of distance in a
graph.
Definition 3.2.1 (Weighted Graph).
A weighted graph is graph in which each edge e is assigned a positive real number, called the weight
of e, and denoted by w(e). The length of a path P in a weighted graph G is the sum of the weights
of the edges of G. For connected vertices u and v of the weighted graph G, the distance d(u, v)
between u and v is the minimum of the lengths of the u − v paths of G. A u − v path of minimum
weight in G is called a shortest u − v path for G (so that a path containing three edges, each of
weight one, is “shorter” than a path containing two edges, each of weight two).

Consider the weighted graph G of Figure 3.1. The path P : v2 , v1 , v3 , v4 is a shortest v2 − v4 path (of
length 4). Notice that the path Q : v2 , v3 , v5 (of length 5) is not a shortest v2 − v4 path for G, even
though Q has fewer edges than P .
For example, an airline service can be represented by a weighted graph with the vertices representing
the cities serviced, edges representing the direct flying routes, and with the weight of an edge being
the cost of a direct fight. Finding the distance between two vertices in this weighted graph corresponds
to finding the minimum cost of flying from one city to another, while a shortest path is a flying route
between two cities with the lowest cost.
Definition 3.2.2 (The Weight Matrix).
Let G be a weighted graph with vertex set V (G) = {v1 , v2 , . . . , vn }. It is convenient to represent G
by means of a weight matrix W (G) defined as follows: W (G) = (wi,j ) is an n × n matrix, where
(
w(vi vj ) if vi vj ∈ E(G)
wi,j =
∞ if vi vj ∈
/ E(G).

(By ′ ∞′ we shall mean a number larger than any weight actually occurring in our calculations.) For
example, a graph and its weight matrix are shown in Figure 3.1, where the weights of edges are indicated
in the diagram.

29
Section 3.3. Dijkstra’s Algorithm Page 30

Figure 3.1: A weighted graph G and its weight matrix.

3.3 Dijkstra’s Algorithm

We now introduce an algorithm, due to Dijkstra (1959), which determines, for a fixed vertex x in a
connected weighted graph G, the distance d(x, v) from x to each vertex v of G, as well as a shortest
x − v path in G. We shall write w(e) = ∞ if e ∈/ E(G), i.e, w(uv) = ∞ if u and v are non-adjacent
vertices of G.
The idea of Dijkstra’s algorithm is to modify labels l(v) attached to the vertices, where l(v) represents
the length of the shortest x − v path presently known. As we proceed, we reduce these labels as shorter
paths are found from x to v. Initially, x is labelled l(x) = 0 and all other vertices are labelled ∞. At any
stage in the algorithm, for any vertex v ̸= x, let the variable parent(v) denote the vertex that precedes
v on a shortest x − v path detected thus far. Furthermore, at each stage of the algorithm, we look at
those vertices with a temporary label that are adjacent to the current vertex. To each such vertex v,
we assign a new temporary label l(v) representing the length of the shortest x − v path considered until
now. This vertex then becomes the current vertex and its label l(v) is now permanent. Whenever l(v)
is updated, a shortest x − v path is found, and at this point parent(v) is updated to indicate the vertex
that now precedes v on this shorter x − v path. Eventually each vertex acquires a permanent label which
represents the shortest distance from x to that vertex. For v (̸= x), the label l(v) changes (perhaps
several times) from ∞ to d(x, v) as this distance is determined. When v acquires its permanent label
l(v), we produce a shortest x − v path

P : x = w0 , w1 , w2 , . . . , wn = v.

where wi−1 = parent(wi ) for i = 1, 2, . . . , n. We are now prepared to present Dijkstra’s algorithm.

Algorithm 3.3.1 (Dijkstra).

Given a connected weighted graph G of order n and a vertex x of G:
1. Set l(x) = 0 and for all v ̸= x, set l(v) = ∞ and set S = V (G).
2. If |S| = 1, then stop; otherwise, continue.
3. Among all the vertices in S, let u be the one of minimum label l(u).
4. For each v ∈ S, if uv ∈ E(G) and l(u) + w(uv) < l(v), then
• replace l(v) by l(u) + w(uv), and
• assign to parent(v) the label u.
5. Remove u from S, and return to Step 2.
Section 3.3. Dijkstra’s Algorithm Page 31

As an example, we apply Dijkstra’s algorithm to the graph G of Figure 3.1 to determine the distance
from the vertex x = v1 to every other vertex of G and to find a shortest x − vi ) path for i = 1, 2, 3, 4.
Table 3.1 has three columns corresponding to the vertices v2 , v3 , v4 . The ordered pairs in the columns
corresponding to the vertex vi indicate (l(vi ), parent(vi )) for i = 2, 3, 4 at a given point in the algorithm.

l(v) v2 v3 v4 removed from S S

0 (∞, −) (∞, −) (∞, −) − {x, v2 , v3 , v4 }
(1, x) (2, x) (5, x) x {v2 , v3 , v4 }
(2, x) (5, x) v2 {v3 , v4 }
(3, v3 ) v3 {v4 }

Table 3.1

To understand how we obtained Table 3.1, let us apply Dijkstra’s algorithm to the graph G of Figure
3.1. We start by assigning to x = v1 the label l(x) = 0, and to every other vertex vi the label l(vi ) = ∞.
Initially, we set S = {x, v2 , v3 , v4 }.
We select x, since it has the smallest label among all vertices in S. The label l(x) = 0 is now the
permanent label of x. Next we examine the vertices in S adjacent to x, namely v2 , v3 , v4 . Since
l(v2 ) = ∞ > 1 = l(x) + w(xv2 ), we replace l(v2 ) by 1 and assign to parent(v2 ) the vertex x.
Furthermore, we replace l(v3 ) by l(x) + w(xv3 ) = 2 and assign to parent(v3 ) the vertex x, and we
replace l(v4 ) by l(x) + w(xv4 ) = 5 and assign to parent(v4 ) the vertex x. We then remove x from S
to obtain S = {v2 , v3 , v4 } and return to Step 2 of the algorithm.
We select v2 , since it has the smallest label among all vertices in S. The label l(v2 ) = 1 is now the
permanent label of v2 . Next we examine the vertices in S adjacent to v2 . Since l(v3 ) = 2 ≤ 5 =
l(v2 ) + w(v2 v3 ), the label l(v3 ) remains unchanged. We then remove v2 from S to obtain S = {v3 , v4 }
and return to Step 2 of the algorithm.
We select v3 , since it has the smallest label among all vertices in S. The label l(v3 ) = 2 is now the
permanent label of v3 . Next we examine the vertices in S adjacent to v3 . Since l(v4 ) = 5 > 3 =
l(v3 ) + w(v3 v4 ), we replace l(v4 ) by 3 and assign to parent(v4 ) the vertex v3 . We then remove v3 from
S to obtain S = {v4 } and return to Step 2 of the algorithm. Since |S| = 1, the algorithm terminates.
Our results may be summarized as shown in Table 3.2. Using Table 3.1 we obtain, for each i = 2, 3, 4,
the distance from x = v1 to vi and a shortest x − vi path Pi .

v d(x, v) Pi
v2 l(v2 ) = 1 x, v2
v3 l(v3 ) = 2 x, v3
v4 l(v4 ) = 3 x, v3 , v4

Table 3.2

As a second example, we apply Dijkstra’s algorithm to the graph G of Figure 3.2 to determine the
distance from the vertex x to every other vertex of G and to find the shortest x-vi path for i = 1, 2, . . . , 5.
Section 3.3. Dijkstra’s Algorithm Page 32

Figure 3.2: A weighted graph G.

Table 3.3 has five columns corresponding to the vertices v1 , v2 , . . . , v5 . As in the previous example, the
ordered pairs in the column corresponding to the vertex vi indicate (l(vi ), parent(vi )) for i = 1, 2, . . . , 5
at a given point in the algorithm.

l(x) v1 v2 v3 v4 v5 Removed from S S

0 (∞, −) (∞, −) (∞, −) (∞, −) (∞, −) − V (G)
(∞, −) (13, x) (∞, −) (16, x) (8, x) x {v1 , v2 , . . . , v5 }
(18, v5 ) (13, x) (25, v5 ) (15, v5 ) v5 {v1 , v2 , v3 , v4 }
(18, v5 ) (25, v5 ) (15, v5 ) v2 {v1 , v3 , v4 }
(18, v5 ) (20, v4 ) v4 {v1 , v3 }
(19, v1 ) v1 {v3 }

Table 3.3

Our results may be summarized as shown in Table 3.4. Using Table 3.3 we obtain, for each i = 1, 2, . . . , 5,
the distance from x to vi and a shortest x-vi path Qi .

v d(x, v) Qi
v1 l(v1 ) = 18 x, v5 , v1
v2 l(v2 ) = 13 x, v2
v3 l(v3 ) = 19 x, v5 , v1 , v3
v4 l(v4 ) = 15 x, v5 , v4
v5 l(v5 ) = 8 x, v5

Table 3.4

We now verify that on completion, Dijkstra’s algorithm has labelled the vertices with their proper
distances from x. To do this, we first prove the following tow lemmas.
Lemma 3.3.2.
At the termination of Dijkstra’s algorithm, l(v) is finite for all v ∈ V (G).
Section 3.3. Dijkstra’s Algorithm Page 33

Proof. Assume, to the contrary, that on completion of Dijkstra’s algorithm not all vertices have finite
labels. Let w be the first vertex selected from S with an infinite label. Since w was chosen as a vertex
of S with minimum label, all vertices of S when w was selected have infinite labels, while all vertices
already deleted from S have finite labels. But then there is no edge from V (G) − S to S (since if such
an edge e = uv with u ∈ V (G) − S and v ∈ S did exist, then u was selected as the current vertex
in Step 3 of the algorithm, the label l(v) of v would have dropped from ∞ to l(u) + w(uv), which is
finite). Thus there is no path from a vertex of S to a vertex of V (G) − S. Hence G is disconnected,
which produces a contradiction.

Lemma 3.3.3.
At the termination of Dijkstra’s algorithm, d(x, v) ≤ l(v) for all v ∈ V (G).

Proof. If v = x, then d(x, v) = 0 = l(v). If v = ̸ x, then by Lemma 3.3.2, l(v) is finite. Consider
the x − v path P : x = w0 , w1 , w2 , . . . , wk = v where wi−1 = parent(wi ) for i = 1, 2, . . . , k. The
k
X
path P has weight w(P ) = w(wi−1 wi ). Since wk−1 is the vertex used to label wk , we know that
i=1
l(v) = l(wk ) = l(wk−1 ) + w(wk−1 wk ). After this labelling, the vertex wk−1 is removed from S (in
Step 5), and hence its label can never change again. Repeating this backtracking search, we have
l(wk−1 ) = l(wk−2 ) + w(wk−2 wk−1 ), so l(v) = l(wk−2 ) + w(wk−2 wk−1 ) + w(wk−1 wk ). Eventually we
will backtrack to x. Thus l(v) = l(w0 ) + w(w0 w1 ) + w(w1 w2 ) + · · · + w(wk−1 wk ) = w(P ), since
l(x) = l(w0 ) = 0. Thus P has weight l(v). Since d(x, v) is the length of a shortest x − v path,
d(x, v) ≤ l(v).

We are now in a position to verify Dijkstra’s algorithm.

Theorem 3.3.4.
At the termination of Dijkstra’s algorithm, l(v) = d(x, v) for all v ∈ V (G).
Proof. We proceed by induction on the order in which we delete vertices from S. This is certainly
true for the vertex, namely x, deleted from S since l(x) = 0 = d(x, x). Assume that l(u) = d(x, u)
for all vertices u deleted from S before v. Let P : x = v0 , v1 , v2 , . . . , vk = v be a shortest x − v
path of length d(x, v). Then the x-vi subsection of P must be a shortest x-vi path for i = 1, 2, . . . , k
(otherwise we could find a shorter x − v path than P which is impossible). Suppose vi is the vertex
of highest subscript on P deleted from S before v. By the inductive hypothesis, l(vi ) = d(x, vi ) =
w(v0 v1 ) + w(v1 v2 ) + · · · + w(vi−1 vi ). When vi was chosen from S as the current vertex, we compared
the current label of vi+1 with l(vi ) + w(vi vi+1 ) in Step 4 of the algorithm. Hence after vi is deleted
from S in Step 5, l(vi+1 ) ≤ l(vi ) + w(vi vi+1 ). If vi+1 ̸= v, then, since Step 4 can only decrease labels,
l(vi+1 ) still satisfies this inequality when v is chosen. Thus,

l(vi+1 ) ≤ l(vi ) + w(vi vi+1 )

= d(x, vi ) + w(vi vi+1 )
= d(x, vi+1 )
< d(x, v) (since vi+1 precedes v on P )
≤ l(v) (by Lemma 3.3.3)

This, however, contradicts the fact that v was chosen before vi+1 , so l(v) ≤ l(vi+1 ). Hence vi+1 = v
Section 3.3. Dijkstra’s Algorithm Page 34

and so

l(v) ≤ l(vi ) + w(vi v)

= d(x, vi ) + w(vi vi+1 )
= d(x, v)
≤ l(v) (by Lemma 3.3.3)

Hence we must have l(v) = d(x, v).

Learning Opportunities
3.1. A company has branches in each of the six cities c1 , c2 , c3 , c4 , c5 and c6 . The fare for a direct
flight from ci to cj is given by the (i, j)th entry in the matrix C (where ∞ indicates that there is
no direct flight). Use Dijkstra’s algorithm to find the cheapest route (and its length) from c1 to
all five other cities.
500 ∞ 400 250 100
 
0
500
 0 150 200 ∞ 250 
∞ 150 0 100 200 ∞ 
C=
 
400 200 100 0 100 250

 
250 ∞ 200 100 0 550
100 250 ∞ 250 550 0

3.2. Let G be the weighted graph in the accompanying figure. Use Dijkstra’s algorithm to compute
d(x, v) for each v ∈ V (G) and to determine the shortest x-v6 path.

3.3. Let G be the weighted graph with V (G) = {v1 , v2 , . . . , v7 } and the weight matrix W (G) as shown
below:
 
0 8 1 4 2 7 ∞
8 0 7 1 ∞ ∞ 4 
 
1 7 0 ∞ 2 ∞ ∞ 
 
 
W (G) = 
4 1 ∞ 0 ∞ 3 6 

2 ∞ 2 ∞ 0 5 ∞ 
 
7 ∞ ∞ 3 5 0 4 
 
∞ 4 ∞ 6 ∞ 4 0

3.3.1. Draw the weighted graph G.

Section 3.3. Dijkstra’s Algorithm Page 35

3.3.2. Find the distance from v3 to every other vertex of G.

3.4. Let G be the weighted graph in the accompanying figure. Use Dijkstra’s algorithm to compute
d(v1 , vi ) for each vi ∈ V (G) and to determine the a shortest v1 -vi path.
4. Trees
4.1 Introduction
Suppose we have a collection of n cities, and we wish to construct a railway system connecting them.
Hence a passenger must be able to ride from any station in the system to any other station. Assume
that we know the cost of building tracks between every two cities. How can we build the railway system
as cheaply as possible?
The desired railway system can be represented by a graph whose vertices correspond to cities involved
and which two vertices are adjacent if a track runs between the two corresponding cities. The edges are
labelled (weighted) with their proposed costs. To solve this problem, we must find a connected graph
(so that all stations can be reached from all other stations) with the minimum sum of the edge weights.
This is called the Minimum Connector Problem.
Note that to construct a graph with minimum edge weight sum, we must avoid cycles, since otherwise
we could remove the most expensive edge (largest weight) on the cycle, obtaining a new connected
graph with smaller weight sum. Hence, it would be possible to leave out a set of tracks between two
cities and still have all cities connected, implying that the original railway system is not the cheapest.
Thus, what we desire is a connected acyclic graph with minimum possible edge weight sum. Before
solving the Minimum Connector Problem, we need to investigate in more detail the type of graph we
have just encountered.

Figure 4.1: Three trees.

Figure 4.1 shows three trees. Trees are the simplest connected graphs. These graphs are perhaps
the most useful of all special cases of graphs. Recently, there has been considerable interest in tree
structures arising in the computer sciences and in artificial intelligence. We often meet such structures
when organising data in a computer memory store or when organising the flow of information through
a system. Trees also have applications in chemistry (for example, in counting the alkanes Cn , H2n+1 ),
sociology, and many other studies. The sorting of mail according to zip code is done according to a
tree (called a decision tree). In computer programming and switching theory, we frequently deal with
decision trees with only two alternatives at each intermediate vertex. Both theory and applications of
trees will be discussed in this chapter.

4.2 Properties of Trees

In this section, we present several results on the properties of trees. Since a tree contains no cycle, it
follows from Theorem 2.4.5 that every edge of a tree is a bridge. Trees have several pleasing properties–

36
Section 4.2. Properties of Trees Page 37

for example, any two vertices of a tree are connected by exactly one path.
Theorem 4.2.1 (Path Uniqueness).
A graph T is a tree if and only if every two distinct vertices are joined by a unique path.
Proof. If T is a tree, then by definition it is connected. Hence, any two vertices are joined by at least
one path. Suppose there are vertices u and v of T that are joined two or more different paths. Let P
and Q be two different u − v paths in T . Then there must be a vertex x (possibly x = u) on both paths
such that the vertex immediately following x on P is different from the vertex immediately following x
on Q. Let y be the first vertex of P following x that also belongs to Q (possibly y = v). Then the
section of P from x to y and the section of Q from x to y produce two x − y paths that have only x
and y in common. These paths produce a cycle in T , which contradicts the fact that T is a tree. Hence
every two distinct vertices of T are joined by a unique path.
On the other hand, suppose T is a graph in which any two distinct vertices are joined by a unique path.
This implies that T is connected. If T has a cycle containing vertices u and v, then u and v are joined
by at least two paths, contradicting our hypothesis. Hence T is acyclic so that T is a tree.

The sizes of the trees shown in Figure 4.1 are one less than their orders. We now verify this simple but
important relationship between the number of vertices and the number edges in any tree.
Theorem 4.2.2 (Size of a tree).
A tree T of order n has size m = n − 1.
Proof. We prove by induction on n. If n = 1, then T ∼ = K1 and T has size m = 0, as required. Let
k ≥ 2 be an integer, and suppose the result is true for all trees of order n < k. Let T be a tree of order
n = k and size m, let e = uv be an edge of T . Since every edge of a tree is a bridge, the graph T − e
is disconnected. In fact, T − e is a forest with exactly two components, namely a tree T1 containing u
and a tree T2 containing v. Let Ti (i = 1, 2) be a tree of order ni and size mi . Then ni < k (i = 1, 2).
Hence, by inductive hypothesis, we know that mi = ni − 1 for i = 1, 2. Since n = n1 + n2 and
m = m1 + m2 + 1 (the + 1 is for the removed edge e),

m = (n1 − 1) + (n2 − 1) + 1
= n1 + n2 − 1
= n − 1.

Thus, by induction, the size of a tree is one less than its order.

We are now in a position to present various characterisations of a tree.

Theorem 4.2.3 (Characterisations of a tree).
Let T be a graph of order n. Then the following statements are equivalent:
(i) T is a tree;
(ii) T is connected and has size n − 1;
(iii) T has no cycles and has size n − 1.
Proof. If T is a tree of order n, then, by definition, T is connected and, by Theorem 4.2.2, T has size
n − 1. So (i) =⇒ (ii).
Suppose that T is connected and has size n − 1. Assume T contains a cycle and let e be an edge of this
cycle. Then, by Theorem 2.4.5, e is not a bridge of T , so T − e is a connected graph of order n and
Section 4.2. Properties of Trees Page 38

size n − 2, which is a contradiction (see Learning Opportunity 4.3). Therefore T has no cycles. Thus
(ii) =⇒ (iii).
Suppose that T has no cycles and size n − 1. In order to prove that T is a tree, we must show that T is
connected. Let T1 , T2 , . . . , Tk be the components of T (k ≥ 1), where Ti has order ni and size mi for
i = 1, 2, . . . , k. Since each component Ti (i = 1, 2, . . . , k) is a connected graph with no cycles, each Ti
is a tree. Thus, by Theorem 4.2.2, mi = ni − 1. Hence
k
X k
X k
X k
X
n−1=m= mi = (ni − 1) = ni − 1 = n − k,
i=1 i=1 i=1 i=1

so k = 1 and therefore T is connected. Hence T is a tree. Thus (iii) =⇒ (i).

Each of the trees shown in Figure 4.1 has at least two end-vertices. Using Theorem 4.2.2, we show that
this is also true in general.
Theorem 4.2.4 (Tree, End-vertices).
Every nontrivial tree contains at least two end-vertices.
Proof. Suppose that T is a tree of order n and size m, and let d1 , d2 , . . . , dn denote the degrees of
its vertices, ordered so that d1 ≤ d2 ≤ · · · ≤ dn . Since T is connected and nontrivial, di ≥ 1 for each
i (1 ≤ i ≤ n). If T does not contain at least two end-vertices, then d1 ≥ 1 and di ≥ 2 for 2 ≤ i ≤ n.
So
n
X n
X
di = d1 + di ≥ 1 + 2m = 1 + 2(n − 1) = 2n − 1.
i=1 i=2

However, by Theorems 1.5.3 and 4.2.2,

n
X
di = 2m = 2(n − 1) = 2n − 2,
i=1

which contradicts the previous inequality. Hence T contains at least two end-vertices.

Learning Opportunities
4.1. How many different trees (pairwise nonisomorphic) are there of order 6? Find all such trees.
4.2. Let G be a graph of order n and size n − 1. Show that G need not be a tree.
4.3. Prove that if G is a connected graph of order n and size m, then m ≥ n−1. (Hint: Use induction
on the order n of a connected graph.)
4.4. Let T be a forest of order n, size m and having k components. Show that m = n − k.
4.5. Construct a forest with 12 vertices and 9 edges.
4.6. Show that if T is a tree and e is an edge of T , then T − e has exactly two components.
4.7. Show that the sequence d1 , d2 , . . . , dn of positive integers is the degree sequence of a tree if and
n
X
only if the graph is connected and di = 2(n − 1).
i=1
Section 4.3. Constructing Minimum Spanning Trees Page 39

4.8. Let G be a graph of order n and size m with m ≥ n ≥ 3. Show that G must contain at least one
cycle.
4.9. Suppose T is a tree of order n that contains only vertices of degree 1 and 3. Prove that T contains
n−2
2 vertices of degree 3.

4.3 Constructing Minimum Spanning Trees

In this section, we return to the Minimum Connector Problem. First we shall need the concept of a
spanning tree of a connected graph.
Definition 4.3.1 (Spanning tree, Spanning forest).
A spanning tree of a connected graph G is a tree that is a subgraph of G that contains all the vertices
of G. A spanning forest of a graph G is a forest that is a subgraph of G that contains all the vertices
of G.

A connected graph may actually have several nonisomorphic spanning trees. Figure 4.2 shows a graph
G and three of its spanning trees T1 , T2 and T3 .

Figure 4.2: Spanning trees of a graph.

Every connected graph G contains a spanning tree. We can find such a spanning tree as follows: If
G has no cycles, then the graph G itself is a spanning tree. If there are cycles in G, then choose any
cycle in G and remove one of its edges. By removing one cycle edge in G, we still remain with a
connected graph. We now repeat this procedure, removing cycle edges one at a time, until finally only
bridges remain; this gives our spanning tree. So it is easy to find a spanning tree in a connected graph.
However, a much stronger statement can be made.
Definition 4.3.2 (Distance preserving).
A spanning tree T of a connected graph G is said to be distance preserving from a vertex v in G if
dT (u, v) = dG (u, v) for every vertex u.

Theorem 4.3.3 (Distance preserving).

For every vertex v of a connected graph G, there exists a spanning tree T that is distance-preserving
from v.
Proof. Let n be the maximum distance from v to a vertex of G. For i = 1, 2, . . . , n, let

Di (v) = {u ∈ V (G) | d(u, v) = i}.

Since G is connected, it follows that every vertex u ̸= v belongs to Di (v) for some i (1 ≤ i ≤ n).
Furthermore, such a vertex u is adjacent to at least one vertex of Di−1 (v) and possibly to vertices in
Section 4.3. Constructing Minimum Spanning Trees Page 40

Di (v) and Di+1 (v) as well. Delete all but one edge that joins u to a vertex of Di−1 (v). Also, remove
every edge joining u to a vertex of Di (v). Repeat this process for each u = ̸ v. Let T denote the
resulting graph.
From the manner in which T was constructed, it is clear that T is connected since u − v path exists for
each u ̸= v. It is also clear that T is distance-preserving from v. It remains for us to verify that T is a
tree. We only need to show that T is acyclic. If this is not the case, then there is a cycle C in T . Let w
be a vertex in C whose distance from v is maximum, and let w1 and w2 be the vertices adjacent to w
on C. Suppose w ∈ Dk . Then wi ∈ Dk or wi ∈ Dk−1 for i = 1, 2. If w1 ∈ Dk or w2 ∈ Dk , then this
contradicts the way in which T was constructed (no edge in T joins two vertices in same set Di (v)).
Thus, both w1 and w2 belong to the set Dk−1 . Once again, this contradicts the way in which T was
constructed (exactly one edge in T joins a vertex in Di to a vertex in Di−1 ). We deduce, therefore,
that T is acyclic and hence T is a tree.

Figure 4.3: A connected graph G (with vertex v) and a spanning tree T that is distance-preserving
from v.

There are a number of applications involving spanning trees in connected graphs.

Definition 4.3.4 (Minimum spanning tree).
The weight w(H) of a subgraph H of a weighted graph is the sum of the weights of the edges of H.
A minimum spanning tree of a connected weighted graph is a spanning tree of minimum weight in
the graph.

We can now restate the Minimum Connector Problem in graphical terms.

The Minimum Connector Problem: Given a connected weighted graph, find a minimum spanning
tree in it.
The Minimum Connector Problem is perhaps one of the best known problems in combinatorial optimi-
sation. Many practical problems involve connected weighted graphs in which it is necessary to find a
minimum spanning tree. Consider, for example, a graph where each vertex represents a village, and an
edge between two vertices represents a road between the corresponding villages. The length of such a
road is indicated in the graph by assigning a weight to the corresponding edge. Telephone line must
Section 4.3. Constructing Minimum Spanning Trees Page 41

be built along some existing roads that connect the villages with each other. We wish to erect these
telephone line in such a way that every pair of villages can communicate by telephone. Moreover, the
total number of kilometres of telephone lines is to be minimised. The problem with which we are faced
is to determine along which roads these telephone lines should be erected to produce the desired system.
This amounts to finding the a minimum spanning tree in the connected weighted graph.
A number of algorithmic solutions to the Minimum Connector Problem have been given. Perhaps the
most famous of these algorithms is one due to Kruskal [21] in 1956. The strategy of the algorithm is
very simple. We begin by choosing an edge of minimum weight that does not form a cycle with any of
the edges we have already chosen. We continue in this fashion until a spanning tree is formed.
Algorithm 4.3.5 (Kruskal).
To construct a minimum spanning tree in a connected weighted graph G, successfully choose edges
of G of minimum weight in such a way that no cycles are created.

Kruskal’s algorithm is an example of a type of algorithm known as a greedy algorithm. This name
arises from the fact that at each stage we make the greediest choice available (that is, the edge involving
the smallest weight) with no concern for what is happening else where in the graph. Algorithms of this
kind can sometimes work very well as we will show in the case of Kruskal’s algorithm. However, in
practice, the greedy approach does not always succeed.
To illustrate Kruskal’s algorithm, we find a minimum spanning tree in the connected weighted graph G
shown in Figure 4.4.

Figure 4.4: A weighted graph G.

First Choice: We choose an edge of minimum weight; this is de with weight 1.

Second Choice:We choose an edge of next smallest weight; this is either bc or cg with weight 2. Let
us choose bc.
Third Choice: We choose an edge of next smallest weight; this is cg of weight 2.
Fourth Choice: We cannot now choose bg, since it would create a cycle, namely b, c, g, b. So we choose
an edge of next smallest weight different from bg; this is either cd or eg with weight 3. Let us choose
cd.
Section 4.3. Constructing Minimum Spanning Trees Page 42

Fifth Choice: We cannot now include eg in the tree, since it would create a cycle (c, d, e, g, c). The
edge of next smallest weight is dg with weight 4. Since this edge would create a cycle (c, d, g, c), we
choose instead one of the edges ab, ag, or af with weight 6. Let us choose ag.
Sixth Choice: The edges of next smallest weight are ab and af with weight 6. Since ab would create
a cycle (a, b, c, g, a), we choose af .
This completes the spanning tree T , since the addition of any further edge would create a cycle. The
tree T (shown in Figure 4.5) is a minimum spanning tree of weight
w(T ) = w(de) + w(bc) + w(cg) + w(cd) + w(ag) + w(af )
=1+2+2+3+6+6
= 20.

Figure 4.5: A spanning tree T of G produced by Krusal’s algorithm.

It is clear that Kruskal’s algorithm will produce a spanning tree of any connected weighted graph to
which it is applied. It is not obvious, though, that it produces a minimum spanning tree. This requires
a proof.
Theorem 4.3.6 (Kruskal).
Kruskal’s algorithm produces a minimum spanning tree in a connected weighted graph.
Proof. Let G be a nontrivial connected weighted graph of order n, and let T be the subgraph produced
by Kruskal’s algorithm. By the way in which T was constructed, it has no cycles. Also, T is connected,
since otherwise we could add another edge of G without creating a cycle. Also, T contains every vertex
of G, since if it did not contain some vertex, then we could ass an edge incident with that vertex without
creating a cycle. Therefore, T is a spanning tree of G (and so has size n − 1 by Theorem 4.2.2). Let
E(T ) = {e1 , e2 , . . . , en−1 },
where e1 , e2 , . . . , en−1 is the order in which the edges were chosen, so w(e1 ) ≤ w(e2 ) ≤ · · · ≤ w(en−1 ).
Therefore, the weight of T is
n−1
X
w(T ) = w(ei ).
i=1
Section 4.3. Constructing Minimum Spanning Trees Page 43

We must show that T is a minimum spanning tree of G. We do this by contradiction. Suppose, the
contrary, that T is not a minimum spanning tree of G. Then, among all the minimum spanning trees
of G, choose one, call it T ∗ , which has a maximum number of edges in common with T . Since T is not
a minimum spanning tree, the trees T and T ∗ are not identical. So T has at least one edge that does
not belong to T ∗ . Using the ordering on the edges of T , we let ei (1 ≤ i ≤ n − 1) be the first edge of
T that is not in T ∗ . If we now insert the edge ei into T ∗ , we get a graph H that is not in T . We now
consider the graph T0 = H − e. Since e is not a bridge of H, the graph T0 is connected and has size
n − 1. Hence, by Theorem 4.2.3, the graph T0 is also a spanning tree of G and

w(T0 ) = w(T ∗ ) + w(ei ) − w(e).

Since w(T ∗ ) ≤ w(T0 ), it follows that w(e) ≤ w(ei ). However, by the manner in which T was con-
structed, ei is an edge of smallest weight which can be added to the edges e1 , e2 , . . . , ei−1 without
creating a cycle. However, since all the edges e1 , e2 , . . . , ei−1 and e come from the tree T ∗ , we note
that if e is added to the edges e1 , e2 , . . . , ei−1 , then no cycle is produced. Thus, we have w(ei ) ≤ w(e),
so w(ei ) = w(e). Hence, w(T0 ) = w(T ∗ ), which implies that T0 is also a minimum spanning tree of
G. But T0 has more edges in common with T than does T ∗ . This contradicts our choice of T ∗ . We
deduce, therefore, that T is a minimum spanning tree of G.

Learning Opportunities
4.10. Apply Kruskal’s algorithm to find a minimum spanning tree in the weighted graph G shown below.
Section 4.3. Constructing Minimum Spanning Trees Page 44

4.11. Apply Kruskal’s algorithm to find a minimum spanning tree in the weighted graph H shown below.

4.12. Let G be a connected weighted graph whose edges have distinct weights. Show that G has a
unique spanning tree.
5. Eulerian Graphs
5.1 Introduction
Probably the oldest and best known of all problems in graph theory is the problem of the seven Königsberg
bridges.
The Königsberg bridges problem. In the eighteenth century, the medieval city of Königsberg in
Eastern Prussia contained a central island called Kneiphof, around which the river Prigel flowed before
dividing into two. The four parts of the city were interconnected by seven bridges, as shown in Figure
5.1. The legend says that the citizens of Königsberg amused themselves by trying to find a route crossing
each bridge exactly once, and returning to the starting point. Can this be done?

Figure 5.1: The bridges of Königsberg

Try as they might, the citizens of Königsberg could find no route crossing each bridge exactly once
and returning to the starting point, and they all came to believe that such a route was not possible.
However, it was not until Leonard Euler [10] investigated the problem that it was proved to be impossible.
Although Euler’s proof in 1736 was not written in the language of graphs, the ideas in it are essentially
graph-theoretical in nature. Before proceeding further, we introduce the concept of a multigraph.
Definition 5.1.1 (Multigraph).
A A Multigraph is a graph in which one allows more than one edge (but a finite number) to join pairs
of vertices.

We can now express the Königsberg bridges in terms of a multigraph by taking the four land areas
as vertices and the seven bridges as edges joining the corresponding pairs of vertices. This gives the

45
Section 5.2. Eulerian Graphs Page 46

multigraph M shown in Figure 5.2. The Königsberg bridges problem is now reduced to determining
whether the multigraph M has a trail that contains all its edges.

Figure 5.2: The multigraph of the Königsberg bridges.

We use Euler’s reasoning to show why such a trail does not exist in M . Suppose, to the contrary, that
M contains a trail T . Then T can be represented by a sequence of eight letters (from {A, B, C, D}),
in which each pair of consecutive letters in the sequence represents an edge. Since five five bridges
lead to region A, Euler observed that the letter A has to appear at least three times-twice to indicate
entrance to and exit from region A. Similarly, since T accounts for all edges of M , each of the letters
B, C, and D must appear at least twice in the sequence. However, this means that at least nine letters
are needed in the sequence, which produces a contradiction. Thus our assumption that T exists must
be false. The townfolk’s suspicion that no walk through Königsberg would traverse each bridge exactly
once was therefore well-founded.

5.2 Eulerian Graphs

The Königsberg bridges problem introduces us quite naturally to two new concepts. Recall that a circuit
is a closed trail, and that in a closed trail the initial vertex is the same as the final vertex while in a
open train the initial vertex is different from the final vertex.
Definition 5.2.1 (An Eulerian Circuit).
An eulerian circuit of a connected (multi)graph G is a circuit of G that contains all the edges of G.
A (multi)graph with an eulerian circuit is called an eulerian (multi)graph. An eulerian trail of a
connected (multi)graph G is an open trail of G that contains all the edges of G.

The graph H of Figure 5.3 is eulerian since it contains an eulerian circuit (for example, C : a, e, b, c, d, e,
f, g, h, i, g, j, k, e, g, k, f, j, e, l, a). Note, however, that H does not contain an eulerian trail. The graph
G of Figure 5.3 has an eulerian trail T : u, v, w, x, v, z, x, y, z, but no eulerian circuit.
Section 5.2. Eulerian Graphs Page 47

Figure 5.3: Graphs with eulerian trails and eulerian circuits

The rule that Euler presented (in different terminology) is: to test whether a given connected (multi)graph
is eulerian, look at the degrees of vertices: if they are all even, then the graph is is eulerian; if not, then
the graph is not eulerian. That is, a necessary condition for a graph to be eulerian is that every vertex
has even degree. In Euler’s original paper [10] he stated that this condition is also sufficient. However,
the first published proof of the result was given by Hierholzer [18] in 1873.

Theorem 5.2.2 (Eulerian Circuit, Even Degree).

A connected multigraph G is eulerian if and only if the degree of every vertex in G is even.
Proof. If G has an eulerian circuit, then we can travel along that circuit, using each edge once, and
return to our original point v (say). Whenever we pass through a vertex of G, there is a contribution of
2 toward the degree of that vertex–including the initial vertex v, since each of the initial and the final
occurrences of v in the circuit contribute 1 to the degree of v. Since each edge of G is used just once,
the degree of each vertex is the sum of a number of 2’s–that is, an even number.
Next we consider sufficiency. Suppose that every vertex of G has even degree. We proceed by induction
on the size m of a (nontrivial) multigraph in which every vertex is even. If m = 2, then the multigraph
consists of two vertices joined by two edges, which has an eulerian circuit. Assume that every multigraph
of size less that m ≥ 3 and having only even degrees contains an eulerian circuit, and let G be such a
multigraph of size m.
If G hs order 2, then the two vertices are joined by an even number (at least 4) of edges and G is
eulerian. So we may assume that G has order at least 3, otherwise there is nothing left to prove. Hence
G contains a vertex v adjacent to distinct vertices u and w. Let H be the multigraph obtained from
G by deleting one of each of the edges uv and vw and adding an edge uw. The H has fewer than m
edges and every vertex in H has even degree.
If H is connected, then, by the inductive hypothesis, H contains an eulerian circuit C. We can now find
an eulerian circuit of G by replacing an edge uw on C by the deleted edges uv and vw.
On the other hand, if H is disconnected, then H contains two components, namely a component Hu
containing u and w and a (possibly trivial) component Hv containing v. By the inductive hypothesis,
Hu contains and eulerian circuit Cu and, if Hv is nontrivial, it contains an eulerian circuit Cv . We can
now find an eulerian circuit of G by replacing and edge uw by the deleted edge uv, then taking the
eulerian circuit Cv (if it exists) at v, and returning to w along the deleted edge uw.

A characterization of graphs containing eulerian trails can now be presented.

Section 5.2. Eulerian Graphs Page 48

Theorem 5.2.3 (Eulerian Trail).

Let G be a nontrivial connected multigraph. Then G contains an eulerian trail if and only if G has
exactly two odd vertices. Furthermore, the trail begins at one of these odd vertices and terminates at
the other.
Proof. Suppose G contains an eulerian trail. Let u and v be the starting and finishing vertices of the
trail. If we add an edge e joining the vertices u and v, we get an eulerian multigraph in which, by
Theorem 5.2.2, every vertex must have even degree. If we now recover G by removing e, we see that u
and v are the only two vertices of odd degree.
Conversely, suppose that G has exactly two odd vertices u and v. If we add an edge e joining the vertices
u and v, we get a connected multigraph in which every edge has even degree. By Theorem 5.2.2, this
graph is eulerian, and must therefore possess an eulerian circuit. Removal of e from this circuit produces
an open trail which includes every edge of G. Thus, G has an eulerian trail. Furthermore, this trail
begins at one of u or v and terminates at the other.

It follows from Theorem 5.2.2 and Theorem 5.2.3 that the multigraph of Figure 5.2 contains neither an
eulerian trail nor an eulerian circuit.

Learning Opportunities
5.1. In present day Königsberg (Kalingrad), there are two additional bridges, one between regions B
and C, and one between regions B and D. Is it now possible to devise a route over all bridges of
Königsberg without crossing any of them?
5.2. Show how the citizens of Königsberg could have built two new bridges in such a way that they
could have taken their tour and returned to their starting point.
5.3. For what positive integers n are the following graphs eulerian?
5.3.1. Cn
5.3.2. Kn
5.3.3. Km,n
5.4. Decide whether each of the following graphs has an eulerian circuit, eulerian trail, or neither.

5.5. Show that if a multigraph G has 2k vertices of degree, then the smallest number of continuous
penstrokes needed to covert all the edges of G is k.
Section 5.3. Fleury’s Algorithm Page 49

5.3 Fleury’s Algorithm

In this section we consider an algorithm designed to produce eulerian circuits. The disadvantage of
the proof of Theorem 5.2.2 is that it is not constructive, in the sense that it does not show us how to
construct an eulerian circuit in a given multigraph. One way of constructing an eulerian circuit is to use
the following algorithm due to Fleury. A proof of Fleury’s algorithm may be found in [6] or [26].

Algorithm 5.3.1 (Fleury).

If G is an eulerian graph, then the following steps can always be carried out, and produce an eulerian
circuit in G:
1. Choose a starting vertex x.
2. At each stage, traverse any available edge, choosing a bridge on if there is no alternative.
3. After traversing each edge, erase it (erasing any vertices of degree 0 which result), and then
choose another available edge.
4. Stop when there are no more edges.

This algorithm is very easy to apply. At each stage, we choose a bridge only as a last resort. The
postponing of the use of bridges is really the critical feature of this algorithm. This feature is clearly
essential, since once we have traversed a bridge, we cannot return to the part of the graph we have just
left.
We illustrate the use of Fleury’s algorithm by applying it to the graph of Figure 5.4(a).

Figure 5.4

Starting at x, we may choose the edge xa, followed by ab. Erasing the edges (and the vertex a) gives
us the graph shown in Figure 5.4(b). We cannot use the edge bx since it is a bridge, so we may choose
the edge bc, followed by cd and db. Erasing these edges (and the vertices c and d) gives the graph
shown in Figure 5.4(c). Now there is no alternative–we have to traverse the bridge bx. Traversing the
Section 5.4. The Chinese Postman Problem Page 50

cycle x, e, f, x completes the eulerian circuit. The circuit is therefore x, a, b, c, d, b, x, e, f, x.

Learning Opportunities
5.6. Using Fleury’s algorithm, find an eulerian circuit in the accompanying graph G.

5.4 The Chinese Postman Problem

A famous problem in graph theory is the so-called Chinese postman problem. (The word Chinese refers
to the problem, not the postman! The problem was formulated in 1962 by Meigu Guan.) It may be
stated as follows.
The Chinese Postman Problem. A postman collects mail at the post office, wishes to deliver the
mail along all streets in his area, and return to the post office. He must, of course, cover each street in
his area at least once. How can the route be planned in order to cover the smallest total distance?
Clearly, we can use a graph to model the mail route the postman must eventually cover, where the
intersections correspond to the vertices of the graph and two vertices are adjacent of the street that
joins the corresponding intersections does not meet the third intersection. We assign to each edge the
distance of the corresponding street. The Chinese postman problem can be phrased in therms of optimal
tours in weighted graphs defines as follows. (Recall that the length of a walk in a weighed graph is the
sum of the weights of the edges of the walk.)

Definition 5.4.1 (An Optimal Tour).

For a connected weighted graph G, a closed walk that uses each edge at least once is called a tour of
G. An optimal tour is a tour of minimum weight in G.

Using this definition, the Chinese postman problem becomes:

The Chinese Postman Problem. For a connected weighted graph G, find an optimal tour in G.
If the map of the postman’s area happens to correspond to an eulerian graph, then there is no difficulty
with this problem–the postman simply chooses an eulerian circuit (using Fleury’s algorithm), and such
a circuit will involve the smallest total distance. What usually happens in practise, of course, is that the
Section 5.4. The Chinese Postman Problem Page 51

postman needs to visit some parts of the route more than once, and wants to minimize the amount of
retracing.
Similar problems have arisen in other contexts. For example, there was a major study of snow-clearing
routes in Zurich some years ago. Since snow-clearing equipment is expensive to operate, it was necessary
to arrange a route which involved reclearing streets as little as possible. Other cities have initiated similar
investigation into the sweeping or cleaning of the streets.
If the graph under consideration is not an eulerian graph, then the Chinese postman problem can be
solved by a good algorithm provided by Edmonds and Johnson. However, their algorithm is too involved
to present here. To get an idea of what is involved, we consider the particular case of a graph with just
two odd vertices of odd degree.
Suppose that G is a connected weighted graph with exactly two vertices u and v of odd degree. Let
T be a tour of G. For each edge e of G, let m(e) + 1 be the number of times T traverses the edge e
(where we may have m(e) = 0). WE now form a new graph G∗ from G as follows: Let G∗ be obtained
from G by joining the ends of the edge e by m(e) new edges of weight w(e) for each edge e of G with
m(e) > 0. Now T may be transformed into an eulerian circuit T ∗ of G∗ : if an edge e needs to be
traversed n times by T in G, then there are n copies of this edge in G, and so we may replace each
occurrence of e in T by one of the n edges in such a way that none of them is repeated in T ∗ .
So G∗ is an eulerian graph. Thus by Theorem 5.2.2, every vertex of G∗ has even degree. But u and v
have odd degree in G. Hence at least one new edge incident with u, and at least one edge incident with
v, must have been added to G to produce G∗ . Let E ∗ be the set of edges of G8 that do not belong
to G, so E ∗ = E(G∗ ) − E(G). WE now consider the subgraph H formed by the edges in E ∗ . (So the
edge set of H is E ∗ , and the vertex set of H consists of those vertices that are incident with some edge
in E ∗ .) Necessarily, each of u and v is in H. Observe that for each vertex w of H, the degree of w in
H is given by

degH w = degG∗ w − degG w

Furthermore, degG∗ w is even and if w is distinct from u and v, then degG w is even, while degG w is
odd if w = u or w = v. It follows that u and v are the only vertices of H of odd degree. This means
(see Corollary 1.5.4) that u and v must lie in the same component of H. Hence u and v are connected
by a u-v path P ∗ (say) in H. (Note that this path P ∗ consists solely of new (duplicated) edges of G.)
Now
X X
w(T ) = w(e) + w(e)
e∈E(G) e∈E(G∗ )

w(e) + w(P ∗ )
X
≥
e∈E(G)
X
≥ w(e) + w(P ),
e∈E(G)
X
where P is a shortest u-v path in G. Thus, w(e) is a minimum when G∗ is obtained from G by
e∈E(G∗ )
duplicating each of the edges on a shortest u-v path in G. (In other words, the best situation would be
for H to contain a shortest u-v path and nothing else.) Thus T is an optimal tour if it is an eulerian
circuit of the graph G∗ obtained from G by duplicating each of the edges on a shortest u-v path.
Section 5.4. The Chinese Postman Problem Page 52

Algorithm 5.4.2 (Edmonds and Johnson).

If G is a connected, weighted graph with exactly two vertices u and v of odd degree, then the following
steps will produce an optimal tour in G.
1. Find a shortest u-v path P in G (use Dijkstra’s algorithm).
2. Form a new (eulerian) graph G∗ by adding to G a duplicate of each edge occurring in P .
3. Find an eulerian circuit T ∗ of G∗ (use Fleury’s algorithm).
4. Interpret T ∗ as an (optimal) tour of G with some repeated edges.

We illustrate the use of Algorithm 5.4.2 by applying it to the graph of Figure 5.5.

Figure 5.5

Observe that G has exactly two vertices of odd degree, namely a and b. We apply Dijkstra’s algorithm to
determine a shortest a-b path in G. Table 5.1 given below has four columns corresponding to the vertices
b, c, d, e. The ordered pairs in the columns corresponding to the vertex v indicate (ℓ(v), parent(v)) at
a given point in the algorithm.

ℓ(a) b c d e removed from S S

0 (∞, −) (∞, −) (∞, −) (∞, −) − V (G)
(7, a) (∞, −) (2, a) (7, a) a {b, c, d, e}
(7, a) (3, d) (6, d) d {b, c, e}
(6, c) (6, d) c {b, e}
(6, d) b {e}

Table 5.1

On applying Dijkstra’s algorithm, we find that d(a, b) = 6 and that P : a, d, c, b is a shortest a-b path
in G. We now for the multigraph G∗ by duplicating the edges ad, dc, and cb in the graph G of Figure
5.5. The multigraph G∗ is shown in Figure 5.6.
Section 5.4. The Chinese Postman Problem Page 53

Figure 5.6

We now apply Fleury’s algorithm to the eulerian multigraph G∗ shown in Figure 5.6. Starting at a,
we may choose the edge e1 = ae, followed by e2 = ed(a bridge, but there is no alternative), e3 = da,
e4 = ad, and e5 = db. We now cannot use the edge ba since it is a bridge, so we may choose one of
the edges bc, say e6 = bc. Since cb is a bridge of the resulting graph, we must traverse cd, say e7 = cd.
Traversing the path d, c, b, a completes the eulerian circuit, so we choose e8 = dc, e9 = cb and e10 = ba.
The circuit T ∗ is therefore

T : a, e1 , e, e2 , d, e3 , a, e4 , d, e5 , b, e6 , c, e7 , d, e8 , c, e9 , b, e10 , a

Lastly, we interpret T ∗ as a tour of G by identifying duplicated edges, that is to say, we set e3 = e4 ,

e6 = e9 and e7 = e8 . This yields the optimal tour

T : a, e, d, a, d, b, c, d, c, b, a

of G weight w(T ) = 25.

Section 5.4. The Chinese Postman Problem Page 54

Learning Opportunities
5.7. Use Algorithm 5.4.2 to find optimal tours in weighted graphs G and H shown in the accompanying
figure.
6. Planar Graphs
6.1 Introduction
In this chapter, we consider graphs that can be drawn in the plane without their edges crossing. Such
graphs we call planar graphs.
Definition 6.1.1 (A Planar Graph).
A planar graph is a graph that can be drawn in the plane in such a way that no two edges meet each
other except at a vertex to which they are both incident. A graph that is drawn in the plane is said to
be embedded in the plane. A planar graph that is embedded in the plane is called a plane graph.

The graph G ≡ K4 of Figure 6.1(a) is drawn with intersecting edges. Nevertheless, G is a planar graph
because it can be drawn in the plane without any of its edges intersecting. Figure 6.1(b) shows G
redrawn with no edges crossing. Thus, the graph of Figure 6.1(a), though planar, is not a plane graph.
On the other hand, the graph of Figure 6.1(b) is a plane graph. The drawing of a planar graph in the
plane is not unique. Indeed, a given planar graph can give rise to several different plane graphs.

Figure 6.1: A planar graph.

Planar graphs have many practical applications, such as to circuit layout problems. In the design of
electronic chips, we wish to locate several nodes on a circuit board (a flat board of insulating material)
and connect certain pairs of these nodes by electrical wires (or conducting strips) printed directly onto
the circuit board. The electrical wires may not cross, since this would lead to undesirable electrical
contact at crossing points. Can we connect the nodes in such a way that no two of the connecting wires
cross? In graph theory terms, the problem is to determine whether the graph associated with the circuit
(where vertices represent nodes, and edges correspond to electrical wires connecting pairs of nodes) is
planar.
Another area where planar graphs are important is in utility problems. Suppose, for example, we have
three houses and three utilities, namely, electricity, gas, and water. Is it possible to connect each utility
with each of the three houses without the utility lines crossing? This well-known problem is referred to
as the Three Houses and Three Utility Problem. This situation can be represented by the complete
bipartite graph K3,3 .

55
Section 6.2. Properties of Planar Graphs Page 56

Figure 6.2: The graph K3,3

So the Three Houses and Three Utility Problem can be restated in graph theory terms: Is K3,3 a planar
graph? We will return to question once we have established a few basic results about planar graphs.
We close this introduction to planar graphs with the following poem:
In Central Spain, in mainly rain
Three houses stood upon the plain
The houses of our mystery
To which, from realms of industry
Came wires with power light and heat
And pipes with gas to cook their meat
And other pipes with water sweet.

The owners said. “Where these things cross,

Burn, leak or short, we’ll suffer loss.
So let a graphman living near
Plan each from each to keep them, clear.”

Tell them graphman, come in vain,

They’ll bear one cross that must remain
Explain the planeness of the plain.

6.2 Properties of Planar Graphs

In this subsection, we present some properties of planar graphs. We begin with a formula developed by
Euler which plays a central role in the study of planar graphs. First, we introduce some definitions.
Section 6.2. Properties of Planar Graphs Page 57

Definition 6.2.1 (Regions).

Given a plane graph G, the regions of G are the connected pieces of the plane that remain after we
remove the vertices and the edges of G. Every plane graph contains exactly one unbounded region,
which we call the exterior region. The vertices and the edges of G that are incident with a region R
form a subgraph called the boundary of R.

To illustrate these concepts, consider the plane graph G of Figure 6.3. The plane graph G has five
regions, labelled R1 , R2 , . . . , R5 . The boundary of R1 consists of four vertices v1 , v2 , v8 , v9 , and four
edges v1 v2 , v2 v9 , v9 v8 , v8 v1 . The boundary of the exterior region consists of all the vertices of G, except
v9 , and the eight edges v1 v2 , v2 v3 , v3 v4 , v3 v5 , v5 v6 , v6 v7 , v7 v8 and v8 v1 . Observe that each cycle edge
belongs to the boundary of two regions, while each bridge is on the boundary of only one region.

Figure 6.3: Boundaries of regions.

The plane graph G of Figure 6.3 has n = 9 vertices, m = 12 edges, and r = 5 regions. Thus, the graph
G satisfies n − m + r = 2. This equality always hold in a connected plane graph. This well-known
formula was discovered by Euler [10] in 1752, and it is a classical result of graph theory.

Theorem 6.2.2 (Euler’s Formula).

If G is a connected plane graph with n vertices, m edges and r regions, then

n − m + r = 2.
Proof. We proceed by induction on m. If m = 0, then G ≡ K1 ; so n = 1, r = 1 and n − m + r = 2.
Thus, the result is true if m = 0. Assume that the result holds for all connected plane graphs with fewer
than m edges, where m ≥ 1, and let G be a connected plane graph with m edges. Suppose that G has
n vertices and r regions. We show that n − m + r = 2. If G is a tree, then r = 1 and, by Theorem
4.2.2, m = n − 1, so n − m + r = n − (n − 1) + 1 = 2, and we have the desired formula. On the other
hand, if G is not a tree, then G contains a cycle edge e. Then G − e is a connected plane graph with
n vertices and m − 1 edges. Furthermore, the two regions incident with e in G produce one region in
Section 6.2. Properties of Planar Graphs Page 58

G − e, so G − e has r − 1 regions. Applying the inductive hypothesis to G − e we have

n − (m − 1) + (r − 1) = 2,

or, equivalently, n − m + r = 2.

It follows from Theorem 6.2.2 that no matter how a connected planar graph is embedded on the plane,
the number of regions of the resulting plane graph is always the same. Thus one can speak of the
number of regions of a planar graph. Our next result shows that a planar graph on a fixed number n of
vertices cannot have too many edges.
Theorem 6.2.3.
If G is a planar graph with n ≥ 3 vertices and m edges, then

m ≤ 3n − 6.

Proof. Consider an embedding of G in the plane (as a plane graph), resulting in r regions. Every edge
lies on the boundary of either one or two regions. Therefore, if the number of edges on the boundary
of a region is summed over all the regions, the result is at most 2m. However, the boundary of every
region contains at least three edges, so such a sum is a least 3r. Hence, 3r ≤ 2m, or r ≤ 2m
3 . Applying
Theorem 6.2.2, we obtain
2m m
2=n−m+r ≤n−m+ =n− .
3 3
Therefore, m ≤ 3n − 6.

We are now in a position to return to our question of whether or not the graph K3,3 is planar.

Theorem 6.2.4.
The graph K3,3 is nonplanar.

Proof. Assume, to the contrary, that K3,3 is planar. Consider any embedding of K3,3 on the plane,
resulting in r regions. Since K3,3 is a bipartite graph, it has no triangles; so the boundary of every region
contains at least four edges. Let x be the number of edges on the boundary of a region summed over all r
regions. Then x ≥ 4r. However, since K3,3 contains no bridges, every edge lies on a boundary of exactly
two regions. Thus, the sum x counts each edge twice; that is, x = 2m = 18. Therefore, 4r ≤ x = 18,
or, equivalently, r ≤ 29 . Thus, r ≤ 4. However, by Theorem 6.2.2, r = 2 + m − n = 2 + 9 − 6 = 5.
This produces a contradiction. We deduce, therefore, that K3,3 is nonplanar.

Theorem 6.2.5.
The graph K5 is nonplanar.
Proof. Assume, to the contrary, that K5 is planar. Since K5 has n = 5 vertices and m = 10 edges,

10 = m > 3n − 6 = 9,

which contradicts the result of Theorem 6.2.3. Thus, K5 is nonplanar.

We close this subsection wit a well-known characterization of planar graphs due to Kuratowski. For this
purpose, we define a relation on a graph called a subdivision.
Section 6.2. Properties of Planar Graphs Page 59

Definition 6.2.6 (Subdivision).

A subdivision of a graph is the graph obtained by inserting vertices (of degree 2) into the edges of
the graph.

For the graph G of Figure 6.4, the graph H is a subdivision of G.

Figure 6.4: Subdivisions of graphs

We are now in a position to state Kuratowski’s Theorem. However, we omit the proof which is too
involved and lengthy to present here.
Theorem 6.2.7 (Kuratowski’s Theorem).
A graph is planar if and only if it contains no subgraph that is isomorphic to a subdivision of K5 or
K3,3 .

Learning Opportunity
6.1. Suppose the Three Houses and Three Utilities problem were the Four Houses and Two Utilities
problem. What would the solution be?
6.2. Show that the graph K2,n is planar for every positive integer n.
6.3. For the plane graph G in the accompanying figure, determine the vertices and the edges of the
boundary of the exterior region.
Section 6.3. The Four Colour Problem Page 60

6.4. Show that the graph obtained from K5 by removing an edge is planar.
6.5. For which values of n is the complete graph Kn planar?
6.6. Prove or disprove: If G is a connected graph on n vertices and m edges with m = 3n − 6, then
G is planar.
6.7. .
6.7.1. Show that if a shortest cycle in a planar graph with n vertices and m edges has length k,
then
k(n − 2)
m≤ .
k−2

6.7.2. Deduce that a planar bipartite graph of order n ≥ 4 has at most 2n − 4 edges.
6.7.3. Use this result to show that K3,3 is nonplanar.
6.8. Prove that if a graph G and its complement G are both planar, then G has at most 10 vertices.

6.3 The Four Colour Problem

In this section, we discuss a problem which at one time was the most famous unsolved problem, not
only in graph theory, but, perhaps even in the whole of mathematics.
The Four Colour Problem. Can any map on the plane (or sphere) be coloured with four or fewer
colours so that adjacent countries (those sharing a common boundary, not just a point) are coloured
differently?
The Four Colour Problem dates back to 1852. In the July 17, 1879 issue of the journal, Nature came the
announcement that the Four Colour Problem had been solve by Alfred Kempe, a London barrister and
keen amateur mathematician. Kempe’s proof of the fact that every map can be coloured with 4-colours
was published in an 1879 issue of the American Journal of Mathematics [20] and an 1880 issue of
Nature [19]. For this remarkable accomplishment, Kempe was knighted and made a fellow of the Royal
Society. However, in 1890, Percy Heawood [17] discovered and error in Kempe’s proof – an error so
serious that he was unable to repair it. The problem was finally solve in June 21, 1976 by Kenneth
Appel and Wolfang Haken [1] who announced that they had solve the Four Colour Problem. Their proof
required over 1200 hours of computer calculations produce a proof running to several hundred pages
and some 10 000 diagrams. However, to date there does not exist a purely mathematical proof showing
that every map can be coloured with four or fewer colours.
The Four Colour Problem can be rephrased in graph theoretical terms. To do this, we define a colouring
in a graph.
Definition 6.3.1 (Colouring).
A colouring of a graph G is an assignment of colours (elements of some set) to the vertices of G, one
colour to each vertex, so that adjacent vertices are assigned distinct colours. If n colours are used,
then the colouring is referred to as an n-colouring. A graph G is k-colourable if there exists an
n-colouring for some n ≤ k.
Section 6.3. The Four Colour Problem Page 61

We now return to the Four Colour Problem. With each map, we can associate a graph G whose vertices
correspond to the countries, and where two vertices are adjacent if the corresponding countries are
adjacent. Such a graph G is a planar graph. The Four Colour Problem can thus be restated as follows:
Theorem 6.3.2 (The Four Colour Theorem).
Every planar graph is 4-colourable.

Although the Four Colour Problem is difficult to solve, Heawood [17] was able to prove the Five Colour
Theorem with surprising ease. To prove this theorem, the following result is useful.
Theorem 6.3.3.
Every planar graph contains a vertex of degree at most 5.
Proof. Let G be a planar graph with n vertices and m edges, and with V (G) = {v1 , v2 , . . . , vn }. If
n ≤ 6, then the degree of every vertex is at most 5. So we may assume that n ≥ 7. By Theorem 6.2.3,
m ≤ 3n − 6. Therefore,
n
X
deg vi = 2m ≤ 6n − 12.
i=1

If all the vertices of G have degree 6 or more, then

n
X
2m = deg vi ≥ 6n,
i=1

which is a contradiction. Hence G must contain a vertex of degree 5 or less.

Theorem 6.3.4 (The Five Colour Theorem).

Every planar graph is 5-colourable.
Proof. We proceed by induction on the order n of a planar graph. The cases when 1 ≤ n ≤ 5 are
trivial. Assume that all planar graphs of order less than n, where n ≥ 6, are 5-colourable, and let G be
a planar graph of order n. By Theorem 6.3.3, G contains a vertex v of degree 5 or less. Consider an
embedding of G in the plane. Then G − v is a plane graph of order less than n. Applying the inductive
hypothesis, G − v is 5-colourable. Consider a 5-colouring of G using the colours 1, 2, 3, 4 and 5. If one
of these colours is not used colouring the vertices adjacent with v, then this colour may be assigned to
v to produce a 5-colouring G. Thus, we may assume that deg v = 5 and that v is surrounded by five
vertices each coloured with a different colour.
Suppose that v1 , v2 , v3 , v4 , v5 are the five vertices adjacent with v, arranged cyclically about v. We may
assume that vi is coloured with colour i, 1 ≤ i ≤ 5. We show that it is possible to recolour some
vertices of G − v so that a colour become available for v. Consider the set of vertices of G − v that are
coloured with colours 1 or 3.
Section 6.3. The Four Colour Problem Page 62

Figure 6.5

Suppose there is no v1 -v3 path in G − v all whose vertices are coloured 1 or 3 (see Figure 6.5(a)). Let
H be the subgraph consisting of all paths that start at v1 all whose vertices are coloured 1 or 3. Then
v3 does not belong to H. Moreover, no vertex adjacent to v3 is in H. We now interchange the colours
of the vertices of H. This produces a new 5-colouring of G − v in which both v1 and v3 are coloured
with colour 3. Thus, we may assign colour 1 to v produce a 5-colouring of G.
On the other hand, suppose there is a v1 -v3 path P in G − v all whose vertices are coloured 1 or 3
(see Figure 6.5(b)). The path P together with the path v3 , v, v1 produces a cycle in G which either
encloses v2 or encloses v4 and v5 . Hence there does not exist a v2 -v4 path in G − v all whose vertices
are coloured 2 or 4. Let F be a subgraph consisting of all paths that start at v2 all of whose vertices are
coloured 2 or 4. This subgraph does not contain v4 or any vertex adjacent with v4 Interchanging the
colours of the vertices of F produces a new 5-colouring of G − v in which both v2 and v4 are coloured
with colour 4. Thus, we may assign colour 2 to v to produce a 5-colouring of G.

Learning Opportunities
6.9. What is the smallest order of a graph that is 4-colourable?
6.10. Show that there exists a planar graph that contains no vertex of degree 4 or less.
6.11. Show that every planar graph of order at least 2 contains at least two vertices of degree 5 or less.
7. Hamiltonian Graphs
7.1 Introduction
In this chapter, we turn our attention to hamiltonian graphs – graphs in which there is a cycle passing
through every vertex. The name “hamiltonian” is derived from a game invented by the famous Irish
mathematician Sir William Rowan Hamilton. In 1867, Hamilton introduced a game consisting of a solid
regular dodecahedron (see Figure 7.1) made of wood, twenty pegs (one inserted at each vertex), and a
supply of string. Every vertex was given a name of an important city of the time – Brussels, Canton,
Delhi, . . . , Zanzibar. The aim of the game called “A Voyage Round the World”, was to find a route
along the edges of a dodecahedron that visits each city exactly once and that ended at the city where
it began. In order for the player to keep track of the cities visited, the player used the string to join the
pegs in the order in which the route was traversed. Hamilton sold the idea of his game to a wholesale
dealer of game and puzzles for £25. However the game did not prove to be very popular, possibly
because a desired route is easy to find.

Figure 7.1: The graph of a dodecahedron.

The above game suggests the graphical concept which we term as “hamiltonian”.
Definition 7.1.1 (Hamiltonian Cycle, Hamiltonian Graph, Hamiltonian Path).
A cycle of a graph G containing every vertex of G is called a hamiltonian cycle. A hamiltonian
graph is a graph possessing a hamiltonian cycle. A path of G containing every vertex of G is called a
hamiltonian path.

Thus, A Voyage Round the World game asks the player to find a hamiltonian cycle in a graph of the
dodecahedron. An earlier example of a problem which can be expressed in terms of hamiltonian cycles
is the knight’s tour problem.
Knight’s Tour Problem. Can a knight visit each square of a standard 8 × 8 chessboard exactly once
by a sequence of knight’s moves, and finish on the same square as it began?
In order to see the connection between this problem and that of finding hamiltonian cycles in graphs,
note that the knight’s tour problem can be represented by a graph in which each vertex corresponds
to a square of the chessboard, and edges correspond to those pairs of squares connected by a knight’s

63
Section 7.2. Which Graphs Are Hamiltonian? Page 64

move. The resulting graph, which has order 64 and size 186, actually contains several hamiltonian
cycles. Figure 7.2 illustrates one such knight’s tour on a standard 8 × 8 chessboard.

Figure 7.2: A knight’s tour on an 8 × 8 chessboard.

7.2 Which Graphs Are Hamiltonian?

The problem of deciding whether or not a given graph is hamiltonian seems similar to the problem of
deciding whether or not a graph is eulerian. Since there is a simple characterization for eulerian graphs,
one might expect there to be a simple characterization for hamiltonian graphs. Unfortunately, no such
characterization is known. To date, there is no known condition that is both necessary and sufficient for
a graph to be hamiltonian. Indeed, the problem of finding an applicable characterization of hamiltonian
graphs is considered one of the major problems in graph theory.
If G is a hamiltonian graph, then G contains a hamitonian cycle. Hence a necessary condition for G to
be hamiltonian is that G is certainly connected, has no cut-vertices and, of course, has order at least 3.
There have been several sufficient conditions established for a graph to be hamiltonian. For a graph G
of order at least 3, it seems logical that the more edges G has, the more likely it is to be hamiltonian.
The simplest such condition is due to Dirac [9]. The proof technique employed is typical of the type of
proof one uses to prove that a graph is hamiltonian. (Recall that the minimum degree in a graph G is
denoted by δ(G).)

Theorem 7.2.1 (Dirac’s Theorem).

Let G be a graph of order n ≥ 3. If δ(G) ≥ n2 , then G is hamiltonian.

Proof. If n = 3, then δ(G) ≥ 2. This implies that G ≡ K3 and, hence, G is hamiltonian. So we may
assume that n ≥ 4, for otherwise there is nothing left to prove.
Let P : v1 , v2 , . . . , vp be a longest path in G. Then every vertex adjacent to v1 lies on P and every
vertex adjacent to vn lies on P ; otherwise there would be a longer path than P . Hence,
n
p = |V (P )| ≥ deg v1 + 1 ≥ δ(G) + 1 ≥ + 1.
2
We show that there must exist some vertex vi , where 2 ≤ i ≤ p, such that v1 is adjacent to vi , and vp
is adjacent to vi−1 . If this is not the case, then, whenever v1 is adjacent tp a vertex vi , the vertex vp
is not adjacent to vi−1 . Since at least n2 vertices are adjacent to to v1 , at least n2 of the n − 1 vertices
different from vp are not adjacent to vp . Hence,
Section 7.2. Which Graphs Are Hamiltonian? Page 65

n n
deg vp ≤ |V (P ) − {vp }| − deg v1 ≤ (n − 1) − <
2 2
which contradicts the fact that deg vp ≥ δ(G) ≥ n2 . Hence, as claimed, there must exist some vertex
vi (2 ≤ i ≤ p) adjacent to v1 with vi−1 adjacent to vp . Thus, G has a cycle

C : v1 , vi , vi+1 , . . . , vp , vi−1 , vi−2 , . . . , v2 , v1

that contains all the vertices of P . We show that C is a hamiltonian cycle of G. If this is not the
case, then there is some vertex u of G that does no belong to C. By hypothesis, deg u ≥ n2 . Since P
contains p ≥ n2 + 1 vertices, there are fewer than n vertices not on C. So u must be adjacent to some
vertex v that lies on C. However, the edge uv together with the cycle C contain a path whose length
exceeds that of P , which contradicts our choice of P . Hence C contains all the vertices of G. Thus, G
is hamiltonian.

The sufficient condition in Theorem 7.2.1 is not necessary condition for a graph to be hamiltonian. For
example, the cycles Cn (n ≥ 5) are hamiltonian but have minimum degree 2, which is less than n2 .
Many other hamiltonian graphs cannot be shown to be hamiltonian using Theorem 7.2.1.
A corresponding degree condition to that presented in Theorem 7.2.1 also exists to prove that a graph
has a hamiltonian path.
Corollary 7.2.2.
n−1
Let G be a graph of order n. If δ(G) ≥ 2 , then G contains a hamiltonian path.

Proof. If n = 1, then G ≡ K1 , and G contains a (trivial) hamiltonian path. So we may assume that
n ≥ 2, for otherwise there is nothing left to prove. Let H be the graph obtained from G by adding a
new vertex v and joining v with an edge to every vertex of G. Then H has order n + 1, so v has degree
n in H. Moreover, for every vertex u of G,

n−1 n+1 |V (H)|

degH u = degG u + 1 ≥ +1= = .
2 2 2
Hence H is a graph of order n + 1 with δ(H) ≥ n+1
2 . By Theorem 7.2.1, we know therefore that H
contains a hamiltonian cycle C. By removing the vertex v from C, we obtain a hamiltonian path in
G.

If G is a bipartite hamiltonian graph with partite sets V1 and V2 , then it follows that |V1 | = |V2 | (see
Learning Opportunity 7.5). Corollary 7.2.2 extents Dirac’s Theorem 7.2.1 to this class of graphs.
Theorem 7.2.3.
n
Let G be a bipartite graph with partite sets V1 and V2 such that |V1 | = |V2 | = n ≥ 2. If δ(G) > 2,
then G is hamiltonian.
Proof. Assume, to the contrary, that the theorem is false. Then there exists a nonhamiltonian bipartite
graph G satisfying the hypothesis of the theorem. Let G be maximal such graph; that is, G is a
nonhamiltonian bipartite graph but the addition of any edge between the two partite sets would make it
hamiltonian. Since Kn,n is hamiltonian, the graph G must contain a pair u, v of nonadjacent vertices
with u ∈ V1 and v ∈ V2 .
Section 7.3. The Closure Function Page 66

The maximality of G implies that G + uv has a hamiltonian cycle, which must contain the edge uv.
Hence, G contains a hamiltonian u-v path

P : u = v1 , v2 , . . . , v2n = v,

where vi ∈ V1 if i is odd and vj ∈ V2 if j is even (since G is bipartite). If v1 vi ∈ E(G), where 2 ≤ i ≤ 2n

and i is even, then vi−1 v2n ∈
/ E(G); for otherwise

v1 , vi , vi+1 , . . . , v2n−1 , v2n , vi−1 , vi−2 , . . . , v2 , v1

is a hamiltonian cycle of G (which would contradict the fact that G is nonhamiltonian). Hence for each
vertex of {v2 , v4 , . . . , v2n } adjacent to v1 , there is a vertex of {v1 , v3 , . . . , v2n−1 } not adjacent to v2n .
Thus,
n n
deg v2n ≤ n − deg v1 < n − = ,
2 2
which contradicts the hypothesis.

Learning Opportunities
7.1. Prove that it is not possible for a knight to tour a 4 × 4 chessboard, visit each square exactly
once, and return to the initial square.
7.2. Prove that if n is odd, then it is not possible for a knight to tour an n × n chessboard, visit each
square exactly once, and return to the initial square.
7.3. Prove that Kn,n+1 is hamiltonian for every positive integer n.
7.4. Use 7.3. to show that lowering the bound of Theorem 7.2.1 from n2 to n2 − 1 will not guarantee
that the graph G is hamiltonian. (Thus, the bound n2 in Theorem 7.2.1 is “sharp”.)
7.5. Show that if G is a hamiltonian bipartite graph with partite sets V1 and V2 , the |V1 | = |V2 |.
7.6. Show that the bouind presented in Theorem 7.2.3 is sharp by finding a class of nonhamiltonian
bipartite graphs G with partite sets V1 and V2 such that |V1 | = |V2 | = n ≥ 2 and δ(G) ≥ n2 .
7.7. A mouse eats his way through a 3 × 3 × 3 cube of cheese, tunnelling through all 27 of the 1 × 1 × 1
cubes. If the mouse starts at a corner, can he finish at the centre?

7.3 The Closure Function

We begin this section by presenting the following result, which was first observed by Bondy and Chvátal.
This can be proved using the same technique employed in the proofs of Theorems 7.2.1 and 7.2.3.
Theorem 7.3.1.
Let u and v be distinct nonadjacent vertices of a graph G of order n ≥ 3 such that deg u + deg v ≥ n.
Then G is hamiltonian if and only if G + uv is hamiltonian.
Proof. If G is hamiltonian, then certainly so too is G + uv. Conversely, suppose that G + uv is
hamiltonian. Let C be a hamiltonian cycle of G + uv. If does not contain the edge uv, then C is
a hamiltonian cycle of G and G is hamiltonian. So we may assume that C contains the edge uv,
for otherwise there is nothing left to prove. Now P = C − uv is a hamiltonian u-v path of G, i.e.,
P : u = v1 , v2 , . . . , vn = v (say) contains every vertex of G.
Section 7.3. The Closure Function Page 67

We show that there must exist some vertex vi , where 2 ≤ i ≤ p, such that v1 vi ∈ E(G), and vi−1 vp ∈
E(G). If this is not the case, then, whenever v1 vi ∈ E(G), 2 ≤ i ≤ p), we have vi−1 vp ∈ / E(G). Hence
for each vertex of {v2 , v3 , . . . , vp } adjacent ot v1 there is a vertex of {v1 , v2 , . . . , vp−1 } not adjacent to
vp . Thus, deg un ≤ (n − 1) − deg ui so that
deg u + deg v ≤ n − 1,
which is a contradiction. Hence there must exist some vertex vi (2 ≤ i ≤ p) such that v1 vi ∈ E(G),
and vi−1 vp ∈ E(G). Thus,
v1 , vi , vi+1 , . . . , vp , vi−1 , vi−2 , . . . , v2 , v1
is a hamiltonian cycle of G and G is hamiltonian.

Theorem 7.3.1 motivates the following definition.

Definition 7.3.2 (Closure).
The closure of a graph G of order n, denoted by c(G), is the graph obtained from G by recursively
joining pairs of nonadjacent vertices whose degree sum is at least n (in the resulting graph at each
stage) until no such pair remains.

The closure function is illustrated in Figure 7.3.

Figure 7.3: The closure function.

We show next that the closure c(G) is well-defined.

Theorem 7.3.3.
If G1 and G2 are two graphs obtained from a graph G of order n ≥ 3 by recursively joining pairs of
nonadjancent vertices whose degree sum is at least n, then G1 = G2 .
Proof. Let e1 , e2 , . . . , em and f1 , f2 , . . . , fp be the sequence of edges added to G to obtain G1 and
G2 , respectively. We show that each ei (1 ≤ i ≤ m) is an edge of G2 and that each fj (i ≤ j ≤ p) is
a edge of G1 . Suppose that some edge ei does not belong to G2 . Let t be the smallest integer such
that et+1 = uv. Let H = G + {e1 , e2 , . . . , et }. Then H is a subgraph of both G1 and G2 . Further, it
follows from the definition of G1 that
degH u + degH v ≥ n.
Therefore,
degG2 u degG2 v ≥ degH u + degH v ≥ n.
This is a contradiction, however, since u and v are nonadjacent vertices of G2 . Hence each edge ei
belongs to G2 . Similarly, each edge fj belongs to G1 . Hence G1 = G2 .
Section 7.3. The Closure Function Page 68

Our next theorem is a simple consequence of the definition and Theorem 7.3.3.
Theorem 7.3.4.
A graph is hamiltonian if and only if its closure is hamiltonian.
Proof. If we apply Theorem 7.3.4 every time an edge is added in the formation of the closure, then we
see that a graph G is hamiltonian if and only if c(G) is hamiltonian.

Since each complete graph with at least three vertices is hamiltonian, we obtain the following sufficient
condition, due to Bondy and Chvátal, for a graph to be hamiltonian.
Corollary 7.3.5.
Let G be a graph of order n ≥ 3. If c(G) ≡ Kn , then G is hamiltonian.

Another consequence of Theorem 7.3.4 is due to Ore.

Corollary 7.3.6.
If deg u + deg v ≥ n for all pairs u, v of nonadjacent vertices of a graph G of order n ≥ 3, then G is
hamiltonian.
Proof. Since the closure of G is complete, the result follows from Corollary 7.3.5.

Corollary 7.3.7.
Let G be a graph of order n ≥ 3 and size m. If
!
n−1
m≥ + 2,
2

then G is hamiltonian.
Proof. If G is complete, then G is hamiltonian. So we may assume that G is not complete and that
G satisfies the hypothesis of the corollary. Let u and v be two distinct nonadjacent vertices of G, and
define H = G − {u, v}. Then m(G) = m(H) + deg u + deg v. So, since
!
n−2
m(H) ≤ m(Kn−1 ) = ,
2

it follows that
! !
n−1 n−2
deg u + deg v = m(G) − m(H) ≥ +2− = n.
2 2

Hence, by Corollary 7.3.6, G is hamiltonian.

Learning Opportunities
7.8. Let u and v be distinct nonadjacent vertices of a graph G of order n ≥ 3 such that deg u+deg v ≥
n − 1. Prove or disprove: The graph G has a hamiltonian path if and only if G + uv has a
hamiltonian path.
7.9. Prove that if G is a hamiltonian graph, then for every proper nonempty subset S of the vertices
of G, k(G − S) ≤ |S|.
Section 7.3. The Closure Function Page 69

7.10. Decide whether each of the following graphs has a hamiltonian cycle, a hamiltonian path, or
neither.

7.11. Show that if a graph of order at least 3 has an isolated vertex, then its closure is not complete.
7.12. Show that the bound presented in Corollary 7.3.6 is sharp by finding a a class of nonhamiltonian
graphs of order n ≥ 3 such that deg u + deg v ≥ n − 1 for all pairs u, v of nonadjacent vertices
of G.
7.13. Show that the bound
presented in Corollary 7.3.7 is sharp by finding a nonhamiltonian graph of
order n ≥ 3 with n−1
2 + 1 edges.
7.14. Let G be a bipartite graph with partite sets V1 and V2 such that |V1 | = |V2 | = n ≥ 2. Let u and
v be nonadjacent vertices of G with u ∈ V1 and v ∈ V2 such that deg u + deg v > n. Show that
G is hamiltonian if and only if G + uv is hamiltonian.
7.15. Define the bipartite closure of a bipartite graph with partite sets V1 and V2 such that |V1 | =
|V2 | = n ≥ 2. Show that the bipartite closure is unique.
8. Networks
8.1 Introduction
You are designing an oil pipeline. Oil is to be pumped from an unloading point s to a refinery t. To
minimize the possibility that pipe repairs will completely halt the flow of oil, there will be several routes.
There will be four stations u, v, x and y along the pipelines, which are linked as shown in Figure 8.1.
The arrows indicate the directions in which oil can flow and the capacities of the section of pipelines
are indicates (in 1000 barrels of oil per hour). The question we are faced with is to determine what is
the maximum volume of oil can be pumped into the system (through s) per hour? In the section, we
shall develop a method of solving problems of this type.

Figure 8.1

8.2 Digraphs
Although many problems lend themselves to a graph-theoretic formulation, the concept of a graph is
sometimes not quite adequate. When dealing with problems of traffic flow, for example, it is necessary
to show which roads are one-way, and in which direction traffic is permitted. We may deal with problems
involving flow in information or water, transport of some commodity, etc. To deal with such problems,
what we need is a graph in which every edge has been assigned a direction – “a digraph”. The terminology
used for digraphs is quite similar to that used for graphs.
Definition 8.2.1 (Digraph).
A digraph (or directed graph) D is a finite set of objects, called vertices, together with a (possibly
empty) set of ordered pairs of distinct vertices of D, called arcs (or directed edges). As with graphs,
the vertex set of D is denoted by V (D) and its arc set by E(D). If D has vertex set V and arc set E,
we write D = (V, E). The cardinality of the vertex set of D is called the order of D and is denoted
by n(D), or simply n, while the cardinality of its arc set is called its size, and is denoted by m(D), or
simply m.
As with graphs, digraphs can be represented by diagrams. The vertices of a digraph D are indicated by

70
Section 8.2. Digraphs Page 71

small circles, and an arc (uv) of D is represented by a curve or line segment directed by an arrow-head
from vertex u to vertex v. Since (u, v) and (v, u) are distinct arcs, two vertices can be joined by two
arcs if they have opposite direction.
Definition 8.2.2 (Underlying Graph).
With each digraph D, we can associate a graph G (on the same vertex set) called the underlying
graph of D that is obtained from D by deleting all directions from the arcs of D (equivalently, replacing
each arc (u, v) by the edge uv) and deleting an edge from a pair of multiple edges if multiple edges
should be produced.

A digraph D with V (D) = {u, v, w, x} and arc set E(D) = {(u, v), (v, u), (v, w), (x, v), (x, w)} is
shown in Figure 8.2 along with the underlying graph G of D.

Figure 8.2: A digraph D and its underlying graph G.

Definition 8.2.3.
If (u, v) is an arc of D, then we say that u is adjacent to v, and v is adjacent from u. Further, the
arch (u, v) is incident from u and incident to v. The outdegree, denoted od(v), of a vertex v in
D is the number of vertices adjacent from v, and the indegree, denoted id(v), of v is the number of
vertices adjacent to v. The degree, denoted deg v, of v is defined by deg v = od(v) + id(v).

The outdegrees, indegrees, and degrees of the vertices of the digraph D of Figure 8.2 are given in Table
8.1

Vertex Outdegree Indegree Degree

u 1 1 2
v 2 2 4
w 0 2 2
x 2 0 2

Table 8.1
Section 8.3. An Introduction to Networks Page 72

Definition 8.2.4.
For a vertex v in a digraph D, we define the out-neighborhood of v by the set N + (v) = {u ∈ V (D) |
(v, u) ∈ E(D)}. The in-neighborhood of v is defined by the set N − (v) = {u ∈ V (D) | (u, v) ∈
E(D)}. Hence, od(v) = |N + (v)|, while id(v) = |N − (v)|.

The First Theorem of Digraph Theory is analogous to the First Theorem of Graph Theory.
Theorem 8.2.5.
If D is a digraph of size m with vertex set V , then
X X
od(v) = id(v) = m.
v∈V v∈V

Proof. When the outdegrees of the vertices are summed, each arc is counted exactly once, since every
arc is incident from one vertex. Similarly, when the indegrees are summed, each arc is counted just once
since every arch is incident to exactly one vertex.

Definition 8.2.6.
Let u and v be two vertices of a digraph D. A u-w walk in D is a finite alternating sequence

u = u0 , a1 , u1 , a2 , . . . , uk−1 , ak−1 , uk = v

of vertices and arcs that begins with the vertex u and ends with the vertex v and such that ai =
(ui−1 , ui ) for i = 1, 2, . . . , k. The number of arcs in the walk is called the length of the walk. The
concepts of trail, path, and circuits in digraphs are defined analogously to those in graphs, except that
in digraphs, we always proceed in the direction of the arcs. Note that cycles of length 2 are possible
in digraphs.

Definition 8.2.7 (Semiwalk).

A term that is unique to digraph theory is that of a semiwalk. Let u and v be two vertices of a digraph
D. A u-v semiwalk in D is a finite, alternating sequence

u = u0 , a1 , u1 , a2 , . . . , uk−1 , ak−1 , uk = v

of vertices and arcs that begins with the vertex u and ends with the vertex v and such that either
ai = (ui−1 , ui ) or ai = (ui , ui−1 ) for i = 1, 2, . . . , k. If ai = (ui−1 , ui ), then we call ai a forward arc,
otherwise, we call ai a backward arc. The number of arcs in the semiwalk is called the length of the
semiwalk. If the vertices uo , u1 , . . . , uk are distinct, then the u-v semiwalk is called a u-v semipath.

8.3 An Introduction to Networks

Before we attempt to solve the problem stated in Section 8.1, we make several fairly natural restrictions.
First, no pipe can carry more oil than its capacity allows and, secondly, all intermediate stations pump
out as much oil as they receive and oil cannot accumulate at these stations. We now formulate our
problem in more mathematical terms.
Section 8.3. An Introduction to Networks Page 73

Definition 8.3.1 (Network).

A network N is a digraph D with a nonnegative capacity c(e) on each arc e, called the capacity
function on N , and two distinguished vertices s and t called the source and sink, respectively. The
digraph D is called the underlying digraph of the network N .

Intuitively, the capacity c(x, y) of an arc (x, y) may be thought of as the maximum amount of some
material that can be transported from x to y per unit time. For example, the capacity of the arc (x, y)
may represent the number of seats available on a direct flight from city x to city y in some airline
system. On the other hand, this capacity might be the capacity of a pipeline from city x to city y
in an oil network. The problem in general, is to maximize the “flow” from the source s to the sink t
without exceeding the capacities of the arcs. fig:graph76 A network may be represented by drawing its
underlying digraph D and labelling each arc of D with its capacity. For example, Figure 8.1 shows a
network with c(u, v) = 5 and c(x, y) = 2.

Definition 8.3.2 (Flow).

Let N be a network with underlying digraph D, source s, sink t and capacity function c. A flow f in
N is an integer-valued function on E(D) that satisfies the
1. (capacity constraint): 0 ≤ f (e) ≤ c(e) for each arc e ∈ E(D), and the
2. (conservation constraint): f + (v) = f − (v) for every v ∈ V (D) − {s, t}
where f + (v) denotes the total flow on edges exiting v and f − (v) denotes the total flow on edges
entering v; that is,
X
f + (v) = f (v, w),
w∈N + (v)

and

f − (v) =
X
f (w, v).
w∈N − (v)

For a vertex v ∈ V (D), the net flow out of v is defined as f + (v) − f − (v), while the net flow into
v is defined as f − (v) − f + (v). The value f (N ) of a flow in N is the net flow

f (N ) = f + (s) − f − (s)

out of the source s. A maximum flow is a flow of maximum value.

A flow is a mapping that describes the movement (or flow) of material along the arcs of the network,
while the capacity is a mapping that describes the maximum amount that can move along the arcs. The
capacity constraint states that the flow in an arc can never exceed its capacity, and the flow conservation
states that all that flows into a vertex, other than the source s and the sink t, also flows out of that
vertex.
Example 8.3.3 (Flow).
The zero flow assigns flow 0 to each arc in the network. Figure 8.3 shows a flow f in a network N .
Associated with each arc, we write an ordered pair where the first number denotes the capacity of the
arc and the second number denotes the flow in the arc. For example, f (u, v) = 1 while c(u, v) = 5.
The value of a flow is f (N ) = f + (s) − f − (v) = 8 − 0 = 8.
Section 8.3. An Introduction to Networks Page 74

Figure 8.3

Before presenting our first result on networks, we introduce some notation. Let D = (V, E) be a
digraph, and let X, Y ⊆ V with X, Y ̸= ∅. We write
(X, Y ) = {(x, y) ∈ E | x ∈ X, y ∈ Y }
to denote the set of all arcs directed from some vertex in X to some vertex in Y . For example, in
Figure 8.3, if X = {u, v, x} and Y = {x, y, t}, then (X, Y ) = {(u, y), (v, t), (x, y)}. For a flow f and
a capacity function c in a network N , we define
X X
f (X, Y ) = f (e) and c(X, Y ) = c(e)
e∈(X,Y ) e∈(X,Y )

where f (X, Y ) = c(X, Y ) = 0 if (X, Y ) = ∅. For a subset X ⊆ V , we denote the compliment V \ X

of X by X.
Definition 8.3.4.
Let N be a network with underlying digraph D = (V, E), source s, sink t, capacity function c and flow
f . If S ⊆ V is such that s ∈ S and t ∈ S, we call the pair (S, S) a cut in N , and we call c(S, S) the
capacity of the cut. A minimum cut is a cut of minimum value. We call f (S, S) the flow from S
to S and we call f (S, S) the flow from S to S.

Example 8.3.5 (Cut).

Suppose f is the flow in the network of Figure 8.3 and that S = {s, v, y}. Then S = {u, x, t}
and the cut (S, S) = {(s, u), (s, x), (v, t), (y, t)}. Thus, c(S, S) = 20 and f (S, S) = 16. Further,
(S, S) = {(u, v), (u, y), (x, v), (x, y)}, and so f (S, S) = 8.

We are now in a position to present our first result on networks.

Theorem 8.3.6.
Let N be a network and f a flow in N . If f (S, S) is a cut of N , then

f (N ) = f (S, S) − f (S, S).

Section 8.3. An Introduction to Networks Page 75

Proof. By definition, f (N ) = f + (s) − f − (s). By the flow conservation constraint (2), we have
f + (v) = f − (v) for all v ∈ S − {v}. Hence we can write

(f + (v) − f − (v)).
X
f (N ) =
v∈S

Since S ∪ S = V (D) where D is the underlying digraph of N ,

X X
f (u, v) + f (u, v) = f (S, S) + f (S, S)
(u,v)∈(S,S) (u,v)∈(S,S)

while

X X
f (u, v) + f (u, v) = f (S, S) + f (S, S)
(u,v)∈(S,S) (u,v)∈(S,S)

Thus

f − (v) = f (S, S) − f (S, S)

X X
f (N ) = f + (v) −
v∈S v∈S

as required.

As an immediate consequence of Theorem 8.3.6, we have the following corollaries.

Corollary 8.3.7.
If f is a flow in a network N , then the value of the flow is the net flow into the sink, i.e.,

f (N ) = f − (t) − f + (s).

Proof. Let D be the underlying digraph of N and let S = V (D) − {t}. Since S = t,

f (w, t) = f − (t)
X
f (S, S) =
w∈N − (t)

while
X
f (S, S) = f (t, w) = f + (t).
w∈N + (t)

Thus, by Theorem 8.3.6 f (N ) = f (S, S) − f (S, S) = f − (t) − f + (t).

Corollary 8.3.8.
Let f be a flow in a network N and let (S, S) be a cut of N . Then

f (N ) ≤ c(S, S).

Proof. By Theorem 8.3.6, the value of the flow f (N ) equals the net flow out of S. Thus, f (N ) =
f (S, S) − f (S, S) ≤ f (S, S) since f (S, S) ≥ 0. However by the capacity constraint (1), f (S, S) ≤
c(S, S), hence f (N ) ≤ c(S, S).
Section 8.3. An Introduction to Networks Page 76

Corollary 8.3.9.
Let f be a flow in a network N and let (S, S) be a cut of N . If f (N ) = c(S, S), then f is a maximum
flow and (S, S) is a minimum cut.

Proof. Let f ∗ be a maximum flow in N , and let (X, X) be a minimum cut of N . By Corollary 8.3.8,
f ∗ (N ) ≤ c(X, X). However, f ∗ is a maximum flow, and so f (N ) ≤ f ∗ (N ), while (X, X) is a minimum
cut, and so c(X, X) ≤ c(S, S). Thus, c(S, S) = f (N ) ≤ f ∗ (N ) ≤ c(X, X) ≤ c(S, S). Thus we must
have equality throughout this inequality chain. In particular, f (N ) = f ∗ (N ) and c(X, X) = c(S, S).
Hence, f is a maximum flow and (S, S) is a minimum cut.

Example 8.3.10.
Consider the network N shown in Figure 8.4, where as before, the first number associated with
an arc a is its capacity c(a) and the second number is its flow f (a). The value of a flow is f (N ) =
f + (s)−f − (s) = 10. If S = {s, x}, then (S, S) is a cut of N and c(S, S) = c(s, u)+c(x, v)+c(x, y) =
4 + 4 + 2 = 10. Thus, by Corollary 8.3.9, f is a maximum flow and (S, S) is a minimum cut.

Figure 8.4

Learning Opportunities
8.1. Let N be the network shown in Figure 8.1, where each arc is labelled with its capacity function.
A function f is defined on the arcs as follows:
f (s, u) = 2 f (s, x) = 2 f (u, v) = 1 f (u, y) = 2
f (v, t) = 2 f (x, v) = 1 f (x, y) = 1 f (y, t) = 3
Is f a flow? Explain.
8.2. For the network shown below, associated with each arc is an ordered pair where the first number
denotes the capacity of the arch and the second number denotes the flow in the arc. Determine
the values of the flows a, b and c.
Section 8.4. The Max-Flow Min-Cut Theorem Page 77

8.3. Consider the network N shown below, where as before, the first number associated with an arc s
is its capacity c(a) and the second number is its flow f (a). Use Corollary 8.3.9 to show that the
given flow is a maximum flow and find the corresponding minimum cut.

8.4 The Max-Flow Min-Cut Theorem

It follows from Corollary 8.3.8 that total value of a flow in a network is never larger tan the smallest
capacity of a cut. Our aim in this subsection is to present the so-called max-flow min-cut theorem due
to Ford and Fulkerson (1956) which shows that the upper bound as always attained by the same flow.
The proof that we present is algorithmic in nature and is based on the idea of improving the current flow
along some s-t semipath that is not being “optimally” used. Once this is done, we repeat the process in
the network with its modified flow until we can find no such s-t semipath whose flow can be improved.
This technique has come to be known as tha augmenting path technique.
Section 8.4. The Max-Flow Min-Cut Theorem Page 78

Definition 8.4.1.
Let N be a network with source s, sink t, capacity function c and flow f . Let P be an s-v semipath.
If every forward arc e on P has excess capacity (meaning f (e) < c(e)) and every backward arc on P
has nonzero flow (meaning f (e) > 0), then we call P an f -unsaturated s-v path from s to v. If
v = t, then we call P and f -augmenting path (even though it may not actually be a path).

For each arc e of P , we define ϵ(e) to be c(e) − f (e) if e is a forward arc and f (e) is e is a backward
arc. We define the leeway of P by ϵ(P ) = min{ϵ(e)}, where the minimum is taken over all arcs e on
P.

Intuitively, if a forward arc e on P has excess capacity, then we increase the flow along e, while if a
backward arch e on P has nonzero flow, then we can “push back” the flow along the arc e.‘
Example 8.4.2.
If f is the flow given in Figure 8.3, P : s, (s, x), x, (x, v), v(u, v), u, (u, y), y, (y, t), t is an f -augmenting
path. Further, ϵ(s, x) = 1, ϵ(x, v) = 2, ϵ(u, v) = 1, ϵ(u, y) = 3 and ϵ(y, t) = 3. Thus, ϵ(P ) = 1.

We are now in a position to present the max-flow min-cut theorem due to Ford and Fulkerson.
Theorem 8.4.3 (Ford and Fulkerson).
In every network, the value of a maximum flow equals the capacity of a minimum cut.
Proof. Let N be a network with underlying digraph D, source s, sink t, and capacity function c. We
define a sequence f0 , f1 , . . . of flows in N of strictly increasing value, i.e., with f0 (N ) < f1 (N ) <
f2 (N ) < · · · , as follows. We start with the zero flow, and so f0 (e) = 0 for all arcs e of D and
f0 (N ) = 0. For each flow fi , i ≥ 0, we denote by Si the set of all vertices v such that there is an
fi -unsaturated s-v semipath from s to v.
Suppose t ∈ Si . Then there is an f -augmenting path P in N . Let fi+1 be the function obtained from
fi by increasing flow by ϵ(P ) along forward arcs of P and decreasing flow by ϵ(P ) along backward arcs
of P and leaving flows on all remaining arcs unchanged. By the definition of the leeway ϵ(P ), we have
0 ≤ fi+1 (e) ≤ c(e) for every arc e, and so the capacity constraint (1) holds. To verify the conservation
constraint (2), we need only to consider vertices of P since the flow along all arcs not on P is unchanged.
However the net flow out of each vertex v on P different from s and t remains 0 (irrespective of the
direction of the two arcs incident with v on P ). Hence, fi+1 is indeed a flow in N . Further, the net
flow out of the source s is ϵ(P ) larger in fi+1 than in fi and so fi+1 (N ) = fi (N ) + ϵ(P ). Thus,
fi+1 (N ) > fi (N ), as desired.
Since a flow is an integer-valued function on E(D), f (N ) + 1 ≤ fi+1 (N ) for all i. By Corollary 8.3.8,
the value of any flow in N is bounded above by the capacity of any cut in N , and so our sequence
f0 , f1 , . . . of flows in N will terminate with some flow fn . Hence in fn , t ∈
/ Sn . Let S = Sn . We
now consider the cut (S, S). Suppose (u, v) ∈ (S, S) and f (u, v) < c(u, v). Then by taking an fn -
unsaturated s-u semipath from s to u, and then proceeding to v along the arc (u, v), we produce an
fn -unsaturated semipath s-v from s to v, contradicting the fact that v ∈ S. Hence if (u, v) ∈ (S, S),
then f (u, v) = c(u, v). Thus, f (S, S) = c(S, S). Further, if (v, u) ∈ (S, S), then f (v, u) = 0, for
otherwise f (v, u) > 0 we could find an fn -unsaturated s-v semipath from s to v, a contradiction.
Section 8.5. The Max-Flow Min-Cut Algorithm Page 79

Hence f (S, S) = 0. Consequently, by Theorem 8.3.6,

fn (N ) = fn (S, S) − fn (S, S) = c(S, S).

Thus, by Corollary 8.3.9, fn is a maximum flow and (S, S) is a minimum cut.

8.5 The Max-Flow Min-Cut Algorithm

As remarked earlier, the proof of the max-flow min-cut theorem due to Ford and Fulkerson is essentially
algorithmic in nature since it searches for an augmenting path to increase the flow value. If it does not
find such a path, then the proof produces a minimum cut and maximum flow.
In this section, we present an algorithm due to Edmonds and Karp which gives a systematic method for
finding an f -augmenting path in a network N with flow f , if such a path exists. We begin the procedure
with a given flow f in N (perhaps the zero flow). As we attempt to find an f -augmenting path, we
label the vertices of N as we examine them. Initially, we label the source s, and then label every vertex
v for which we can find an f -unsaturated s-v semipath. The label assigned to v is an ordered pair .
If u is the vertex immediately preceding v on P , then the first component of the label is u+ or u−
depending on whether the arc preceding v is a forward arc (u, v) or a backward arc (v, u). The second
component of the label is a positive integer reflecting the potential change in f along P . When we
finally label the sink t, we have found an f -augmenting path. This path is then used to increase the
total flow in N , and the process is begun again. If at some point, we cannot find any vertex to label,
then no f -augmenting path exists and, as shown in the proof of Theorem 8.4.3, the present value of
the flow is maximum.
Algorithm 8.5.1 (Edmonds and Karp).
Given a network N with underlying digraph D = (V, E), source s, sink t, and capacity function c.
1. Assign values of an initial flow to the arcs of D.
2. Label s with (−, ∞) and add s to L, the list of labelled and unscanned vertices.
3. Select and remove the first element of L, say u, with label (x+ , ϵ(u)) or (x− , ϵ(u)). If L is
empty, then stop. Otherwise, continue
• To all vertices v that are unlabelled and such that (u, v) ∈ E and f (u, v) < c(u, v), assign
the label (u+ , ϵ(v)), where

ϵ(v) = min{ϵ(u), c(u, v) − f (u, v)}

and add v to the end of L.

• To all vertices v that are unlabelled and such that (v, u) ∈ E and f (u, v) > 0, assign the
label (u− , ϵ(v)), where

ϵ(v) = min{ϵ(u), f (v, u)}

and add v to the end of L.

4. If t has been labelled, go to Step 5; otherwise, go to Step 3.
Section 8.5. The Max-Flow Min-Cut Algorithm Page 80

5. The labels describe an f -augmenting path

s = u0 , a1 , u1 , a2 , . . . , un−1 , an−1 , un = t.

For i = 1, . . . , n, replace f (ai ) by f (ai ) + ϵ(t) if ai is a forward arc and by f (ai ) − ϵ(t) if ai is
backward arc.
6. Discard all labels, remove all vertices from L, and go to Step 2.

As shown in the proof of the max-flow min-cut theorem due to Ford and Fulkerson (Theorem 8.4.3),
Algorithm 8.5.1 terminates with a maximum flow f in N . Furthermore, if S is the set of labelled vertices
upon termination, then (S, S) is a minimum cut.
Example 8.5.2.
In this example, we shall use the Edmonds and Karp Algorithm to find a maximum flow and minimum
cut for the network shown in Figure 8.5. The labels on each arc a are the capacity c(a) of a and the
flow f (a) in a, respectively. We begin with the zero flow as shown in Figure 8.5

Figure 8.5
Section 8.5. The Max-Flow Min-Cut Algorithm Page 81

Initially, s is labelled (−, ∞), and L consists only of s. As the algorithm proceeds through Step 3
for the first time, we remove s from L. Since u is unlabelled, and (s, u) ∈ E satisfies f (s, u) <
c(s, u), we assign the label (s+ , 4) to the vertex u, and add u to the end of L. (Note that ϵ(u) =
min{ϵ(s), c(s, u) − f (s, u)} = min{∞, 4} = 4.) Furthermore, since x is unlabelled, and (s, x) ∈ E
satisfies f (s, x) < c(s, x), we assign the label (s+ , 5) to the vertex x, and add x to the end of L.
At this stage, L = {u, x}. Since t has not been labelled, we return to Step 3. We remove the first
element of L, namely u. We the assign the label (u+ , 4) to the vertex v, and add v to the end of
L. (Note that ϵ(v) = min{ϵ(u), c(u, v) − f (u, v)} = min{4, 5} = 4.). We then assign y the label
(u+ , 4), and add y to the end of L. At this stage, L = {x, v, y}. Since t has not been labelled, we
return to Step 3. We remove the first element of L, namely x. Since there are no unlabelled vertices
that can be labelled from x, we continue through Step 3 again (with L = {v, y}). We remove the first
element of L, namely v, and then assign the label (v + , 3) to the vertex t, and add t to the end of L.
(Note that ϵ(t) = min{ϵ(v), c(v, t) − f (v, t)} = min{4, 3} = 3.) We now reach Step 4 and proceed
to Step 5 to obtain the f -augmenting path P : s, (s, u), u, (u, v), v, (v, t), t. (See Figure 8.6)

Figure 8.6

We now increase by ϵ(t) = 3 along forward arcs of P and decrease flow decrease flow by ϵ(t) = 3
along backward arcs of P and leave flows on remaining arcs unchanged. The resulting flow is shown
in Figure 8.7.
Section 8.5. The Max-Flow Min-Cut Algorithm Page 82

Figure 8.7

Proceeding through Step 2 of the Edmonds-Karp algorithm, we assign to the vertices to labels shown
in Figure 8.7. Using the resulting f -augmenting path s, (s, u), u, (u, y), y, (y, t), t with leeway ϵ(t) = 1,
we increase the flow in each of the arcs if this path by ϵ(t) = 1. The resulting flow is shown in Figure
8.8.

Figure 8.8
Section 8.5. The Max-Flow Min-Cut Algorithm Page 83

Proceeding through Step 2 of the Edmonds-Karp algorithm, we assign to the vertices the labels shown
in Figure 8.8. Using the resulting f -augmenting path s, (s, x), x, (x, y), y, (y, t), t with leeway ϵ(t) = 2,
we increase the flow in each of the arcs if this path by ϵ(t) = 2. The resulting flow is shown in Figure
8.9.

Figure 8.9

Proceeding through Step 2 of the Edmonds-Karp algorithm, we assign to the vertices the labels shown
in Figure 8.9. Using the resulting f -augmenting path s, (s, x), x, (x, v), v, (u, v), u, (u, y), y, (y, t), t
with leeway ϵ(t) = 3, we increase the flow in each of the arcs if this path by ϵ(t) = 3 and decrease the
flow by ϵ(t) = 3 along backward arcs in this path. The resulting flow is shown in Figure 8.10.

Figure 8.10
Section 8.5. The Max-Flow Min-Cut Algorithm Page 84

Proceeding through Step 2 of the Edmonds-Karp algorithm, we are only able to label the source s
an no other vertex (including the sink t). Thus the given flow f is a maximum flow of value, and
the corresponding minimum cut is (S, S), where S = {s}. The value of the flow f is f (N ) =
f (S, S) − f (S, S) = 9, while c(S, S) = 9 .

Remark. When a vertex receives a label in the Edmonds-Karp algorithm, it is added to the bottom
of the “labelled but unscanned” list L. These vertices are scanned on a “first-labelled first scanned”
basis, which insures that a shortest f -augmenting path is selected. The importance of taking a shortest
f -augmenting path is illustrated by the network shown in Figure 8.11. If the f -augmenting path is taken
alternately along s, (s, x), x, (x, y), y, (y, t), t and s, (s, y), y, (x, y), x, (x, t), t, then we will need 2 × 106
steps before we obtain a maximum flow of 2 × 106 , whereas the Edmonds-Karp algorithm obtains a
maximum flow in two steps.

Figure 8.11
Section 8.5. The Max-Flow Min-Cut Algorithm Page 85

Learning Opportunities
8.4. For the networks shown below, associated with each arc is an ordered pair where the first number
denotes the capacity of the arc and the second arc denotes the flow in the arc. Starting with
the given flow, use the Edmonds-Karp algorithm to find a maximum flow and a minimum cut for
these networks.
8.4.1. .

8.4.1. .
References
[1] K. Appel and W. Haken. Every planar map is four colorable. Bulletin of the American mathematical
Society, 82(5):711–712, 1976.
[2] N. Biggs, E. K. Lloyd, and R. J. Wilson. Graph Theory, 1736-1936. Oxford University Press, 1986.
[3] B. Bollobás. Graph Theory: An Introductory Course. Springer Verlag, 1979.
[4] J. Bondy and U. S. R. Murty. Graph theory with applications. North-Holland New York, 1976.
[5] G. Chartrand. Introduction to graph theory. Tata McGraw-Hill Education, 2006.
[6] G. Chartrand, L. Lesniak, and P. Zhang. Graphs & digraphs, volume 39. CRC press, 2010.
[7] G. Chartrand and O. R. Oellermann. Applied and algorithmic graph theory. Mcgraw-Hill College,
1993.
[8] E. W. Dijkstra et al. A note on two problems in connexion with graphs. Numerische mathematik,
1(1):269–271, 1959.
[9] G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society,
3(1):69–81, 1952.
[10] L. Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum
Petropolitanae, pages 128–140, 1741.
[11] H. Fleischner, L. Beineke, and R. Wilson. Eulerian graphs, selected topics in graph theory 2.
Academic Press, London, pages 2–53, 1983.
[12] A. Gibbons. Algorithmic graph theory. Cambridge university press, 1985.
[13] R. J. Gould. Updating the hamiltonian problem—a survey. Journal of Graph Theory, 15(2):121–
157, 1991.
[14] R. L. Graham and P. Hell. On the history of the minimum spanning tree problem. Annals of the
History of Computing, 7(1):43–57, 1985.
[15] S. L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. i.
Journal of the Society for Industrial and Applied Mathematics, 10(3):496–506, 1962.
[16] V. Havel. A remark on the existence of finite graphs. Casopis Pest. Mat., 80:477–480, 1955.
[17] P. J. Heawood. Map color theorems. Quant. J. Math., 24:332–338, 1890.
[18] C. Hierholzer and C. Wiener. Über die möglichkeit, einen linienzug ohne wiederholung und ohne
unterbrechung zu umfahren. Mathematische Annalen, 6(1):30–32, 1873.
[19] A. Kempe. How to colour a map with four colours, 1880.
[20] A. B. Kempe. On the geographical problem of the four colours. American journal of mathematics,
2(3):193–200, 1879.
[21] J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem.
Proceedings of the American Mathematical society, 7(1):48–50, 1956.

86
REFERENCES Page 87

[22] C. Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathematicae,
15(1):271–283, 1930.
[23] L. Lesniak and O. R. Oellermann. An eulerian exposition. Journal of Graph Theory, 10(3):277–297,
1986.
[24] L. Lesniak-Foster. Some recent results in hamiltonian graphs. Journal of Graph Theory, 1(1):27–36,
1977.
[25] E. Lucas. Recreations mathematiques: 2e ed. A. Blanchard, 1960.
[26] D. B. West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, NJ,
1996.
[27] A. T. White. The proof of the heawood conjecture. Selected Topics in Graph Theory, LW Beineke
and RJ Wilson, Eds., Academic Press, London, pages 51–81, 1978.
[28] R. J. Wilson and J. J. Watkins. Graphs: an introductory approach: a first course in discrete
mathematics. John Wiley & Sons Inc, 1990.