Graph Theory

BCA 517-GRAPH THEORY

Unit-1
Introduction to Graphs: Definition and types of graphs (simple, multigraph,
pseudograph), degree, order, and size, special graphs (complete, regular,
bipartite, cycle, wheel), Applications of graphs.
Unit-2
Graph Representation & Connectivity: Adjacency matrix, incidence matrix,
adjacency list. Graph isomorphism. Walk, path, cycle. Connected and
disconnected graphs. Eulerian and Hamiltonian paths and circuits.
Trees and Spanning Trees: Definition and properties of trees, rooted trees,
binary trees, tree traversal techniques (infix, prefix, postfix), spanning trees,
minimum spanning trees (Prim’s & Kruskal’s).
Unit-3
Planar Graphs and Coloring: Planar graphs and Euler’s formula (basic),
graph coloring, chromatic number, Four Color Theorem (conceptual),
applications in scheduling and map coloring.
Graph Traversal & Shortest Path: BFS and DFS with examples. Shortest
path: Dijkstra's algorithm.

i
 Graph Theory

Unit 1 Graph Theory — Introduction

What is a Graph?
A graph is a pictorial representation of a set of objects where some pairs of objects are
connected by links. The interconnected objects are represented by points termed
as vertices, and the links that connect the vertices are called edges.

Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of
edges, connecting the pairs of vertices. Take a look at the following graph:

In the above graph,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Applications of Graph Theory

Graph theory has its applications in diverse fields of engineering −

Electrical Engineering: The concepts of graph theory is used extensively in designing

circuit connections. The types or organization of connections are named as topologies.
Some examples for topologies are star, bridge, series, and parallel topologies.

Computer Science: Graph theory is used for the study of algorithms. For example,

• Kruskal's Algorithm
• Prim's Algorithm
• Dijkstra's Algorithm

Computer Network: The relationships among interconnected computers in the network

follows the principles of graph theory.
 Graph Theory
Graph Theory

Science: The molecular structure and chemical structure of a substance, the DNA
structure of an organism, etc., are represented by graphs.

Linguistics: The parsing tree of a language and grammar of a language uses graphs.

Fundamentals of Graph

Point
A point is a particular position in a one-dimensional, two-dimensional, or three-
dimensional space. For better understanding, a point can be denoted by an alphabet. It
can be represented with a dot.

Example

Here, the dot is a point named ‘a’.

Line
A Line is a connection between two points. It can be represented with a solid line.

Example

Here, ‘a’ and ‘b’ are the points. The link between these two points is called a line.

Vertex
A vertex is a point where multiple lines meet. It is also called a node. Similar to points, a
vertex is also denoted by an alphabet.

Example

Here, the vertex is named with an alphabet ‘a’.

Edge

An edge is the mathematical term for a line that connects two vertices. Many edges can
2
 Graph Theory
be formed from a single vertex. Without a vertex, an edge cannot be formed. There must
be a starting vertex and an ending vertex for an edge.

Example

Here, ‘a’ and ‘b’ are the two vertices and the link between them is called an edge.

Graph
A graph ‘G’ is defined as G = (V, E) Where V is a set of all vertices and E is a set of all
edges in the graph.

Example 1

In the above example, ab, ac, cd, and bd are the edges of the graph. Similarly, a, b, c,
and d are the vertices of the graph.

Example 2

In this graph, there are four vertices a, b, c, and d, and four edges ab, ac, ad, and cd.

Loop
In a graph, if an edge is drawn from vertex to itself, it is called a loop.

Example 1

3
 Graph Theory

In the above graph, V is a vertex for which it has an edge (V, V) forming a loop.

Example 2

In this graph, there are two loops which are formed at vertex a, and vertex b.

Degree of Vertex
It is the number of vertices adjacent to a vertex V.

Notation − deg(V).

In a simple graph with n number of vertices, the degree of any vertices is:

deg(v) ≤ n – 1 ∀ v ∈ G

A vertex can form an edge with all other vertices except by itself. So the degree of a vertex
will be up to the number of vertices in the graph minus 1. This 1 is for the self-vertex
as it cannot form a loop by itself. If there is a loop at any of the vertices, then it is not a
Simple Graph.

Degree of vertex can be considered under two cases of graphs:

• Undirected Graph
• Directed Graph

Degree of Vertex in an Undirected Graph

An undirected graph has no directed edges. Consider the following examples.

Example 1

Take a look at the following graph:

4
 Graph Theory

In the above Undirected Graph,

• deg(a) = 2, as there are 2 edges meeting at vertex ‘a’.

• deg(b) = 3, as there are 3 edges meeting at vertex ‘b’.
• deg(c) = 1, as there is 1 edge formed at vertex ‘c’
• So ‘c’ is a pendent vertex.
• deg(d) = 2, as there are 2 edges meeting at vertex ‘d’.
• deg(e) = 0, as there are 0 edges formed at vertex ‘e’.
• So ‘e’ is an isolated vertex.

Example 2

Take a look at the following graph:

In the above graph,

deg(a) = 2, deg(b) = 2, deg(c) = 2, deg(d) = 2, and deg(e) = 0.

The vertex ‘e’ is an isolated vertex. The graph does not have any pendent vertex.

Degree of Vertex in a Directed Graph

In a directed graph, each vertex has an indegree and an outdegree.

Indegree of a Graph

• Indegree of vertex V is the number of edges which are coming into the vertex V.

5
 Graph Theory
• Notation − deg−(V).

Outdegree of a Graph

• Outdegree of vertex V is the number of edges which are going out from the vertex
V.
• Notation − deg+(V).

Consider the following examples.

Example 1

Take a look at the following directed graph. Vertex ‘a’ has two edges, ‘ad’ and ‘ab’, which

are going outwards. Hence its outdegree is 2. Similarly, there is an edge ‘ga’, coming
towards vertex ‘a’. Hence the indegree of ‘a’ is 1.

The indegree and outdegree of other vertices are shown in the following table:

Vertex Indegree Outdegree

a 1 2

b 2 0

c 2 1

d 1 1

e 1 1

f 1 1

g 0 2

Example 2

6
 Graph Theory
Take a look at the following directed graph. Vertex ‘a’ has an edge ‘ae’ going outwards
from vertex ‘a’. Hence its outdegree is 1. Similarly, the graph has an edge ‘ba’ coming
towards vertex ‘a’. Hence the indegree of ‘a’ is 1.

The indegree and outdegree of other vertices are shown in the following table −

Vertex Indegree Outdegree

a 1 1

b 0 2

c 2 0

d 1 1

e 1 1

Pendent Vertex

By using degree of a vertex, we have a two special types of vertices. A vertex with degree
one is called a pendent vertex.

Example

Here, in this example, vertex ‘a’ and vertex ‘b’ have a connected edge ‘ab’. So with respect
to the vertex ‘a’, there is only one edge towards vertex ‘b’ and similarly with respect to
the vertex ‘b’, there is only one edge towards vertex ‘a’. Finally, vertex ‘a’ and vertex ‘b’
has degree as one which are also called as the pendent vertex.

Isolated Vertex
A vertex with degree zero is called an isolated vertex.

7
 Graph Theory
Example

the degree of both the vertices ‘a’ and ‘b’ are zero. These are also called as isolated
vertices.

Adjacency
Here are the norms of adjacency:

• In a graph, two vertices are said to be adjacent, if there is an edge between the
two vertices. Here, the adjacency of vertices is maintained by the single edge that
is connecting those two vertices.

• In a graph, two edges are said to be adjacent, if there is a common vertex between
the two edges. Here, the adjacency of edges is maintained by the single vertex that
is connecting two edges.

Example 1

In the above graph:

• ‘a’ and ‘b’ are the adjacent vertices, as there is a common edge ‘ab’ between the

• ‘a’ and ‘d’ are the adjacent vertices, as there is a common edge ‘ad’ between them.
• ab’ and ‘be’ are the adjacent edges, as there is a common vertex ‘b’ between them.
• be’ and ‘de’ are the adjacent edges, as there is a common vertex ‘e’ between them.

Example 2

8
 Graph Theory

In the above graph:

• a’ and ‘d’ are the adjacent vertices, as there is a common edge ‘ad’ between them.
• ‘c’ and ‘b’ are the adjacent vertices, as there is a common edge ‘cb’ between them.
• ‘ad’ and ‘cd’ are the adjacent edges, as there is a common vertex ‘d’ between them.
• ac’ and ‘cd’ are the adjacent edges, as there is a common vertex ‘c’ between them.

Parallel Edges
In a graph, if a pair of vertices is connected by more than one edge, then those edges are
called parallel edges.

In the above graph, ‘a’ and ‘b’ are the two vertices which are connected by two edges ‘ab’
and ‘ab’ between them. So it is called as a parallel edge.

Multi Graph
A graph having parallel edges is known as a Multigraph.

Example 1

In the above graph, there are five edges ‘ab’, ‘ac’, ‘cd’, ‘cd’, and ‘bd’. Since ‘c’ and ‘d’ have
two parallel edges between them, it a Multigraph.

9
 Graph Theory
Example 2

In the above graph, the vertices ‘b’ and ‘c’ have two edges. The vertices ‘e’ and ‘d’ also
have two edges between them. Hence it is a Multigraph.

Degree Sequence of a Graph

If the degrees of all vertices in a graph are arranged in descending or ascending order,
then the sequence obtained is known as the degree sequence of the graph.

Example 1

Vertex A b c d e

Connecting to b,c a,d a,d c,b,e d

Degree 2 2 2 3 1

In the above graph, for the vertices {d, a, b, c, e}, the degree sequence is {3, 2, 2, 2,
1}.

10
 Graph Theory

Example 2

Vertex A b c d e f

Connecting to b,e a,c b,d c,e a,d -

Degree 2 2 2 2 2 0

In the above graph, for the vertices {a, b, c, d, e, f}, the degree sequence is {2, 2, 2, 2,
2, 0}.

2. G Eccentricity of a Vertex
The maximum distance between a vertex to all other vertices is considered as the
eccentricity of vertex.

Notation − e(V)
The distance from a particular vertex to all other vertices in the graph is taken and among
those distances, the eccentricity is the highest of distances.

Example

In the above graph, the eccentricity of ‘a’ is 3.

The distance from ‘a’ to ‘b’ is 1 (‘ab’),

from ‘a’ to ‘c’ is 1 (‘ac’),

from ‘a’ to ‘d’ is 1 (‘ad’),

from ‘a’ to ‘e’ is 2 (‘ab’-‘be’) or (‘ad’-‘de’),

from ‘a’ to ‘f’ is 2 (‘ac’-‘cf’) or (‘ad’-‘df’),

from ‘a’ to ‘g’ is 3 (‘ac’-‘cf’-‘fg’) or (‘ad’-‘df’-‘fg’).

So the eccentricity is 3, which is a maximum from vertex ‘a’ from the distance between
‘ag’ which is maximum.

In other words,

e(b) = 3

e(c) = 3
11
 Graph Theory
e(d) = 2

e(e) = 3

e(f) = 3

e(g) = 3

Radius of a Connected Graph

The minimum eccentricity from all the vertices is considered as the radius of the Graph G.
The minimum among all the maximum distances between a vertex to all other vertices is
considered as the radius of the Graph G.

Notation − r(G)
From all the eccentricities of the vertices in a graph, the radius of the connected graph is
the minimum of all those eccentricities.

Example

In the above graph r(G) = 2, which is the minimum eccentricity for ‘d’.

Diameter of a Graph
The maximum eccentricity from all the vertices is considered as the diameter of the Graph
G. The maximum among all the distances between a vertex to all other vertices is
considered as the diameter of the Graph G.

Notation − d(G): From all the eccentricities of the vertices in a graph, the diameter of
the connected graph is the maximum of all those eccentricities.

Example

In the above graph, d(G) = 3; which is the maximum eccentricity.

Central Point
If the eccentricity of a graph is equal to its radius, then it is known as the central point of
the graph. If

e(V) = r(V),

then ‘V’ is the central point of the Graph ’G’.

Example

In the example graph, ‘d’ is the central point of the graph.

e(d) = r(d) = 2

Centre
The set of all central points of ‘G’ is called the centre of the Graph.

Example

In the example graph, {‘d’} is the centre of the Graph.

12
 Graph Theory

Circumference
The number of edges in the longest cycle of ‘G’ is called as the circumference of ‘G’.

Example

In the example graph, the circumference is 6, which we derived from the longest cycle a-
c-f-g-e-b-a or a-c-f-d-e-b-a.

Girth
The number of edges in the shortest cycle of ‘G’ is called its Girth.

Notation: g(G).

Example − In the example graph, the Girth of the graph is 4, which we derived from the
shortest cycle a-c-f-d-a or d-f-g-e-d or a-b-e-d-a.

Sum of Degrees of Vertices Theorem

If G = (V, E) be a non-directed graph with vertices V = {V1, V2,…Vn} then

n ∑ i=1 deg(Vi) = 2|E|

Corollary 1

If G = (V, E) be a directed graph with vertices V = {V1, V2,…Vn}, then

n ∑ i=1 deg+(Vi) = |E| = n ∑ i=1 deg−(Vi)

Corollary 2

In any non-directed graph, the number of vertices with Odd degree is Even.

Corollary 3

In a non-directed graph, if the degree of each vertex is k, then

k|V| = 2|E|

Corollary 4

In a non-directed graph, if the degree of each vertex is at least k, then

k|V| ≤ 2|E|

Corollary 5

In a non-directed graph, if the degree of each vertex is at most k, then

k|V| ≥ 2|E|

13
 Graph Theory ― Types of Graph Theory

Graphs

There are various types of graphs depending upon the number of vertices, number of
edges, interconnectivity, and their overall structure. We will discuss only a certain few
important types of graphs in this chapter.

Null Graph
A graph having no edges is called a Null Graph.

Example

In the above graph, there are three vertices named ‘a’, ‘b’, and ‘c’, but there are no edges
among them. Hence it is a Null Graph.

Trivial Graph
A graph with only one vertex is called a Trivial Graph.

Example

In the above shown graph, there is only one vertex ‘a’ with no other edges. Hence it is a
Trivial graph.

Non-Directed Graph
A non-directed graph contains edges but the edges are not directed ones.
14
Example

15
 Graph Theory

In this graph, ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’ are the vertices, and ‘ab’, ‘bc’, ‘cd’, ‘da’, ‘ag’, ‘gf’,
‘ef’ are the edges of the graph. Since it is a non-directed graph, the edges ‘ab’ and ‘ba’
are same. Similarly other edges also considered in the same way.

Directed Graph
In a directed graph, each edge has a direction.

Example

In the above graph, we have seven vertices ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, and ‘g’, and eight edges
‘ab’, ‘cb’, ‘dc’, ‘ad’, ‘ec’, ‘fe’, ‘gf’, and ‘ga’. As it is a directed graph, each edge bears an
arrow mark that shows its direction. Note that in a directed graph, ‘ab’ is different from
‘ba’.

16
 Graph Theory

Simple Graph
A graph with no loops and no parallel edges is called a simple graph.

• The maximum number of edges possible in a single graph with ‘n’ vertices
is nC2 where nC2 = n(n – 1)/2.
• The number of simple graphs possible with ‘n’ vertices = 2 c = 2n(n-1)/2.
n
2

Example

In the following graph, there are 3 vertices with 3 edges which is maximum excluding the
parallel edges and loops. This can be proved by using the above formulae.

The maximum number of edges with n=3 vertices:

n
C2 = n(n–1)/2

= 3(3–1)/2

= 6/2

= 3 edges

The maximum number of simple graphs with n=3 vertices:

2 C = 2n(n-1)/2
n
2

= 23(3-1)/2

= 23
=8
These 8 graphs are as shown below:

17
 Graph Theory

Pseudograph

In graph theory, a pseudograph is a type of graph that allows both multiple edges
(more than one edge connecting the same pair of vertices) and loops (edges that connect a
vertex to itself). This contrasts with a simple graph, which does not permit either multiple edges
or loops.

Regular Graph
A graph G is said to be regular, if all its vertices have the same degree. In a graph, if
the degree of each vertex is ‘k’, then the graph is called a ‘k-regular graph’.

Example

In the following graphs, all the vertices have the same degree. So these graphs are called
regular graphs.

In both the graphs, all the vertices have degree 2. They are called 2-Regular Graphs.

Complete Graph
18
 Graph Theory
A simple graph with ‘n’ mutual vertices is called a complete graph and it is denoted by
‘Kn’. In the graph, a vertex should have edges with all other vertices, then it called
a complete graph.

In other words, if a vertex is connected to all other vertices in a graph, then it is called a
complete graph.

Example

In the following graphs, each vertex in the graph is connected with all the remaining
vertices in the graph except by itself.

In graph I,

a b c

a Not Connected Connected Connected

b Connected Not Connected Connected

c Connected Connected Not Connected

In graph II,

p q r s

p Not Connected Connected Connected Connected

q Connected Not Connected Connected Connected

r Connected Connected Not Connected Connected

s Connected Connected Connected Not Connected

19
 Graph Theory

Cycle Graph
A simple graph with ‘n’ vertices (n >= 3) and ‘n’ edges is called a cycle graph if all its
edges form a cycle of length ‘n’.

If the degree of each vertex in the graph is two, then it is called a Cycle Graph.

Notation: Cn

Example

Take a look at the following graphs:

• Graph I has 3 vertices with 3 edges which is forming a cycle ‘ab-bc-ca’.

• Graph II has 4 vertices with 4 edges which is forming a cycle ‘pq-qs-sr-rp’.
• Graph III has 5 vertices with 5 edges which is forming a cycle ‘ik-km-ml-lj-ji’.

Hence all the given graphs are cycle graphs.

Wheel Graph
A wheel graph is obtained from a cycle graph Cn-1 by adding a new vertex. That new vertex
is called a Hub which is connected to all the vertices of Cn.

Notation: Wn

No. of edges in Wn = No. of edges from hub to all other vertices +

No. of edges from all other nodes in cycle graph without a hub.

= (n–1) + (n–1)

= 2(n–1)

Example

Take a look at the following graphs. They are all wheel graphs.

20
 Graph Theory

In graph I, it is obtained from C3 by adding an vertex at the middle named as ‘d’. It is

denoted as W4.

Number of edges in W4 = 2(n-1) = 2(3) = 6

In graph II, it is obtained from C4 by adding a vertex at the middle named as ‘t’. It is
denoted as W5.

Number of edges in W5 = 2(n-1) = 2(4) = 8

In graph III, it is obtained from C6 by adding a vertex at the middle named as ‘o’. It is
denoted as W7.

Number of edges in W4 = 2(n-1) = 2(6) = 12

Cyclic Graph
A graph with at least one cycle is called a cyclic graph.

Example

In the above example graph, we have two cycles a-b-c-d-a and c-f-g-e-c. Hence it is called
a cyclic graph.

Acyclic Graph

21
 Graph Theory
A graph with no cycles is called an acyclic graph.

Example

In the above example graph, we do not have any cycles. Hence it is a non-cyclic graph.

Bipartite Graph
A simple graph G = (V, E) with vertex partition V = {V 1, V2} is called a bipartite graph if
every edge of E joins a vertex in V1 to a vertex in V2.

In general, a Bipertite graph has two sets of vertices, let us say, V1 and V2, and if an edge
is drawn, it should connect any vertex in set V1 to any vertex in set V2.

Example

In this graph, you can observe two sets of vertices − V1 and V2. Here, two edges named
‘ae’ and ‘bd’ are connecting the vertices of two sets V 1 and V2.

Complete Bipartite Graph

A bipartite graph ‘G’, G = (V, E) with partition V = {V1, V2} is said to be a complete bipartite
graph if every vertex in V1 is connected to every vertex of V2.

In general, a complete bipartite graph connects each vertex from set V1 to each vertex
from set V2.

Example

22
 Graph Theory
The following graph is a complete bipartite graph because it has edges connecting each
vertex from set V1 to each vertex from set V2.

If |V1| = m and |V2| = n, then the complete bipartite graph is denoted by Km, n.

• Km,n has (m+n) vertices and (mn) edges.

• Km,n is a regular graph if m=n.

In general, a complete bipartite graph is not a complete graph.

Km,n is a complete graph if m=n=1.

The maximum number of edges in a bipartite graph with n vertices is:

[n2/4]

If n=10, k5, 5= [n2/4] = [102/4] = 25.

Similarly, K6, 4=24

K7, 3=21

K8, 2=16

K9, 1=9

If n=9, k5, 4 = [n2/4] = [92/4] = 20

Similarly, K6, 3=18

K7, 2=14

K8, 1=8

‘G’ is a bipartite graph if ‘G’ has no cycles of odd length. A special case of bipartite graph
is a star graph.

Star Graph
A complete bipartite graph of the form K 1, n-1 is a star graph with n-vertices. A star graph
is a complete bipartite graph if a single vertex belongs to one set and all the remaining
vertices belong to the other set.

23
 Graph Theory
Example

In the above graphs, out of ‘n’ vertices, all the ‘n–1’ vertices are connected to a single
vertex. Hence it is in the form of K1, n-1 which are star graphs.

Complement of a Graph
Let 'G−' be a simple graph with some vertices as that of ‘G’ and an edge {U, V} is present
in 'G−', if the edge is not present in G. It
I and graph II are called complements of each other.

Example

In the following example, graph-I has two edges ‘cd’ and ‘bd’. Its complement graph-II
has four edges.

Note that the edges in graph-I are not present in graph-II and vice versa. Hence, the
combination of both the graphs gives a complete graph of ‘n’ vertices.

Note: A combination of two complementary graphs gives a complete graph.

If ‘G’ is any simple graph, then

|E(G)| + |E('G-')| = |E(Kn)|, where n = number of vertices in the graph.

Example

Let ‘G’ be a simple graph with nine vertices and twelve edges, find the number of edges
in 'G-'.

You have, |E(G)| + |E('G-')| = |E(Kn)|

12 + |E('G-')| =

9(9-1) / 2 = 9C2
24
 Graph Theory
12 + |E('G-')| = 36

|E('G-')| = 24

‘G’ is a simple graph with 40 edges and its complement 'G−' has 38 edges. Find the number
of vertices in the graph G or 'G−'.

Let the number of vertices in the graph be ‘n’.

We have, |E(G)| + |E('G-')| = |E(Kn)|

40 + 38 = n(n-1)/2

156 = n(n-1)

13(12) = n(n-1)

n = 13

25