LECTURE NOTES

ON

CSC 411 - GRAPH THEORY AND APPLICATIONS

Prepared by Prof. A. A. Eludire

AIM

The course is aimed at developing the fundamental mathematical skills of students that are
instrumental for effective understanding of advanced engineering subjects. The topics introduced
will serve as the tools for specialized studies in many engineering fields, significantly in field
theory, computer technology and communication engineering.

OBJECTIVES

• Have knowledge of the basic concepts of graph

• Have a knowledge classes of graphs and its algorithm
• Be exposed to constrained and unconstrained optimization techniques
• to make students familiar with the most fundamental graph theory topics and results; and
to teach the students the techniques of proofs and analysis

COURSE OUTLINE

This course discusses fundamental concepts of graph theory and its applications in computer, social,
and natural sciences. The topics include graphs as models; representation of graphs; trees; universal
trees; distances; matchings’ connectivity; flows in networks; colourings; Hamiltonian cycles; and
planarity. All concepts, methods, and applications will be presented through a sequence of exercises
and problems.

MODULE I BASICS OF GRAPH THEORY

Graphs - Basic definitions: graphs; vertex degrees; paths; cycles; isomorphism; Subgraphs -
Operations on Graphs Connectivity - Spanning trees - Rooted trees - Matrix representation of
graphs.

MODULE II CLASSES OF GRAPHS

Eulerian graphs and Hamiltonian graphs - Standard theorems - Planar graphs - Euler's formula. Five
colour theorem - Colouring of graphs - Chromatic number (vertex and edge) properties and
examples - Directed graphs.

MODULE III GRAPH ALGORITHM

Computer Representation of graphs - Basic graph algorithms - Minimal spanning tree algorithm -
Kruskal and Prim's algorithm. Shortest path algorithms – Travelling Salesman Problem

MODULE I

BASICS OF GRAPH THEORY

I.1. Module Objective

This module presents a general introduction to graph theory. It explains the concepts of graph theory
and associated terminologies. It also introduces the basic definitions of graphs and explains
components of graphs such as vertex, edges, degrees, paths, connectivity and cycles. Related
2
terminologies as isomorphism, subgraphs, spanning trees are presented. The module closes with a
presentation on the available operations on graphs and matrix representation of graphs.

I.2. Lecture Note

Defining a Graph

Informally, a graph is a bunch of dots, some of which are connected by lines. Here is an example
of a graph:

Figure I.1. A Graph

This definition is not precise enough for formalised mathematical discussion. Formally, a graph is
a pair of sets (V,E), where:
• V is a nonempty set whose elements are called vertices (or nodes).
• E is a collection of two-element subsets of V called edges.
The vertices correspond to the dots in the picture, and the edges correspond to the lines. Thus, the
dots-and-lines diagram above is a pictorial representation of the graph (V,E) where:
V = {A,B,C,D,E, F, G,H, I}
E = {{A,B} , {A,C} , {B,D} , {C,D} , {C,E} , {E, F} , {E,G} , {H, I}} .

Conceptually, a graph is formed by vertices and edges connecting the vertices. Formally, a graph
is a pair of sets (V,E), where V is the set of vertices and E is the set of edges, formed by pairs of
vertices. E is a multiset, in other words, its elements can occur more than once so that every element
has a multiplicity. Often, we label the vertices with letters (for example: a, b, c, . . . or v1, v2, . . . )
or numbers 1, 2, . . . Throughout this lecture material, we will label the elements of V in this way.

Graph Concepts, Definitions and Terminologies

A nuisance in first learning graph theory is that there are so many definitions that correspond to
intuitive ideas, but can take a while to absorb. Some ideas have multiple names. For example,
graphs are sometimes called networks, vertices are sometimes called nodes, and edges are
sometimes called arcs. Even worse, no one can agree on the exact meanings of terms. For example,
in our definition, every graph must have at least one vertex, however, graphs with no vertices are
also permitted. There are many different variations of the following graph concepts and
terminologies but for the purpose of our study we will adopt the definitions given here and further.
We shall examine the following graph terminologies:
1. The two vertices u and v are end vertices of the edge (u, v).
2. Edges that have the same end vertices are parallel.
3. An edge of the form (v, v) is a loop.
4. A graph is simple if it has no parallel edges or loops.
5. A graph with no edges (i.e. E is empty) is empty.
6. A graph with no vertices (i.e. V and E are empty) is a null graph.
3
 7. A graph with only one vertex is trivial.
8. Edges are adjacent if they share a common end vertex.
9. Two vertices u and v are adjacent if they are connected by an edge, in other words, (u, v) is
an edge.
10. The degree of the vertex v, written as d(v), is the number of edges with v as an end vertex.
By convention, we count a loop twice and parallel edges contribute separately.
11. A pendant vertex is a vertex whose degree is 1.
12. An edge that has a pendant vertex as an end vertex is a pendant edge.
13. An isolated vertex is a vertex whose degree is 0.
Example.

Figure I.2
For the graph in Fig.I.2 the follow can be identified:
• v4 and v5 are end vertices of e5.
• e4 and e5 are parallel.
• e3 is a loop.
• The graph is not simple.
• e1 and e2 are adjacent.
• v1 and v2 are adjacent.
• The degree of v1 is 1 so it is a pendant vertex.
• e1 is a pendant edge.
• The degree of v5 is 5.
• The degree of v4 is 2.
• The degree of v3 is 0 so it is an isolated vertex.

Further in our discussions, we will label graphs with letters, for example: G = (V, E). The minimum
degree of the vertices in a graph G is denoted δ(G) (= 0 if there is an isolated vertex in G). Similarly,
we write (G) as the maximum degree of vertices in G.

Complete Graph
A simple graph that contains every possible edge between all the vertices is called a complete graph.
A complete graph with n vertices is denoted as Kn. The first four complete graphs are given as
examples:

4
Figure I.3. Complete graphs

Subgraph
The graph G1 = (V1,E1) is a subgraph of G2 = (V2,E2) if
1. V1 V2 and
2. Every edge of G1 is also an edge of G2.
For example, given the graph shown in Figure I.4, then the graphs in Figure I.5 are subgraphs of
the graph in figure I.4.

Figure I.4: Graph G

Figure I.5: Subgraphs G1 of graph G

Walks in the Graph

A walk in the graph G = (V,E) is a finite sequence of the form vi0 , ej1 , vi1, ej2, . . . , ejk , vik, which
consists of alternating vertices and edges of G. The walk starts at a vertex. Vertices vit−1 and vit are
end vertices of ejt (t = 1, . . . , k). vi0 is the initial vertex and vik is the terminal vertex. k is the length
of the walk. A zero length walk is just a single vertex vi0. It is allowed to visit a vertex or go through
an edge more than once. A walk is open if vi0 ≠ vik . Otherwise it is closed.

5
Figure I.6: Graph G

In the graph shown in Figure I.6, the walk v2, e7, v5, e8, v1, e8, v5, e6, v4, e5, v4, e5, v4 is open. On the
other hand, the walk v4, e5, v4, e3, v3, e2, v2, e7, v5, e6, v4 is closed.

Trails in a graph
A walk is a trail if any edge is traversed at most once. Then, the number of times that the vertex
pair u, v can appear as consecutive vertices in a trail is at most the number of parallel edges
connecting u and v. For example in Figure I.6, the walk in the graph v1, e8, v5, e9, v1, e1, v2, e7, v5,
e6, v4, e5, v4, e4, v4 is a trail.

Paths
A trail is a path if any vertex is visited at most once except possibly the initial and terminal vertices
when they are the same. The walk v2, e7, v5, e6, v4, e3, v3 is a path

Circuits
A closed path is a circuit. For simplicity, we will assume in the future that a circuit is not empty,
i.e. its length ≥ 1. We identify the paths and circuits with the subgraphs induced by their edges. The
walk v2, e7, v5, e6, v4, e3, v3, e2, v2 is a circuit. A graph is circuitless if it does not have any circuit
in it. A graph is circuitless exactly when there are no loops and there is at most one path between
any two given vertices.

Connectivity of a graph
A graph is connected if all the vertices are connected to each other. The walk starting at u and
ending at v is called an u–v walk. u and v are connected if there is a u–v walk in the graph (then
there is also a u–v path!). If u and v are connected and v and w are connected, then u and w are also
connected, i.e. if there is a u–v walk and a v–w walk, then there is also a u–w walk. A trivial graph
is connected by convention.

Figure I.7: Unconnected graph

6
Components of a graph

A subgraph G1 which is not a null graph of the graph G is a component of G if

1. G1 is connected and
2. Either G1 is trivial (one single isolated vertex of G) or G1 is not trivial and G1 is the subgraph
induced by those edges of G that have one end vertex in G1.
Different components of the same graph do not have any common vertices because If the graph G
has a vertex v that is connected to a vertex of the component G1 of G, then v is also a vertex of G1.

Figure I.8: Graph G

Figure I.9: Components of G are G1, G2, G3 and G4

Every isolated vertex forms its own component. A connected graph has only one component,
namely, itself.

Rank of a graph
A graph G with n vertices, m edges and k components has the rank ρ(G) = n − k.

Nullity of a graph
The nullity of the graph G with n vertices, m edges and k components is μ(G) = m − n + k. We see
that ρ(G) ≥ 0 and ρ(G) + μ(G) = m. In addition, μ(G) ≥ 0 because (G) ≤ m.
7
Graph Operations
A number of operations can be carried out with graphs. This includes the complement operation
and binary operations such as union, intersection and ring sum or symmetric difference.

Complement of a simple graph

The complement of the simple graph G = (V,E) is the simple graph G = (V,E), where the edges in
E are exactly the edges not in G.

Figure I.10: Graph G and its complement G‾

The complement of the complete graph Kn is the empty graph with n vertices. Obviously, G = G.
If the graphs G = (V, E) and G′ = (V, E′) are simple and V ⊆ V, then the difference graph is G − G
= (V, E), where E contains those edges from G that are not in G.

Below are some binary operations between two simple graphs G1 = (V1, E1) and G2 = (V2, E2):

Figure I.11: Graphs G1 and G2

• The union is G1 ∪ G2 = (V1 ∪ V2,E1 ∪ E2) (simple graph).

8
Figure I.12: Union operation on graph G1 and G2

• The intersection is G1 ∩ G2 = (V1 ∩ V2, E1 ∩ E2) (simple graph).

Figure I.13: Intersection operation on graph G1 and G2

• The ring sum G1⊕G2 is the subgraph of G1∪G2 induced by the edge set E1⊕E2 (simple graph).
The set operation ⊕ is the symmetric difference, i.e. E1 ⊕ E2 = (E1 − E2) ∪ (E2 − E1).
Since the ring sum is a subgraph induced by an edge set, there are no isolated vertices.

Figure I.14: Ring sum operation on graph G1 and G2

All three operations are commutative and associative.

Operations on non-simple graph

The operations ∪, ∩ and ⊕ can also be defined for more general graphs other than simple graphs.
In this case, we have to ”keep track” of the multiplicity of the edges:
∪ : The multiplicity of an edge in G1 ∪ G2 is the larger of its multiplicities in G1 and G2.
∩ : The multiplicity of an edge in G1 ∩ G2 is the smaller of its multiplicities in G1 and G2.

9
 ⊕ : The multiplicity of an edge in G1 ⊕ G2 is |m1 − m2|, where m1 is its multiplicity in
G1 and m2 is its multiplicity in G2.
(We assume zero multiplicity for the absence of an edge.) In addition, we can generalize the
difference operation for all kinds of graphs if we take account of the multiplicity. The multiplicity
of the edge e in the difference G − G′ is

(also known as the proper difference), where m1 and m2

are
the multiplicities of edges in G1 and G2, respectively.

Weighted (Labelled) Graphs

By a labelling of the vertices of the graph G = (V,E), we mean a mapping α : V → A, where A is
called the label set. Similarly, a labelling of the edges is a mapping β: E → B, where B is the label
set. Often, these labels are numbers. Then, we call them weights of vertices and edges. In a weighted
graph, the weight of a path is the sum of the weights of the edges traversed.
The labelling of the vertices (respectively edges) is injective if distinct vertices (respectively edges)
have distinct labels. An injective labelling is bijective if there are as many labels in A (respectively
in B) as the number of vertices (respectively edges). A weighted graph is a graph, in which each
edge has a weight (some real number). The weight of a graph is the sum of the weights of all edges.
Example:

Graph Tree 1 (w)=74 Tree 2 (w)=71 Tree 3 (w)=72

Figure I.15: Graphs and associated weights

Isomorphism of graphs
Two graphs G and H are isomorphic, denoted by G ∼=H, if there exists a bijection a: VG → VH
such that uv ∈ EG ⇐⇒ a(u)a(v) ∈ EH for all u, v ∈ G. Hence G and H are isomorphic if the vertices
of H are renamings of those of G. Two isomorphic graphs enjoy the same graph theoretical
properties, and they are often identified. In particular, all isomorphic graphs have the same plane
figures (excepting the identities of the vertices). This is shown in the figures, where we tend to
replace the vertices by small circles, and talk of ‘the graph’ although there are, in fact, infinitely
many such graphs.
The following graphs are isomorphic. Indeed, the required isomorphism is given by:

v1 → 1, v2 → 3, v3 → 4, v4
→ 2, v5 → 5.

Figure I.16: Graph

Isomorphism
10
A graph has usually many different adjacency matrices, one for each ordering of its set VG of
vertices. The following result is obvious from the definitions. Two graphs G and H are isomorphic
if and only if they have a common adjacency matrix. Moreover, two isomorphic graphs have exactly
the same set of adjacency matrices.

Trees and Forests

A forest is a circuitless graph. A tree is a connected forest. A subforest is a subgraph of a forest. A
connected subgraph of a tree is a subtree. Generally speaking, a subforest (respectively subtree) of
a graph is its subgraph, which is also a forest (respectively tree).

Figure I.17: Four trees in a forest

Spanning Trees
A subgraph T of a undirected graph G = (V, E) is a spanning tree of G if it is a tree and contains
every vertex of G. Every connected graph has a spanning tree.
Example:

Graph G Spanning tree 1 Spanning tree 2 Spanning tree 3

Figure I.18: Spanning trees of graph G

Minimum Spanning Trees

A minimum spanning tree in an undirected connected weighted graph is a spanning tree of
minimum weight (among all spanning trees).
Example

11
Graph G Tree 1 (w)=74 Tree 2 (w)=71 Tree 3 (w)=72

Minimum spanning trees

Figure I.19: Minimum spanning trees of graph G with their associated weights

The minimum spanning tree of a graph may not be unique. However, if the weights of all the edges
are pairwise distinct, it is indeed unique. The minimum spanning tree (MST) problem is stated as:
Given a connected weighted undirected graph G, design an algorithm that outputs a minimum
spanning tree of G.

Directed Graphs
In some problems the relation between the objects is not symmetric. For example, answering
questions like can we make the streets of a small town one-way, and still be able to drive from one
house to another or exit the town requires graphs with directions, where the edges are oriented from
one vertex to another. These types of graphs are called directed graphs or diagraphs.

A digraph (or a directed graph) D = (VD, ED) consists of the vertices VD and (directed) edges
ED ⊆ VD × VD (without loops vv). We still write uv for (u, v), but note that now uv <> vu. For each
pair e = uv define the inverse of e as e−1 = vu (= (v, u)). Note that e ∈ D does not imply e−1 ∈ D.

Figure I.20: Directed graph (diagraph)

A digraph is a pair (V,E), where V is the vertex set and E is the set of vertex pairs as in ”usual”
graphs. The difference is that now the elements of E are ordered pairs: the arc from vertex u to
vertex v is written as (u, v) and the other pair (v, u) is the opposite direction arc. We also have to
keep track of the multiplicity of the arc (direction of a loop is irrelevant). For a digraph following
notions and results for terminologies applies:
1. Vertex u is the initial vertex and vertex v is the terminal vertex of the arc (u, v). We also say
that the arc is incident out of u and incident into v.
2. The out-degree of the vertex v is the number of arcs out of it (denoted d+(v)) and the
indegree of v is the number of arcs going into it (denoted d−(v)).
3. In the directed walk (trail, path or circuit), vi0 , ej1, vi1 , ej2, . . . , ejk, vik viℓ is the initial
vertex and viℓ−1 is the terminal vertex of the arc ejℓ . .
4. When we treat the graph (V,E) as a usual undirected graph, it is the underlying undirected
graph of the digraph G = (V,E), denoted Gu.
12
 5. Digraph G is connected if Gu is connected. The components of G are the directed subgraphs
of G that correspond to the components of Gu. The vertices of G are connected if they are
connected in Gu. Other notions for undirected graphs can be used for digraphs as well by
dealing with the underlying undirected graph.
6. Vertices u and v are strongly connected if there is a directed u–v path and also a directed
v–u path in G.
7. Digraph G is strongly connected if every pair of vertices is strongly connected. By
convention, the trivial graph is strongly connected.
8. A strongly connected component H of the digraph G is a directed subgraph of G (not a null
graph) such that H is strongly connected, but if we add any vertices or arcs to it, then it is
not strongly connected anymore. Every vertex of the digraph G belongs to one strongly
connected component of G. However, an arc does not necessarily belong to any strongly
connected component of G.

Figure I.21: Diagraph with strongly connected components

For the digraph G the strongly connected components are ({v1}, ), ({v2, v3, v4}, {e3, e4, e5}), ({v5},
) and ({v6}, ).The condensed graph Gc of the digraph G is obtained by contracting all the arcs in
every strongly connected component.

Directed Trees
A directed graph is quasi-strongly connected if one of the following conditions holds for every pair
of vertices u and v:
(i) u = v or
(ii) there is a directed u–v path in the digraph or
(iii) there is a directed v–u path in the digraph or
(iv) there is a vertex w so that there is a directed w–u path and a directed w–v path.

The digraph G is a tree if Gu is a tree. It is a directed tree if Gu is a tree and G is quasistrongly

connected, i.e. it has a root. A leaf of a directed tree is a vertex whose out-degree is zero.

13
Figure I.22: Directed tree with six leaves

For the digraph G with n > 1 vertices, the following are equivalent:
(i) G is a directed tree.
(ii) G is a tree with a vertex from which there is exactly one directed path to every other vertex
of G.
(iii) G is quasi-strongly connected but G − e is not quasi-strongly connected for any arc e in G.
(iv) G is quasi-strongly connected and every vertex of G has an in-degree of 1 except one vertex
whose in-degree is zero.
(v) There are no circuits in G (i.e. not in Gu) and every vertex of G has an in-degree of 1 except
one vertex whose in-degree is zero.
(vi) G is quasi-strongly connected and there are no circuits in G (i.e. not in Gu).

I.3. Assessment

Q1. Consider a simple connected graph G with n vertices and n edges (n>2). Then which of the
following statements are TRUE?
a. G has at least one cycle
b. G has no cycles
c. The graph obtained by removing any edge from G is not connected.
d. G has at least one cycle and the graph obtained by removing any edge from G is not
connected.

Q2. The number of distinct simple graphs with up to three nodes is…........
a. 9
b. 7
c. 10
d. 15

Q3. Consider the graph G where V(G)={A,B,C,D} and E(G)=[{A,B},{B,C},{C,D}]. The degree
of each vertices A,B,C,D respectively in G are…..
a. 1,2,3,2
b. 1,3,2,2

14
 c. 1,1,1,1
d. 1,2,2,3

Q3. Maximum number of edges in a n-node undirected graph without self loops is….......
a. \frac{n(n+2)}{2}
b. n-1
c. n^2
d. \frac{n(n-1)}{2}

Q4. Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |ij|=8
or |i-j|=12. The number of connected components in G is…......
a. 8
b. 12
c. 25
d. 4

Q5. A graph in which all nodes are of equal degree is known as…....
a. complete graph
b. multi graph
c. non regular graph
d. regular graph

Q6. Let G = (V, E) be a graph. Define:

i. a walk ii. a trail iii. a cycle, iv. a circuit v.
an Eulerian circuit.

I. 4. References

1. BANG-JENSEN, J. & GUTIN, G.: Digraphs: Theory, Algorithms and Applications. Springer–
Verlag (2002)
2. BOLLOBÁS, B.: Modern Graph Theory. Springer–Verlag (2002)
3. DIESTEL, R.: Graph Theory. Springer–Verlag (2005)
4. DOLAN, A. & ALDOUS, J.: Networks and Algorithms. An Introductory Approach. Wiley (1999)
5. GIBBONS, A.: Algorithmic Graph Theory. Cambridge University Press (1987)

15
 MODULE II

CLASSES OF GRAPHS

II.1. Module Objective

The objectives of this module are to:

• Examine Standard theorems with regards to planar graphs
• Investigate the five colour theorem, colouring of graphs and properties of chromatic number
(vertex and edge) with examples
• Understand how directed and undirected graphs are represented in computers

II.2. Lecture Note

Planar Graphs and Graph Colouring

Planar Graphs
A graph is a planar graph if and only if it has a pictorial representation in a plane which is a plane
graph. This pictorial representation of a planar graph G as a plane graph is called a planar
representation of G.
Let G denote the plane graph in Figure II.1. Graph G, in Figure II.1, divides the plane into different
regions R1 and R2, called the faces of G.

Figure II.1. Planar Graphs

A graph is said to be planar if it can be drawn in the plane in such a way that no two edges intersect
each other. Drawing a graph in the plane without edge crossing is called embedding the graph in
the plane (or planar embedding or planar representation).
Given a planar representation of a graph G, a face (also called a region) is a maximal section of the
plane in which any two points can be joint by a curve that does not intersect any part of G. When
we trace around the boundary of a face in G, we encounter a sequence of vertices and edges, finally
returning to our final position. Let v1, e1, v2, e2, . . . , vd, ed, v1 be the sequence obtained by tracing
around a face, then d is the degree of the face. Some edges may be encountered twice because both
sides of them are on the same face. A tree is an extreme example of this: each edge is encountered
twice. The following result is known as Euler’s Formula.

Theorem: If G is a connected planar graph with n vertices, m edges and f faces, then n − m + f = 2.
Proof. We prove by induction on m. If m = 0, then G = K1, a graph with 1 vertex and 1 face. The
formula is true in this case. Assume it is true for all planar graphs with fewer than m edges and
suppose G has m edges.
16
Case 1: G is a tree. Then m = n − 1 and obviously f = 1. Thus n − m + f = 2, and the result holds.
Case 2: G is not a tree. Let C be a cycle in G, and e an edge in C. Consider the graph G−e. Compared
to G this graph has the same number of vertices, one edge fewer, and one face fewer (since
removing e coalesces two faces in G into one in G−e). By the induction hypothesis, in G − e we
have n − (m − 1) + (f − 1) = 2. Therefore, in G we have n − m + f = 2, which completes the proof.

Graph Colouring
Graph colouring is one of the most important concepts in graph theory and is used in many real
time applications in computer science. Various colouring methods are available and can be used on
requirement basis. The proper colouring of a graph is the colouring of the vertices and edges with
minimal number of colours such that no two vertices should have the same colour. The minimum
number of colours is called as the chromatic number and the graph is called properly coloured
graph. An example of a graph colouring problem could be stated as follows: Given a graph G,
assign one of k colours to each node such that adjacent nodes have different colours. In general, a
graph G is k-colourable if each vertex can be assigned one of k colours so that adjacent vertices
get different colours. The minimum value of k for which a colouring exists is the chromatic
number Х(G) of G.

Figure II.2: Graph colouring

Edge colourings
Colourings of edges and vertices of a graph G are useful, when one is interested in classifying
relations between objects. There are two sides of colourings. In the general case, a graph G with a
colouring a is given, and we study the properties of this pair Ga = (G, a). This is the situation, e.g.,
in transportation networks with bus and train links, where the colour (buss, train) of an edge tells
the nature of a link.
In the chromatic theory, G is first given and then we search for a colouring that the edge satisfies
required properties. One of the important properties of colourings is ‘properness’. In a proper
colouring adjacent edges or vertices are coloured differently.

Edge chromatic number

A k-edge colouring a : EG → [1, k] of a graph G is an assignment of k colours to its edges. We
write Ga to indicate that G has the edge colouring a. A vertex v ∈ G and a colour i ∈ [1, k] are
incident with each other, if a(vu) = i for some vu ∈ G. If v ∈ G is not incident with a colour i, then
i is available for v.
The colouring a is proper, if no two adjacent edges obtain the same colour: a(e1) 6=a(e2) for
adjacent e1 and e2. The edge chromatic number c′(G) of G is defined as c′(G) = min{k | there
exists a proper k-edge colouring of G} .
A k-edge colouring a can be thought of as a partition {E1, E2, . . . , Ek} of EG, where Ei = {e | a(e)
= i}. Note that it is possible that Ei = Æ for some i. We adopt a simplified notation Ga[i1, i2, . . . ,
it] = G[Ei1 ∪ Ei2 ∪ · · · ∪ Eit ] for the subgraph of G consisting of those edges that have a colour
i1, i2, . . . , or it. That is, the edges having other colours are removed.

17
Each colour set Ei in a proper k-edge colouring is a matching. Moreover, for each graph G, D(G)
≤ c′(G) ≤ #G.

Vertex colourings
The vertices of a graph G can also be classified using colourings. These colourings tell that certain
vertices have a common property (or that they are similar in some respect), if they share the same
colour. In this chapter, we shall concentrate on proper vertex colourings, where adjacent vertices
get different colours.

The chromatic number

A k-colouring (or a k-vertex colouring) of a graph G is a mapping a: VG → [1, k]. The colouring
a is proper, if adjacent vertices obtain a different colour:
for all uv G, we have a(u) 6= a(v). A colour i [1, k] is said to be available for a vertex v, if no
neighbour of v is coloured by i.
A graph G is k-colourable, if there is a proper k-colouring for G. The (vertex) chromatic number
c(G) of G is defines as c(G) = min{k | there exists a proper k-colouring of G} .
If c(G) = k, then G is k-chromatic.
Each proper vertex colouring a : VG → [1, k] provides a partition {V1,V2, . . . ,Vk} of the vertex
set VG, where Vi = {v | a(v) = i}.
The graph shown below, which is often called a wheel (of order 7), is 3-chromatic.

Figure II.3: A 3-chromatic colourable graph

By the definitions, a graph G is 2-colourable if and only if it is bipartite. Again, the ‘names’ of the
colours are immaterial:
Lemma Let a be a proper k-colouring of G, and let p be any permutation of the colours. Then the
colouring b = pa is a proper k-colouring of G.
Proof. Indeed, if a: VG → [1, k] is proper, and if p: [1, k] → [1, k] is a bijection, then uv G implies
that a(u) 6= a(v), and hence also that pa(u) 6= pa(v). It follows that pa is a proper colouring.
A graph is triangle-free, if it has no subgraphs isomorphic to K3. We show that there are
trianglefree graphs with arbitrarily large chromatic numbers.
The following construction is due to GRÖTZEL: Let G be any triangle-free graph with VG = {v1,
v2, . . . , vn}. Let Gt be a new graph obtained by adding n + 1 new vertices v and u1, u2, . . . , un
such that Gt has all the edges of G plus the edges uiv and uix for all x N(vi) and for all i [1, n].

Matrix Representation of Graphs

The adjacency matrix of the graph G = (V,E) is an n × n matrix D = (dij), where n is the number of
vertices in G, V = {v1, . . . , vn} and dij = number of edges between vi and vj .
In particular, dij = 0 if (vi, vj) is not an edge in G. The matrix D is symmetric, i.e. DT = D.

18
Computer Representation

Plane figures catch graphs for our eyes, but if a problem on graphs is to be programmed, then these
figures are, to say the least, unsuitable. Integer matrices are ideal for computers, since every
respectable programming language has array structures for these, and computers are good in
crunching numbers.
Let VG = {v1, . . . , vn} be ordered. The adjacency matrix of G is the n × n-matrix M with entries
Mij = 1 or Mij = 0 according to whether vivj G or vivj / G. For instance, the graph in figure II.4a
has an adjacency matrix in figure II.4b. Notice that the adjacency matrix is always symmetric (with
respect to its diagonal consisting of zeros).

(a) graph (b) adjacency matrix

Figure II.4: Undirected graph with its adjacency matrix

Adjacency Matrix of Directed Graph

The adjacency matrix of a directed graph G is D = (dij), where dij = number of arcs that come out
of vertex vi and go into vertex vj .

Figure II.5: Directed graph with its adjacency matrix

Incidence Matrix of a Undirected Graph

The all-vertex incidence matrix of a non-empty and loopless graph G = (V,E) is an n×m matrix A
= (aij), where n is the number of vertices in G, m is the number of edges in G and

19
Incidence Matrix of a Directed Graph
The all-vertex incidence matrix of a non-empty and loopless directed graph G is A = (aij), where

II.3. Assessment

a. Draw a simple, complete graph with four nodes

b. Determine the adjacency matrixes for the following graphs:

G1.

G2:

c. Using the graph shown below answer the following questions:

20
 i. What type of graph is this?
ii. Which vertices are reachable from vertex 3?
iii. What is the length of the shortest path from vertex 3 iv. Give a path from
vertex 1 to vertex 3 of length 4 (2mks)

a. Sketch a graph having vertices {1, 2, 3, 4, 5, 6}, edges {a1, a2, a3, a4, a5, a6, a7} where
edges a1 = 1-2, a2 = 2-3, a3 = 3-4, a4 = 4-5, a5=3-5, a6 = 5-6, a7 = 6-6.
b. Determine the adjacency matrix for the graph drawn in 6a above
c. Why is adjacency matrix not efficient in computer data representation?
d. What alternative data structure can be used for graph representation in computer
processing?
e. What is the degree of vertex 5 in the graph drawn in a above?

II.4. References

1. GRIMALDI, R.P.: Discrete and Combinatorial Mathematics. Addison–Wesley (2003)

2. GROSS, J. & YELLEN, J.: Graph Theory and Its Applications. CRC Press (2006)
3. GROSS, J. & YELLEN, J.: Handbook of Graph Theory. CRC Press (2003)
4. HOPCROFT, J.E. & ULLMAN, J.D.: Introduction to Automata Theory, Languages, and
Computation. Addison–Wesley (1979)
5. JUNGNICKEL, D.: Graphs, Networks and Algorithms. Springer–Verlag (2004)

21
MODULE III

GRAPH ALGORITHM

III.1. Module Objective

The objectives of this module are to:

• Explore Euler’s paths and circuits.
• Explore Hamiltonian path and circuits
• Examines the various basic graph algorithms such as the minimal spanning tree algorithm
– Euler’s and Floyd's algorithm.
• Study the applications of graph algorithms to mathematical and real life situational
problems such as the travelling salesman problem.

III.2. Lecture Note

Graph Algorithms and Application

The major role of graph theory in computer applications is the development of graph algorithms.
Numerous algorithms are used to solve problems that are modelled in the form of graphs. These
algorithms are used to solve the graph theoretical concepts which intern used to solve the
corresponding computer science application problems. Some of the algorithms are as follows:
1. Shortest path algorithm in a network
2. Finding a minimum spanning tree
3. Finding graph planarity
4. Algorithms to find adjacency matrices.
5. Algorithms to find the connectedness
6. Algorithms to find the cycles in a graph
7. Algorithms for searching an element in a data structure and so on.
Various computer languages are used to support the graph theory concepts. The main goal of such
languages is to enable the user to formulate operations on graphs in a compact and natural manner.

Euler paths and circuits

1.1. The Könisberg Bridge Problem
Könisberg was a town in Prussia, divided in four land regions by the river Pregel. The regions were
connected with seven bridges as shown in figure III.1(a). The problem is to find a tour through the
town that crosses each bridge exactly once or better still, the problem is equivalent with that of
finding a path in the graph of figure III.1(b) such that it crosses each edge exactly one time.
Leonhard Euler gave a formal solution for the problem and established the graph theory field in
mathematics.

The dot, called the node represents land in this problem. The line joining the nodes is called edge
and represents a bridge in this problem. Instead of an exhaustive search of every path, Euler found
out a very simple criterion for checking the existence of such paths in a graph and gave the solution:
It is not possible to cross all the bridges exactly once.

22
Figure III.1: The bridges of Könisberg (a) and corresponding graph (b)

Euler Path is a path in the graph that passes each edge only once. The problem of Seven Bridges of
Konigsberg can be also stated: Does Euler Path exist in the graph?
Euler Circut is a path in the graph that passes each edge only once and return back to its original
position. From Definition, Euler Circuit is a subset of Euler Path.

An Euler path is defined as a path that crosses each edge of the graph exactly once. If the path is
closed, we have an Euler circuit.
Checking the existence of an Euler path
The existence of an Euler path in a graph is directly related to the degrees of the graph’s vertices.
Euler formulated the three following theorems of which the first two set a sufficient and necessary
condition for the existence of an Euler circuit or path in a graph respectively.
Theorem 1: An undirected graph has at least one Euler path iff it is connected and has two or zero
vertices of odd degree.
Theorem 2: An undirected graph has an Euler circuit iff it is connected and has zero vertices of
odd degree.
Theorem 3: The sum of the degrees of every vertex of a graph is even and equals to twice the
number of edges

Figure III.2: Euler’s path and Euler’s circuit

Degree of Nodes: Number of Edges on a vertex

Euler Path existence: 2 or no odd-degree nodes exist in the graph.
Euler Circuit existence: no odd-degree nodes exist in the graph.
Finding an Euler path
There are several ways to find an Euler path in a given graph. Since it is a relatively simple problem
it can solve intuitively respecting a few guidelines:
• Always leave one edge available to get back to the starting vertex (for circuits) or to the
other odd vertex (for paths) as the last step.
23
 • Don't use an edge to go to a vertex unless there is another edge available to leave that vertex
(except for the last step).
This technique certainly gives results for simple graphs but we surely need a formal algorithm to
find Euler circuits. In the following sections we present two algorithms serving that purpose.

Fluery’s algorithm for Euler’s Circuits and Paths

Fluery’s algorithm can be applied in searches for both Euler circuits and paths.
FLUERY
Input: A connected graph G = (V, E) with no vertices of odd degree
Output: A sequence P of vertices and their connecting edges indicating the Euler circuit.
1 Choose any vertex u0 in G.
2 P = u0
3 if Pi = u0e1u1e2…eiui choose edge ei+1 so that
1. ei+1 is adjacent to ei
2. Removal of ei+1 does not disconnect G – {e1,…, ei} (i.e. ei+1 is
not a bridge). 4 if P includes all edges in E return P
5 goto 3

The algorithm for finding an Euler path instead of a circuit is almost identical to the one just
described. Their only difference lies in step 1 where we must choose one of the vertices of odd
degree as the beginning vertex.

A Constructive Algorithm for Euler’s Circuits and Paths

The ideas used in the proof of Euler’s theorem can lead us to a recursive constructive algorithm to
find an Euler path in an Eulerian graph.
CONSTRUCT
Input: A connected graph G = (V, E) with two vertices of odd degree.
Output: The graph with its edges labeled according to their order of appearance in the path found.
1 Find a simple cycle in G.
2 Delete the edges belonging in C.
3 Apply algorithm to the remaining graph.
4 Amalgamate Euler cycles found to obtain the complete Euler cycle.

Applications
Eulerian graphs are used rather extensively, as they’re necessary to solve important problems in
telecommunication, parallel programming development and coding. Moreover, the corresponding
theory underlies in many classic mathematical problems.

The Hamiltonian Circuit Problem

A problem that at first sight seems to be very close to the Eulerian path is the Hamiltonian
Circuit/Cycle problem, defined as follows:
Given a (connected) graph G(V,E) find a circuit that starts at a vertex of a graph, passes through
every vertex exactly once, and returns to the starting vertex. This circuit is called Hamiltonian
Circuit.

24
The problem can be slightly changed so that the ending vertex does not have to be the starting one.
Instead of a Hamiltonian circuit we get a homonymous path. The problem of deciding whether a
graph has a Hamiltonian circuit/path (and finding one) or not is NP-complete in the general case.
For weighted graphs a more important and practically useful challenge is to find a Hamiltonian
path with the minimum sum of weights over the edges we pass. This path is called an optimal
Hamiltonian path. The problem is well known as the Travelling Salesman Problem (TSP).

Existence of Hamiltonian Path or Circuit

To check for the existence of a Hamiltonian path or circuit it is useful to try to find whether the
examined graph has one. This is an NP-Complete problem as well but for some specific types of
graphs criteria that help us decide faster have been set. Here is a list of the most useful and
commonly used:
A directed graph G(V,E) such that for each pair vi , vj in V either(vi , vj) or (exclusive) (vj, vi)
belongs in E is called Tournament Graph and a tournament graph always contains a Hamilton
path. The proof is a matter of induction.
For undirected graphs it is obvious that any complete or chain (all nodes have degree=2) graph
has Hamiltonian circuits.

Necessary Conditions for Hamilton Circuit

Assume G=(V, E) has more than 2 nodes.
1. No vertex of degree 1. If node a has degree 1, then the other endpoint of the edge incident to a
must be visited at least twice in any circuit of G.
2. If a node has degree 2, then both edges incident to it must be in any Hamilton circuit.
3. No smaller circuits contained in any Hamilton circuit (the start/endpoint of any smaller circuit
would have to be visited twice).
4. There must exist a subgraph of G with the following properties:
1. H contains every vertex of G
2. H is connected
3. H has the same number of edges as vertices
4. H has every node with degree 2
Then, the subgraph H is the Hamilton circuit in the graph G.

The Traveling Salesman Problem

The traveling salesman problem (TSP), was originally set and defined as “Which is the best way
for a salesman to visit a given number of cities?” Here, best has the meaning of the minimum
distance the salesman has to cover, but depending on the context given it may mean different things
such as lower cost, minimum time etc.
We can represent each city by using a node, the way between any two cities as an edge between the
respective nodes and the distance as the weight of the edge. The result is a complete graph, unless
there is no way to go directly from one city to some other. In this case the respective edge does not
exist.
The algorithm proposed is a brutal-force algorithm:
1. List all possible Hamilton circuits (of course exact reversals can be omitted)
2. Find the weight of each
3. Choose (the) one with the smallest weight
This algorithm always works, but its main backbone is its cost.

25
The 1st step can only be solved by exhaustive search. For a computer doing 10,000 circuits/sec, it
would take about 18 seconds to handle 10 vertices, 50 days to handle 15 vertices, 2 years for 16
vertices, 193,000 years for 20 vertices!!!
This has made researchers change their approach to the problem and find approximation algorithms
that may not produce the optimal result but get close to it and (more important) work in acceptable
time limits. Three such algorithms are given here: They all take as input a graph and return a
closeto-the-optimal-Hamilton circuit (if one exists).

Cheapest Link Algorithm (CLA)

1. Choose the edge with the smallest weight (the "cheapest" edge), randomly breaking ties.
2. Keep choosing the "cheapest" edge unless it (a) closes a smaller circuit OR (b) results in 3
selected edges coming out of a single vertex Continue until the Hamilton Circuit is complete

Figure III.3: Graph to demonstrate cheapest link algorithm

Figure III.3a shows a graph on which we apply this algorithm: We choose AC(min weight). Then,
since no restriction will be validated we add AD. Now if we try to add DC we get a cycle ACDA
(Fig. III.3b) so we do not add it. Instead we take the next lower weighted edge DB and add it. If we
add ED node D will have degree 3(Fig III.3c), so we do not use it. Instead we add EC and EB
successively so we get a Hamiltonian cycle ADBECA (Fig III.3d) with total cost 20

Figure III.3: Graph to demonstrate cheapest link algorithm

Nearest Neighbour Algorithm (NNA)

1. Start at a vertex (think of it as your Home city)

26
2. Travel to the vertex that you haven’t been to yet whose path has the smallest weight If there is a
tie, pick randomly.
3. Continue until you travel to all vertices
4. Travel back to your starting vertex

Figure III.4: Graph to demonstrate Nearest Neighbour Algorithm

Example and explanation: In figure III.4 we show how this algorithm is applied for the graph of the
figure III.3.a. Randomly we choose E as the initial vertex. We choose the edge with the lower cost
starting from E (Fig III.4.a) which is ED. Same way we add DA and AC and reach III.4.b. Here we
cannot use the edge with the lower cost (CD) since D has already been visited so we travel to B
through CB(Fig III.4.c) and finally reach the circuit EDACBE (Fig III.4.d) with total cost 25 (worse
than the previous)

Figure III.4: Graph to demonstrate Nearest Neighbour Algorithm

Repetitive Nearest Neighbor Algorithm (RNNA)

1. DO NNA for each vertex (city)
2. Choose the best solution (smallest weight)
3. If necessary, rewrite this solution with a particular starting vertex (Home)

27
It uses the previous algorithm, which is depended on the choice of the initial node. That’s why we
apply it for every initial node possible and choose the best circuit among the ones produced.

The criterion to decide which is the more efficient is the relative error: Re = (difference from
optimal solution)/(optimal solution)
A similar problem is to find a Hamiltonian path given the initial and final nodes. This would help
the salesman end his journey at his home and not the city he was at the beginning. There exists a
constructive algorithm that gives us the optimal Hamilton path between two nodes a (initial) and p
(terminal). This algorithm tries to find the optimal path between any two vertices visiting any
number (<=|V|-2) of vertices starting from 0 (no intermediates) and adding one node to the (new)
path at the time. e.g. in order to find the minimum path between a and p that has 3 intermediate
nodes we find all the paths from any node k to p with 2 intermediate nodes (¹a, p) and add (a,k) and
choose the minimum.

Optimal Hamilton Path

Input : w: matrix of weights, a: initial node, p: final node and N=|V|
Output: The optimal Hamilton Path optimal
Hamilton Path(w,a,p)
S: subset {1,2,…,N}
Array H [N] [N] [S]
int i,j,s,k
1. for i,j=1 to N
2. H[i,j,Æ]=w(i,j)
3. for s=1 to N-2
4. for i,j=1 to N
5. for each SÍ{[1…N]-{i,j}} with size s
6. H[i,j,S]=minkeS[d(i,k)+H(k,j,S-{k})]
7. return H[a,p,{1…N}-{a,p}]

The algorithm runs in T(2N) time significantly lower than T(N!) which gives us the ability to work
with larger graphs in appropriate time. The reason we have this complexity has to do with the
number of the paths we have to calculate in step 6 before we select the minimum among them.

3. Comparison of Euler and Hamilton Circuits

The similarity of the two problems discussed is just illusionary since there are many differences
both in their practical appliances and their theoretical analysis. First of all, the Eulerian problem
takes edges in consideration while the Hamiltonian one has to do with vertices. The first one tries
to pass through every edge of the graph exactly once, while the second one tries to visit all the
nodes exactly once without retracing any edge.
The nature of the problems shows that in the first case we are not interested whether the graph is
weighted or not, while the second one has much bigger practical use if the graph is weighted. The
analysis showed that despite their “similarity” the Eulerian problem can be solved in linear time
while the question whether a Hamilton cycle exists or not can only be answered in NP-time in the
general case O(n!). The table below is a list with the most important differences between the two
problems.

28
Euler Circuit Hamilton Circuit
Repeated visits to a given node are allowed Visit each node exactly once
Traverse each edge exactly once (by definition Repeated traversals of a given edge are not
of problem). permitted, since that would result in visiting a
node more than once
No node may be omitted(if so, one of the edges No node may be omitted(by definition of the
incident to the node would not be traversed). problem).
No edges may be omitted Any edge may be omitted

III.3. Assessments

Q1. For each of the following four graphs, decide if it has an Eulerian trail an Eulerian circuit, both,
or neither. Give a brief justification in each case

Q2. Define what it means for two graphs G1, G2 to be isomorphic

Q3. Define the adjacency matrix of an n-vertex graph G = (V, E)

Q4. (i) Define an Eulerian graph, and state Euler’s theorem which characterizes such graphs in
terms of their vertex degree.

(ii) Explain the concept of a map G.

(iii) Prove that a map G is 2-colourable if and only if G is an Eulerian graph.

III.4. References

1. SWAMY, M.N.S. & THULASIRAMAN, K.: Graphs, Networks, and Algorithms. Wiley (1981)
2. SWAMY, M.N.S. & THULASIRAMAN, K.: Graphs: Theory and Algorithms. Wiley (1992)
3. VÁGÓ, I.: Graph Theory. Application to the Calculation of Electrical Networks. Elsevier (1985)
4. WALTHER, H.: Ten Applications of Graph Theory. Kluwer (1985)
5. WEST, D.B.: Introduction to Graph Theory. Prentice–Hall (1996)
6. N. BIGGS, “Algebraic Graph Theory”, Cambridge University Press, (2nd ed.) 1993.
7. C. GODSIL, G.F. ROYLE, “Algebraic Graph Theory”, Springer, 2001

29