C

H
A
P Introduction to graph
T
E theory
R

10
10.1 What is a graph?
The objects that we study in the branch of mathematics known as graph
theory are not graphs drawn with x and y axes. In this chapter, the word
‘graph’ refers to a structure consisting of points (called ‘vertices’), some
of which may be joined to other vertices by lines (called ‘edges’) to form a
network. Structures of this type abound in computing. The computers on
a site may be connected into a local area network, which in turn may be
linked to wider networks, including the Internet. The circuitry inside a
computer (which we represented schematically by digital circuit diagrams
in Chapter 8) provides another example of a graph or network structure.
At a more abstract level, we saw in Chapter 5 how a relation on a set can
be depicted using a diagram that takes the form of a graph.
There is a particular type of graph called a tree, which we will study in
Chapter 11. Trees are used in computing to represent the structure of
expressions; we saw an example of a logical expression tree in Chapter 4.
Trees can also be used to represent decision processes, in which we are
faced with two or more choices at each step of a procedure; the tree
diagrams in Chapter 9 were of this type.
In this chapter, we introduce graphs, study their basic properties, and
investigate some practical problems in which they can be applied. In
Chapter 11, we will study trees and investigate some of their applications
to computing.

10.2 Basic concepts in graph theory

Definition A graph consists of a non-empty set of points, called vertices (singular:

vertex), and a set of lines or curves, called edges, such that every edge is
attached at each end to a vertex.

An example of a graph is shown in Figure 10.1, with the edges and

vertices labelled.

174
 Introduction to graph theory

Figure 10.1

An edge is said to be incident to the vertices to which it is attached. For

example, the edge e1 is incident to the vertices v1 and v2 in the graph in
Figure 10.1.
Two vertices that are joined by an edge are said to be adjacent. In the
graph in Figure 10.1, v1 and v2 are adjacent, while v1 and v3 are not
adjacent.
A graph such as the one shown in Figure 10.1 could arise in many
situations of practical interest. For example, a graph could represent a
road system, in which the edges are the roads and the vertices are the
towns and road junctions. Alternatively, the vertices might represent
computer laboratories in a local area network (LAN), with the edges
representing the links in the network.
More abstract interpretations are also possible. For example, the
vertices could be sporting teams, with an edge joining two vertices if
those teams have played against each other during the current season.
Before we go any further, it is important that we clarify just what is and
what is not allowed in a graph.
Firstly, a graph does not have to be in one piece. For example, Figure
10.2 shows a perfectly legitimate graph.

Figure 10.2

If a graph is in one piece, it is said to be connected. For some applications

we will only be interested in connected graphs, but we do not include
being connected in the definition of a graph.
The second point to notice is that there is no restriction on the
numbers of edges and vertices a graph may have (except that it must have
at least one vertex). It is permissible for a graph to have no edges; such
graphs are called null graphs. It is also permissible for the number of
vertices or edges of a graph to be infinite; however, we will assume from
now on that all the graphs we will be dealing with have a finite number of
vertices and edges.
A graph may have loops (an edge from one vertex to the same vertex),
as in Figure 10.3.

Figure 10.3

A graph may also have parallel edges (two or more edges linking the
same pair of vertices), as in Figure 10.4.

175
Discrete mathematics for computing

Figure 10.4

In some applications of graphs, loops and parallel edges make sense.

For example, if a graph represents a road system, there may be two towns
with two or more roads joining them, and there may be a road that leaves
a town and returns to it. There are other applications in which loops and
multiple edges do not arise – a graph representing a local area network,
for example.
A graph is said to be simple if it has no loops and no parallel edges.
Notice that we have not assigned a direction to the edges of a graph. In
some applications it would make sense for each edge to have a direction.
For example, in the technique known as critical path analysis, the vertices
of a graph represent tasks to be carried out, and an edge from one vertex
to another indicates that one task has to be completed before the other
can begin. This situation can be depicted using directed edges (edges with
arrows drawn on them), and a graph with directed edges is called a
directed graph. The graphical depiction of a relation, which we met in
Chapter 5, is an example of a directed graph. The graphs we study in this
chapter are all undirected graphs.
We now come to a subtle but important point about the way graphs are
drawn. When we draw a graph, all that matters is which vertices are
adjacent (joined by an edge) and which are not; the precise location of the
vertices and the lengths and shapes of the edges are irrelevant. It follows
that there will be many different ways of drawing the same graph, some of
which may look very different from others.
For example, the two diagrams in Figure 10.5 represent the same graph.

Figure 10.5

In order to make the relationship between these two graphs clearer,

corresponding vertices have been labelled with the same letter. The
graphs are essentially the same (they are isomorphic, to use the technical
term), because the first graph can be ‘rearranged’ to look like the second.
In this rearranging process, we are free to move the vertices around, and
stretch and bend the edges, as much as we like. We may even draw two
edges so that they cross at a point where there is no vertex. The only
restrictions are that we may not create new edges or vertices, delete any
edges or vertices, or reattach edges to different vertices.
Imagine that the graph in Figure 10.5(a) is made of buttons (the
vertices) joined by pieces of elastic string (the edges). We may move the
buttons and string around however we like, as long as we don’t break any

176
 Introduction to graph theory

of the strings. In particular, we can rotate the first graph anticlockwise so

that it looks like the one shown in Figure 10.6.

Figure 10.6

If we flip the edge AB over into the triangle BCD, and bend DEF up a bit,
we now obtain the graph shown in Figure 10.5(b) without breaking or
rejoining edges or creating new ones.
We will have more to say in Section 10.4 about graphs being
isomorphic.
A useful way to get a feel for graphs is to look for all the simple graphs
with a small number of vertices. We do this now, by finding all the simple
graphs with up to three vertices.
If a simple graph has one vertex, then it must have no edges, because a
simple graph is not permitted to have loops. Therefore there is only one
simple graph with one vertex; it is shown in Figure 10.7(a).

Figure 10.7(a)
If a simple graph has two vertices, then either there is an edge joining
the vertices or there is not. The two possibilities are shown in Figure
10.7(b).

Figure 10.7(b)
With three vertices, things start to get more complicated. It doesn’t
matter whether we draw the vertices in a straight line or in a triangle,
because we may move them around however we like and the graph will
still be essentially the same graph. Suppose we arrange the vertices in a
triangle. We find that there are four different simple graphs with three
vertices; see Figure 10.7(c).

Figure 10.7(c)

These four graphs are all different (they must be, because they have
different numbers of edges), and any simple graph with three vertices is
isomorphic to one of these four. (For example, the graph with three
vertices ‘in line’ can be obtained by ‘straightening out’ the third graph in
Figure 10.7(c).)
You are asked in Exercise 2 to draw all 11 simple graphs with four
vertices. This can be tricky, but it is a useful exercise for becoming

177
Discrete mathematics for computing

familiar with graphs. (If you think you have found more than 11, you will
need to look carefully to see whether you have included graphs that
appear to be different but are actually isomorphic.)
There are 34 simple graphs with five vertices. The number of simple
graphs increases rapidly as the number of vertices increases. There is a
known method for calculating the number of simple graphs with n
vertices, but as it is very complicated we will not give it here.
We now return to graphs in general (not necessarily simple graphs). In
order to proceed further, we need the following definitions.

Definitions The degree of a vertex v in a graph is the number of edges incident to v,

with a loop counting 2 towards the degree of the vertex to which it is
incident. The degree of v is denoted by deg(v).
A vertex with degree 0 is said to be isolated.

For example, the vertices of the graph shown in Figure 10.8 have the
degrees indicated.

Figure 10.8

There is a simple relationship between the degrees of the vertices of any

graph and the number of edges of the graph. It is given by the following
theorem.

Theorem In any graph, the sum of the degrees of the vertices equals twice the
number of edges.

If V and E denote respectively the set of vertices and the set of edges of a
graph, then the theorem can be written in symbols as follows:

 deg(v) = 2 | E |
v ŒV

The theorem follows immediately from the fact that if we add the degrees
of all the vertices, every edge will be counted twice, since each edge is
incident to two vertices.

Example 10.2.1 Verify for the graph shown in Figure 10.8 that the sum of the degrees of
the vertices equals twice the number of edges.

178
 Introduction to graph theory

Solution  deg(v) = deg(a) + deg(b) + deg(c) + deg(d) + deg(e)

v ŒV
= 2 + 3 + 2 + 4 +1
= 12
=2¥6
= 2| E|

A more surprising result is the following one, which is widely known by

the curious name of the ‘Handshaking lemma’. (A lemma is a result that
is used primarily to prove other theorems, rather than being of interest in
its own right.)

Handshaking In any graph, the number of vertices with odd degree is even.
lemma

For example, the graph in Example 10.2.1 (Figure 10.8) has two vertices
with odd degree (b and e), and two is an even number. In general, the
Handshaking lemma asserts that if we count the number of vertices with
odd degree in a graph, we must obtain an even number as the answer.
The name of the lemma arises from an amusing way of interpreting this
result. Imagine a room full of people, some of whom shake hands with
some of the other people in the room. The situation can be represented as
a graph, in which the vertices represent the people in the room, and two
vertices are adjacent if the corresponding people shake hands. Even if we
do not know how many people there are, or how many times and with
whom each person shakes hands, we can nevertheless make one assertion
with confidence: the number of people who shake hands an odd number of
times is even.
The Handshaking lemma can be proved in the following way. We begin
with the result of the previous theorem:

 deg(v) = 2 | E |
v ŒV

The left-hand side of this equation can be split into two terms: the sum
taken over the set Vodd of vertices with odd degree, and the sum taken
over the set Veven of vertices with even degree:

 deg(v) +  deg(v) = 2 | E |
v ŒVodd v ŒVeven

179
Discrete mathematics for computing

The second term on the left-hand side is a sum of even numbers, and is
therefore equal to an even number. The right-hand side is clearly an even
number. Thus the first term on the left-hand side is the difference
between two even numbers, and so it must be an even number. Now, this
term is a sum of odd numbers; but an even result can be obtained by
adding odd numbers together only if there is an even number of them.
Hence the number of vertices with odd degree is even. This completes the
proof.

Definition A simple graph is complete if each vertex of the graph is adjacent to every
other vertex.

There is essentially only one complete graph with any given number of
vertices. The complete graph with five vertices is shown in Figure 10.9.

Figure 10.9

We can obtain a formula for the number of edges in the complete graph
with n vertices, using the following reasoning. Each edge in the graph
corresponds to a selection of two distinct vertices from the set of n vertices,
without taking order into account. This selection can be carried out in (n2 )
ways. Hence the number of edges is (n2 ), which equals [n(n – 1)]/2.

Definition The complement G of a simple graph G is the graph with the same vertices
as G, such that any two vertices are adjacent in G if and only if they are
not adjacent in G.

For example, if the vertices of G represent sporting teams, and an edge

indicates that two teams have already played a match against each other
this season, then G shows the matches that are still to be played if each
team plays once against every other team during the season.

10.3 The matrix representation of a graph

While a pen-and-paper drawing of a graph is convenient for working with
small graphs by hand, it is not suitable if a graph is to be handled on a
computer. For this purpose, other ways of representing graphs have been
developed. The most commonly used representation is known as an
adjacency matrix.

180
 Introduction to graph theory

If G is a graph with n vertices, labelled v1, v2, ..., vn, then the adjacency
matrix of G is an n × n matrix whose entries are given by the following
rule:
The entry in the ith row and the jth column is the number of edges
from vi to vj.
In particular, if G is a simple graph, then the entry in the ith row and the
jth column of the adjacency matrix is 1 if vi and vj are adjacent, and 0 if
they are not. In addition, the elements on the principal diagonal of the
matrix (from the top left to the bottom right corner) are all 0, because
simple graphs do not have loops.

Example 10.3.1 Construct the adjacency matrix for the graph shown in Figure 10.10,
assuming the vertices are given in the order a, b, c, d, e.

Figure 10.10

Solution a b c d e
a !0 1 0 1 1$
b #1 0 1 1 0&
# &
c #0 1 0 1 1&
d #1 1 1 0 0&
# &
e "
#1 0 1 0 0&
%

Example 10.3.2 Draw the graph with the following adjacency matrix:
a b c d
a !0 0 0 1$
b #0 0 2 0&
# &
c #0 2 0 1&
d #1 0 1 1&
" %

Solution The graph is shown in Figure 10.11.

181
Discrete mathematics for computing

Figure 10.11

The entry in the ith row and the jth column of an adjacency matrix must
be the same as the entry in the jth row and the ith column, because both
entries represent the number of edges between vi and vj. We express this
fact by saying that the adjacency matrix of any graph is symmetric. (Recall
that we are dealing only with undirected graphs; the adjacency matrix of a
directed graph need not be symmetric.) It follows that it is sufficient to
give the entries on and below the principal diagonal of the matrix; there is
no need to write down the entire matrix. This representation is called the
lower triangular matrix representation of the graph. For example, the
lower triangular matrix representation of the graph in Example 10.3.2 is:
a b c d
a !0 $
b #0 0 &
# &
c #0 2 0 &
d #1 0 1 1&
" %

Notice that the adjacency matrix of a graph depends on the order in

which the vertices are labelled. A graph can have many adjacency
matrices, corresponding to the different ways in which the vertices can be
arranged. Using the theory introduced in Chapter 9, we know that there
are n! different ways in which n items can be arranged, so a graph with n
vertices could have up to n! different adjacency matrices.

10.4 Isomorphism of graphs

We want to look more closely now at the problem of how to tell whether
graphs are isomorphic. We have said that two graphs are isomorphic if
one of them can be ‘moved around’ until it looks like the other (subject to
certain rules, such as not breaking edges). This is a bit too vague to be
really satisfactory, so we will now look for a more precise definition. In
order to avoid some rather messy details that arise in the general case, we
will deal only with simple graphs in this section.
The key to defining ‘isomorphic’ precisely is the idea of matching up
the corresponding vertices in the two graphs. We did this in Figure 10.5,
where we labelled corresponding vertices with the same letter. If two
graphs are isomorphic, then we can associate with each vertex of one
graph a corresponding vertex in the other graph.

182
 Introduction to graph theory

Suppose we have two simple graphs G and H. Let V(G) and V(H)
denote the vertex sets of G and H respectively. If G and H are isomorphic,
then we should be able to show this by associating with each element of
V(G) the corresponding element of V(H).
We have seen something like this before. Recall that in Chapter 6, we
encountered the idea of associating each element of a set with an element
of another set. In a word, what we have here is a function, with domain
V(G) and codomain V(H):
f : V (G) ' V (H )
There are some conditions that the function f must satisfy. We cannot
associate two different vertices of G with the same vertex of H, nor can
there be any vertices of H that are not associated with vertices of G. This
means that f must be one-to-one and onto. There is a further requirement
– if two vertices are adjacent in G, then the corresponding vertices must
be adjacent in H, while if two vertices are not adjacent in G, then the
corresponding vertices must not be adjacent in H. A function that
satisfies all of these conditions is called an isomorphism from G to H.

Definitions Let G and H be two simple graphs, with vertex sets V(G) and V(H)
respectively. An isomorphism from G to H is a function f : V (G) ' V (H )
with the following properties:
f is one-to-one and onto.
▼ ▼

For any two vertices u and v of G, if u and v are adjacent in G, then f(u)
and f(v) are adjacent in H, and if u and v are not adjacent in G, then
f(u) and f(v) are not adjacent in H.
If there exists an isomorphism from G to H, then G and H are isomorphic.

Example 10.4.1 Find an isomorphism between the two graphs shown in Figure 10.12.

Figure 10.12

Solution One isomorphism is:

f : V (G) Æ V (H ), f (a) = e, f (b) = b, f (c) = d , f (d ) = a, f (e) = c

183
Discrete mathematics for computing

It is a straightforward exercise to check that this function satisfies the

conditions of an isomorphism.

How can two graphs G and H be shown not to be isomorphic, if this is

the case? It would be impractical to test all the functions from V(G) to
V(H) to show that none of them are isomorphisms. A better way of
showing that two graphs are not isomorphic is to find a graph-theoretic
property that one graph has but the other does not. A ‘graph-theoretic’
property is a property that is retained if the graph is rearranged according
to the rules we stated in Section 10.2.
For example, rearranging a graph in this way will not change the
number of edges or the number of vertices. It follows that two graphs
with different numbers of edges or vertices cannot possibly be
isomorphic.
If two graphs have the same number of edges and the same number of
vertices, then the problem is more difficult. In such cases, it is often useful
to look at the degrees of the vertices. For example, if one graph has two
vertices with degree 3, and the other has only one, then the graphs are not
isomorphic. Sometimes even this test fails, and it is necessary to look for
another property that distinguishes the two graphs.

Example 10.4.2 Show that the pairs of graphs shown in Figures 10.13(a) and 10.13(b) are
not isomorphic.

Figure 10.13

Solution (a) Both graphs in Figure 10.13(a) have four vertices and three edges.
However, the second graph has a vertex with degree 3, while the first
does not, so the graphs are not isomorphic. (Note that it would be
incorrect to say that they are not isomorphic because vertex a has
degree 2 in the first graph and degree 1 in the second. An
isomorphism from one graph to another does not necessarily
associate vertices that happen to be labelled with the same letter.)
(b) Both graphs in Figure 10.13(b) have six vertices and seven edges.
Also, both graphs have four vertices with degree 2 and two vertices

184
 Introduction to graph theory

with degree 3. However, the first graph has a sequence def of three
vertices with degree 2, with d adjacent to e and e adjacent to f,
whereas there is no such sequence of three vertices with degree 2 in
the second graph. Therefore the graphs are not isomorphic.

In the spirit of the earlier chapters, you might imagine that we would
provide an algorithm for testing whether two graphs are isomorphic.
Unfortunately, even the best known graph isomorphism algorithms are
inefficient when applied to moderately large graphs. It is not known
whether it is possible to construct a graph isomorphism algorithm that
works ‘efficiently’ (in a sense that will be made precise in Chapter 13).
The idea that two mathematical objects (whether they are graphs or
something else) can be fundamentally the same, even if they ‘look different’,
is very powerful. We met a related idea in Chapter 8, where we saw that
propositional logic and sets obey the ‘same’ laws of Boolean algebra. In this
more general sense, isomorphism is one of the most important concepts in
mathematics, because it allows us to ignore the superficial aspects of a
problem and study its underlying mathematical structure.

10.5 Paths and circuits

If you look at a fairly detailed map of eastern Europe, you will see that
there is a small territory on the coast of the Baltic Sea between Poland and
Lithuania, called the Kaliningrad Region. The region belongs politically to
the Russian Federation (although it is physically separate), and its main
town is the Russian naval base of Kaliningrad. Until the Second World
War, Kaliningrad was known by the name of Königsberg, and was in the
part of Germany known as East Prussia.
The town of Königsberg provides the historical setting for the
Königsberg bridge problem. This problem is one of the most famous in the
history of mathematics, and its solution in about 1735 by the famous
Swiss mathematician Leonhard Euler1 (1707–1783) is generally regarded
as marking the beginning of graph theory as a subject.
Two streams, called the Old Pregel and the New Pregel, join in the town
to form the river Pregel (now called the Pregolya), but with the added
complication that there is an island in the stream where they meet. In the
early 18th century, seven bridges joined the four areas of land thus
formed (the north and south banks, the island, and the land between the
two streams), as shown in Figure 10.14.
The problem that is now known as the Königsberg bridge problem must
have first occurred to someone who was taking a stroll around the town. It
goes as follows: is it possible for someone to take a walk around Königsberg
in such a way as to cross each of the seven bridges exactly once?
A good way to get a feel for the problem is to try to find such a path.
For example, if we start on the north bank, we could cross bridge a to the

1 Pronounced ‘oiler’.

185
Discrete mathematics for computing

Figure 10.14

island, then e to the south bank. After returning to the island via f, we
could then cross d, followed by c and b. But now we’re in trouble; bridge g
remains uncrossed, but we have no way of reaching it without crossing
one of the bridges a second time.
At this point, you are encouraged to explore the problem yourself
before reading further. We will obtain the answer later in this section. For
now, we just make the observation that the Königsberg bridge problem
can be treated as a problem in graph theory.
In order to see this, notice that in order to explore the problem, it is not
necessary to know the precise geography of the pieces of land, the shape
of the river, or the lengths of the bridges. In fact, we could collapse each
of the four pieces of land down to a single point, without changing the
problem in any essential way. All that matters is which pieces of land are
joined by bridges, and by how many. If we represent the pieces of land by
vertices and the bridges by edges joining those vertices, we obtain the
graph shown in Figure 10.15.

Figure 10.15

In the terminology of graph theory, the Königsberg bridge problem now

asks whether it is possible to trace along the edges of the graph in Figure
10.15 in a continuous sequence (which we will be calling a path) in a way
that ensures that each edge is traversed exactly once.
If the recreational needs of the citizens of 18th century Königsberg
seem irrelevant to today’s problems, imagine instead that the edges
represent the streets on a mail delivery run. It is necessary to travel along
every street in order to deliver the mail, but in the interests of efficiency
we would prefer not to travel along any street a second time.
Before we can investigate the Königsberg bridge problem, we need to
establish some more terminology.2

2 Unfortunately, the terminology in graph theory is not fully standardised, and

some terms, in particular ‘path’ and ‘circuit’ (defined here) and ‘cycle’ (defined
in Chapter 11), are defined differently elsewhere. You should keep this in mind
when referring to other textbooks.

186
 Introduction to graph theory

Definitions A path of length n in a graph is a sequence of vertices and edges of the

form:
v0, e1, v1, e2, v2, ..., en, vn
where ei is an edge joining vi – 1 and vi, for all i ( {1, 2, !, n}.
(In other words, e1 is an edge joining v0 and v1, e2 is an edge joining v1
and v2, and so on.)
A path for which v0 = vn is called a circuit.

A path can be thought of as a sequence of vertices and edges that can be

traced without lifting your pen off the paper. A path may include repeated
edges or repeated vertices. The length of a path is the number of edges in
the path. A circuit is a path that starts and ends at the same vertex.
A careful reading of the definition reveals that any vertex by itself is
both a path and a circuit of length 0.
For example, consider the graph shown in Figure 10.16.

Figure 10.16

In this graph, A, a, B, g, D, d, E is a path of length 3, and C, c, D, g, B, b, C,

c, D is a path of length 4. E, d, D, g, B, b, C, c, D, d, E is a circuit of length 5.
When we write down a path, it is sufficient to list the starting vertex
followed by the sequence of edges; for example, the first of the paths listed
above can be written Aagd.
Paths can also be defined recursively, in the following way:
1. A sequence consisting of a single vertex is a path.
2. If a sequence p is a path whose last term is the vertex u, and e is an
edge from u to v, then the sequence p, e, v is a path.
We can now give a more precise definition of what it means for a graph to
be connected.

Definition A graph G is connected if, for any pair of vertices u and v of G, there is a
path from u to v.

187
Discrete mathematics for computing

The graph shown in Figure 10.17 is not connected, because there is no

path from u to v.

Figure 10.17

We can define a relation R on the set of vertices of a graph by the rule:

u R v if there is a path from u to v. Then R is an equivalence relation; you
are asked to show this in Exercise 14. The equivalence classes for this
relation are called the components of the graph; they are simply the
connected ‘pieces’ of the graph. A connected graph is thus a graph that
has only one component.
In passing, we note that if there is a path from a vertex u to a vertex v in
a graph, then in particular there is a path from u to v that contains no
repeated vertices or edges. It follows that in a connected graph, each pair
of vertices is connected by at least one path that doesn’t contain repeated
vertices or edges.
The path we are looking for in the Königsberg bridge problem has an
additional property – it must include every edge of the graph exactly
once. More generally, we can ask the following question: Given any
connected graph, can we find a path that includes every edge exactly
once? (If a graph is not connected, there could still be a path that includes
every edge exactly once, but only in the not particularly interesting case
where all the components except one consist of just one vertex. For this
reason, we will restrict our attention to connected graphs.)

Definitions Let G be a connected graph. An Eulerian path is a path that includes every
edge of G exactly once. An Eulerian circuit is an Eulerian path for which
the first and the last vertices coincide (that is, an Eulerian circuit is an
Eulerian path that is also a circuit).
A connected graph that has an Eulerian circuit is called Eulerian. A
connected graph that has an Eulerian path but no Eulerian circuit is
called semi-Eulerian.

Note that an Eulerian circuit may have repeated vertices.

Figure 10.18 shows the graph for the Königsberg bridge problem again,
this time with the vertices labelled. The problem can now be restated as
follows: does this graph have an Eulerian path (that is, is it either an
Eulerian or a semi-Eulerian graph)?
Suppose we focus our attention on vertex A for a moment. If there is an
Eulerian path in the graph, then at some stage it must enter A along one

188
 Introduction to graph theory

Figure 10.18

of the three edges incident to A, and leave via another one. That leaves
just one unused edge incident to A. It would be impossible to pass
through A a second time without repeating an edge that has already been
used, so the remaining edge can be used only if the path either starts or
ends at A. This rules out any possibility of an Eulerian circuit, but there
could still be an Eulerian path.
Now consider vertex C. Like vertex A, this vertex also has degree 3, so
the reasoning that we have just applied to A applies to C too. We deduce
that any Eulerian path would have to start or end at C.
So far, it appears that there could be an Eulerian path, provided that it
starts at A and ends at C (or vice versa). But now, if we apply the same
reasoning to vertex D (which also has degree 3), we see that any Eulerian
path would have to start or end at D. We conclude that no Eulerian path
exists, and therefore that it is impossible to find a route around
Königsberg that crosses every bridge exactly once.
The solution to the Königsberg bridge problem suggests a more general
result about Eulerian paths and circuits in connected graphs. The key to the
reasoning we used was to look at the degrees of the vertices. If a vertex has
even degree, say 2n, then an Eulerian path will use all the edges incident to
the vertex by entering and leaving the vertex n times. If a vertex has odd
degree, on the other hand, then there will be one edge left over which can be
used only if the path starts or ends there. Therefore, any connected graph
with more than two vertices with odd degree cannot have an Eulerian path.
This conclusion forms part of the following theorem.

Theorem Let G be a connected graph.

1. If all the vertices of G have even degree, then G is Eulerian.
2. If exactly two vertices of G have odd degree, then G is semi-Eulerian,
and every Eulerian path in G must start at one of the vertices with
odd degree and end at the other.
3. If G has more than two vertices with odd degree, then G is neither
Eulerian nor semi-Eulerian.

Example 10.5.1 Classify each of the graphs in Figure 10.19 as Eulerian, semi-Eulerian, or
neither, and find an Eulerian path or an Eulerian circuit if one exists.

189
Discrete mathematics for computing

Figure 10.19

Solution (a) All the vertices have even degree, so the graph is Eulerian. An
Eulerian circuit is Aabcdefgihj.
(b) Two vertices, B and C, have odd degree, so it is possible to find an
Eulerian path from B to C. One such path is Baedcbgfh.
(c) There are four vertices with odd degree, so this graph does not have
an Eulerian path.

We have not yet proved Parts 1 and 2 of the theorem. We will establish
Part 1 by devising an algorithm for finding an Eulerian circuit in a
connected graph in which all the vertices have even degree. The fact that
the algorithm always works amounts to a proof of Part 1. Part 2 will
follow as a corollary.
Consider again the graph in part (a) of Example 10.5.1. Suppose we
decide to begin our Eulerian circuit at vertex F. (Because an Eulerian
circuit is a circuit, we should be able to start at any vertex.) If we follow
the circuit Ffge, we then find that we cannot go any further without
repeating edges, yet we have not used all the edges in the graph.
The key to the algorithm for finding an Eulerian circuit is that we can
extend the circuit we already have, by inserting extra edges and vertices at
any vertex where there are unused edges. A is such a vertex. Starting at A,
and following unused edges until we can go no further, we produce the
circuit Aahj. This new circuit can be inserted into the original one to
produce the extended circuit Ffahjge.

190
 Introduction to graph theory

The circuit we have obtained so far still doesn’t include all of the edges
of the graph, so we repeat the extension process. There is a vertex, B, on
the circuit, where there are still some unused edges. Starting at B, and
using only edges that have not previously been used, we obtain the circuit
Bbcdi. Inserting the new circuit into the existing one, we obtain
Ffabcdihjge. This circuit uses all of the edges, so it is an Eulerian circuit.
Why does this procedure work? To answer this question, we need to explain
why, when a path is being created for insertion into a circuit that has already
been obtained, we can be sure that the new path will always be a circuit.
The explanation runs as follows. Since every vertex of the graph has
even degree, the new path can always leave any vertex it has entered, with
the exception only of the vertex where it started. This guarantees that
each new path will always be a circuit, and so can be inserted into the
circuit previously obtained.
We will now write this procedure as an algorithm in a form suited to hand
computation. (In a computer-oriented version of the algorithm, the graph
would be input as an adjacency matrix, and some of the steps would need
to be specified in greater detail.)
1. Input an Eulerian graph G, with vertex set V(G) = {v1, v2, ..., vm} and
edge set E(G) = {e1, e2, ..., en}.3
2. circuit ) v1 ; unused _ edges ) E(G)
{circuit is a circuit (expressed as a sequence of vertices and edges) that
is built up piece by piece until it forms an Eulerian circuit. Initially it
consists of a single vertex. The set unused_edges keeps track of the
edges that have not yet been used.}
{Step 3 is the main part of the algorithm. Each time the While-do loop
is executed, a new circuit is formed and inserted into circuit in place of
the vertex insertion_point.}
3. While unused _ edges * + do
3.1. insertion_ point ) first vertex in circuit with unused edges incident
to it
3.2. v ) insertion_ point; new _ circuit ) v
{Each time the Repeat-until loop in Step 3.3 is executed, an edge and a
vertex are appended to new_circuit.}
3.3. Repeat
3.3.1. e ) first element of unused_edges incident to v
3.3.2. v ) vertex adjacent to v via edge e
3.3.3. new _ circuit ) new _ circuit , e, v
3.3.4. unused _ edges ) unused _ edges , {e}
until no element of unused_edges is incident to v
3.4. circuit ) (circuit before insertion_point), new_circuit, (circuit after
insertion_point)
4. Output circuit

3 There is a notational ambiguity here; we have been using braces in algorithms

to denote comments, but braces are also used to write sets in enumerated or
predicate form. The problem is not serious, as the meaning will always be clear
from the context.

191
 Discrete mathematics for computing

Example 10.5.2 Trace the algorithm using the graph shown in Figure 10.20 as input, with
vertex set {A, B, C, D} and edge set {p, q, r, s, t, u}.

Figure 10.20

Solution A full trace would be rather tedious here, so we will take a short-cut and
treat the four steps within Step 3.3 as a single step (see Table 10.1).

Table 10.1
Step circuit insertion_ e v new_ unused_ Output
point circuit edges
2 A – – – – {p, q, r, s, t, u} –
3 A – – – – {p, q, r, s, t, u} –
3.1 A A – – – {p, q, r, s, t, u} –
3.2 A A – A A {p, q, r, s, t, u} –
3.3.1–4 A A p B ApB {q, r, s, t, u} –
3.3.1–4 A A q C ApBqC {r, s, t, u} –
3.3.1–4 A A s D ApBqCsD {r, t, u} –
3.3.1–4 A A r A ApBqCsDrA {t, u} –
3.4 ApBqCsDrA A r A ApBqCsDrA {t, u} –
3 ApBqCsDrA A r A ApBqCsDrA {t, u} –
3.1 ApBqCsDrA B r A ApBqCsDrA {t, u} –
3.2 ApBqCsDrA B r B B {t, u} –
3.3.1–4 ApBqCsDrA B t D BtD {u} –
3.3.1–4 ApBqCsDrA B u B BtDuB + –
3.4 ApBtDuBqCs B u B BtDuB + –
DrA
3 ApBtDuBqCs B u B BtDuB + –
DrA
4 ApBtDuBqCs B u B BtDuB + ApBtDuBqCsDrA
DrA

192
 Introduction to graph theory

If a graph is semi-Eulerian, we can find an Eulerian path in the following

way:
1. Insert a new edge between the two vertices with odd degree. (The
resulting graph is Eulerian, because all of its vertices have even
degree.)
2. Let the vertex set and the edge set of the Eulerian graph be {v1, v2, ..., vm}
and {e1, e2, ..., en} respectively, where the new edge e1 is incident to v1
and v2. Apply the algorithm to obtain an Eulerian circuit.
3. Remove v1, e1 from the beginning of the Eulerian circuit. What
remains is an Eulerian path joining the two vertices with odd degree.
Now that we have obtained a satisfactory solution to the problem of
determining whether a graph has a path or a circuit that includes every
edge exactly once, we turn to what appears to be a similar problem – to
determine whether a graph has a path or a circuit that includes every
vertex exactly once.

Definitions Let G be a connected graph. A Hamiltonian4 path is a path that includes

every vertex of G exactly once, except only that the first and the last
vertices may coincide. A Hamiltonian circuit is a Hamiltonian path for
which the first and the last vertices coincide (that is, a Hamiltonian circuit
is a Hamiltonian path that is also a circuit).
A connected graph that has a Hamiltonian circuit is called Hamiltonian.

Note that a Hamiltonian path or a Hamiltonian circuit need not use all of
the edges of the graph.
For example, consider the two graphs shown in Figure 10.21.

Figure 10.21

4 Hamiltonian paths and circuits are named after the Irish mathematician Sir
William Hamilton (1805–1865). In 1859, Hamilton produced a puzzle
consisting of a dodecahedron (a regular solid with 12 faces) on which each
vertex was labelled with the name of a city. The problem was to find a way of
travelling along the edges of the dodecahedron, visiting each city exactly once.

193
Discrete mathematics for computing

The first graph, Figure 10.21(a), is Hamiltonian, because it has a

Hamiltonian circuit, Acefda. The second graph, Figure 10.21(b), has a
Hamiltonian path, Babef; however, the graph is not Hamiltonian, because
any circuit passing through all of the vertices would have to pass through
vertex C twice.
The problem of determining whether a graph is Hamiltonian appears at
first sight to be similar to the problem of determining whether a graph is
Eulerian, and it might be imagined that it could be solved in a similar
way. In fact, no efficient algorithm for determining whether a graph is
Hamiltonian has so far been produced, and it may well turn out to be the
case that no such algorithm can exist. This problem is one of a certain
class of problems, all of which can be shown to be equivalent, in the sense
that if an efficient algorithm could be found for solving just one of the
problems, then there would be an efficient algorithm for solving all of
them. The problem of the ‘Travelling sales representative’, which we will
examine in Chapter 11, is another such problem.

EXERCISES
1 Explain how each of the following situations could be modelled
as a graph. In each case, state what meaning (if any) can be
attached to loops and parallel edges, and whether it would make
sense to use directed edges.
(a) An electronic circuit.
(b) A chemical molecule.
(c) A group of people and the relationship of friendship
between two people.
(d) The management structure of a company.
(e) The modules of a computer program, and the relationship of
one module calling another.
2 Draw all 11 simple graphs with four vertices.
3 Verify for each of the graphs shown in Figure 10.22 (opposite)
that the sum of the degrees of the vertices equals twice the
number of edges.
4 Draw a graph whose vertices have the following degrees, or
explain why no such graph exists:
(a) 2, 3, 3, 4, 5 (b) 2, 3, 3, 3, 3
5 Obtain an alternative proof that the complete graph with n
vertices has [n(n – 1)]/2 edges, using the result that the sum of
the degrees of the vertices equals twice the number of edges.
6 If a simple graph G has n vertices and m edges, how many edges
does G have?

194
 Introduction to graph theory

Figure 10.22

7 Construct an adjacency matrix for each of the graphs shown in

Figure 10.23.

Figure 10.23
8 Draw the graphs with the following adjacency matrices:
!0 0 1 2 1$
!0 1 1 0$ #0
#1 1 1 1 0&
0 0 1& # &
(a) # & (b) # 1 1 0 0 1&
#1 0 0 1& #2
#0 1 0 0 1&
" 1 1 0&
% # &
#1
" 0 1 1 2&
%

9 Write down the lower triangular matrix representation of each of

the graphs in Exercise 7.
10 How can the degrees of the vertices of a graph be determined
directly from the adjacency matrix, without drawing the graph?

195
Discrete mathematics for computing

(Answer the question first for the simpler case where the graph
has no loops.)
11 Show that the pairs of graphs in Figure 10.24 are isomorphic, by
finding an isomorphism from one graph to the other.

Figure 10.24

12 Show that the pairs of graphs in Figure 10.25 are not isomorphic.

Figure 10.25

196
 Introduction to graph theory

13 (a) Draw the complement G of graph G (Figure 10.26), and

show that G and G are isomorphic.

Figure 10.26

(b) Could a simple graph with six vertices be isomorphic to its

complement? (Use the result of Exercise 6.)
14 Let G be a graph, and let R be the relation on the set of vertices of
G defined by the rule: u R v if there is a path from u to v. Prove
that R is an equivalence relation.
15 Classify the graphs in Figure 10.27 as Eulerian, semi-Eulerian, or
neither, and find an Eulerian path or an Eulerian circuit if one
exists.

Figure 10.27
(a) and (b)
(continued overleaf)

197
Discrete mathematics for computing

Figure 10.27
(c) and (d)

16 The theorem for determining whether a graph is Eulerian, semi-

Eulerian or neither makes no mention of the case of a graph with
exactly one vertex with odd degree. Why not?
17 For each of the graphs in Exercise 15, find a Hamiltonian circuit
or explain why no Hamiltonian circuit exists.
18 Prove that if G is any simple graph, then at least one of G and G is
a connected graph. (Assume G is not connected, and prove that
there is a path between any two vertices u and v of G by
considering two cases: u and v are in the same component of G,
and u and v are in different components.)
19 Prove that if G is a simple graph with at least two vertices, then it
is always possible to find two vertices of G with the same degree.
(Begin by listing all the possible values that the degree of a vertex
can take in a simple graph with n vertices.)
20. (Assumes a knowledge of matrix multiplication.) Let G be a
graph with vertex set V = {v1, v2, ..., vn}.
(a) Explain why the number of paths of length 2 from a vertex vi
to a vertex vj is

198
 Introduction to graph theory

n
. (number of edges from vi to v k )
k-1
/ (number of edges from v k to v j )

(b) Let M denote the adjacency matrix of G. Using the result of

(a), give an interpretation of M2 in terms of the graph, where
M2 denotes the matrix product of M with itself.
(c) Calculate M2 for the graph in Exercise 7(a), and verify your
answer to (b) for that graph.

199