MA253: DISCRETE MATHEMATICS AND ALGEBRA

UNIT : 3 - Graph Theory

Dr. Manoj Prajapati

SEMESTER 3 B.Tech. CE, IT, CSE

AY: 2024-25

1
 INTRODUCTION TO GRAPH THEORY
In a hockey tournament there are 8 teams which are denoted by S,T,U,V,W,X,Y,Z. Let
the following games has been played.

S → X, Z T → W, X, Z
U → Y, Z V → W,Y
W →T, V, Y X → S, T
Y → U, V, W Z → S, T, U

We may illustrate this situation by following diagram:

2
Or one can draw in the following way:

3
The team are represented by dots. Two such dots are join by line
segment wherever the corresponding teams have played each other.
In the figure-1, dots have been joined by straight line while in the
figure-2, some of the line segment are straight but some are not since
we are simply interested in which games have been played.
The manner in which the pair of dots is joined is of no importance so
it does not matter whether the line segments are straight or not.
Many real world situations can be described by means of such type of
diagram which are called graph.

4
Graph:
A graph 𝐺 = 𝑉 𝐺 , 𝐸 𝐺 consist of two finite set 𝑉(𝐺) and 𝐸(𝐺),
where
• 𝑉 𝐺 is the vertex set of graph, often denoted by just 𝑉 which is non-empty set,
and elements are called vertices or nodes
• 𝐸(𝐺) is the edge set of the graph often denoted by 𝐸 which is possibly empty
set, and elements are called edges or arc such that 𝑒 in 𝐸 assigned with an
unordered or ordered pair of vertices (𝑢, 𝑣).

Order of a Graph:
The order of a graph is number of vertices.
It is denoted by |𝑉(𝐺)|.

Size of a Graph:
The size of a graph is number of edges.
It is denoted by |𝐸(𝐺)|.
5
For the above example,
V={S, T, U, V, W, X, Y, Z} Order=8
E={e1, e2, e3, e4, e5, e6, e7, e8, e9, e10} Size=10

e1 ↔ (S,Z)
e2 ↔ (S,X) ( UNORDERED PAIR )
e3 ↔ (T,Z)
e4 ↔ (T,X)
e5 ↔ (T,W)
e6 ↔ (U,Y)
e7 ↔ (Y,V)
e8 ↔ (V,W)
e9 ↔ (W,Y)
e10 ↔ ( U,Z) 6
Loop (Self loop):
An edge of graph which join a vertex to itself is said to be a loop.
In figure given below 𝑒 is the loop:

Parallel Edge or Multi Edge:

• In undirected graph, if two (or more) edges have same vertices then
the edges are said to be parallel.
• In directed graph, if two (or more) edges with the same start vertex
and same end vertex then the edges are said to be parallel.

7
Example-1: Let G=(V, E), where V={a, b, c, d, e} and
E={e1, e2, e3,e4,e5, e6,e7,e8} and the ends of the edges are given by
e1 ↔ (a, b), e2 ↔ (b, c), e3 ↔ (c, c), e4 ↔ (c, d),
e5 ↔ (b, d), e6 ↔ (d, e), e7 ↔ (b, e), e8 ↔ (b, e).
Draw a diagram (or Graph).

Solution:

8
Example-2: Draw a diagram for each of the following graph
G(V, E), where V={a, b, c, d, e ,f} and
E={(a, d), (a, f) ,(b, c), (b ,f), (c, e)}.
Solution:

9
Isolated Vertex:
A vertex of a graph which is not end of any edge is said to be an isolated vertex.

Adjacent Vertices:
Two vertices of a graph which are joined by an edge are said to be adjacent
vertices or neighbours to each other.

Vertex Adjacent
Vertex
a b, c, e
b a
c a, e, d
d c ,e
e a, d, c
f (Isolated ----------
vertex)
10
Neighbour of vertex:
Let 𝑣 be a vertex of a graph 𝐺. If vertex 𝑣 is joined by an edge to a vertex 𝑢 of 𝐺,
then 𝑢 is said to be neighbour of vertex 𝑣.
In above graph 𝐺, neighbour of a vertex 𝑎 are 𝑏, 𝑐, 𝑒.

Neighbourhood set of vertex:

The set of all neighbour for fixed vertex 𝑣 of a graph 𝐺 is said to be neighbourhood
set for vertex 𝑣. It is denoted by 𝑁(𝑣).
In above graph 𝐺, 𝑁 𝑎 = {𝑏, 𝑐, 𝑒}.

Incident Edge with vertex:

An edge 𝑒 of a graph 𝐺 is said to be incident edge with vertex 𝑣 if 𝑣 is either start
vertex or end vertex of 𝑒.

Adjacent Edges:
Two edges 𝑒1 and 𝑒2 of the graph 𝐺 which are incident with a common vertex is said
to be adjacent edges.
11
 TYPES OF GRAPH

Simple Graph:
A Graph which neither contains loop nor parallel edges is known
as Simple Graph.

Multi Graph:
A Graph which contains multi edges(parallel) is known Multi
Graph.

12
Pseudo Graph:
A graph with loops and multi edges is called a Pseudo graph.

Null Graph:
There is no edges in graph is called Null Graph.

Trivial Graph:
A graph having one vertex and no edge is known as trivial graph.

Remark: Every Trivial graph is a null graph but every null graph need not to be trivial
graph.
13
Finite Graph and Infinite Graph:
A graph with finite numbers of vertices is called finite graph.
A graph which is not finite is known as infinite graph.
Note: A graph with finite number of vertices must contain finite
number of edges.

Directed Graph(Digraph):
A directed graph is a graph in which every edge have a direction
associated with them.
The notation 𝒆 → 𝒖, 𝒗 says 𝑒 is an directed edge with initial
vertex 𝑢 and end vertex 𝑣.

14
Mixed Graph:
A Graph is known as Mixed Graph if some edges are directed and
some edges are undirected.

15
 Graph Terminology
Type Edges Multiple Edges Loop
Simple Graph Undirected No No
Simple directed Graph Directed No No
Multigraph Undirected Yes No
Directed multigraph Directed Yes Yes
Pseudo Graph Undirected Yes Yes
Mixed Graph Directed and Undirected Yes Yes

Weighted Graph:
A weighted graph is a graph 𝐺 in which each edge 𝑒 has been assign a real number 𝑤(𝑒).
Here 𝑤(𝑒) is said to be weight(or length) of edge 𝑒.
The weighted can represent various attributes, such as time, cost or distance.

Complete Graph:
A simple graph in which each pair of distinct vertices is joined by an edge is said to be
complete graph.
A complete graph with 𝑛 vertices is denoted by 𝑲𝒏 .
16
Complete graph with one, two, three, four, five, six vertices.

𝑛(𝑛−1)
Remark: The number of edges of a complete graph 𝐾𝑛 is .
2

Example: Find the number of edges in the graphs 𝑲𝟏𝟐 and 𝑲𝟏𝟓 .
𝑛(𝑛−1)
Solution: The number of edges of in 𝐾𝑛 is .
2
(12)(12−1)
For 𝐾12 , the number of edges in 𝐾12 is = 66.
2
(15)(15−1)
For 𝐾15 , the number of edges in 𝐾15 is = 105.
2
17
Bipartite Graph:
If vertex set 𝑉 of a graph 𝐺 can be divided into two non-empty disjoint
subset 𝑋 and 𝑌 (i.e. V = X ∪ 𝑌, 𝑋 ≠ 𝜙, 𝑌 ≠ 𝜙, 𝑋 ∩ 𝑌 = 𝜙) such that each
edge of 𝐺 has one end point in 𝑋 and one end point in 𝑌, then
𝐺 is said to be bipartite graph.
Note: From the definition, it is clear that bipartite graph does not have any
loop.

Complete Bipartite Graph:

A simple bipartite graph with partition 𝑉 = 𝑋 ∪ 𝑌 is said to be complete
bipartite graph if every vertex in 𝑋 is joined to each vertex of 𝑌.

Note: Let 𝐺 be a complete bipartite graph with partition 𝑉 = 𝑋 ∪ 𝑌.

If 𝑋 = 𝑚 and 𝑌 = 𝑛 where 𝑚 ≤ 𝑛, then the total number of edges in a
complete bipartite graph are 𝑚𝑛 because each 𝑚 vertices is connected to
each of 𝑛 vertices.
It is denoted by 𝐾𝑚,𝑛 where 𝑚 ≤ 𝑛.
18
The complete bipartite graph 𝐾2,3 , 𝐾3,3 , 𝐾3,4 , 𝐾2,6 are as follows:

19
 Degree of a vertex in undirected graph

Degree of Vertex:
Let 𝐺 be an undirected graph and 𝑣 be any vertex of 𝐺. The number of edges of 𝐺
connected with the vertex 𝑣 is called degree of a vertex 𝑣.
Loop is counted twice.
It is denoted by 𝑑(𝑣) or deg(𝑣) or 𝑑𝐺 (𝑣).

Remark: The degree of a vertex of a simple undirected graph 𝐺 on 𝑛 vertices

cannot exceed 𝑛 − 1, i.e. 𝑑 𝑣 ≤ 𝑛 − 1.

Odd Vertex and Even vertex:

In an undirected graph, a vertex with odd degree is said to be odd vertex and vertex
with even degree is said to be even vertex.
Remarks:
1. The degree of vertex is also known as its valency.
2. The degree of an isolated vertex is zero.
3. The vertex with degree one is known as Pendant vertex. 20
Example: Find the degree of the vertices in the given graph. Also find
the even and odd vertex in the given graph.

Solution:
Vertex(𝒗𝒊 ) Degree of vertex 𝒅(𝒗𝒊 ) Odd/Even degree

𝑣1 3 Odd
𝑣2 3 Odd
𝑣3 2 Even
𝑣4 6 Even
𝑣5 4 Even
21
 Degree of a vertex in directed graph
Indegree of Vertex:
The in degree of a vertex 𝑣 in directed graph is the number edges
ending at it.
It is denoted by indeg(𝑣) or 𝑑+ (𝑣).

Out Degree of Vertex:

The out degree of a vertex 𝑣 in a directed graph is the number of
edges beginning from it.
It is denoted by outdeg(𝑣) or 𝑑− (𝑣).

The total degree is the sum of in degree and out degree.

22
Example : Find the in degree and out degree of the vertices in
following graph. Also find the even and odd vertex in the graph.

23
Solution:

Vertex(𝒗𝒊 ) In degree Out degre Total degree Odd/Even

𝒅+ (𝒗𝒊 ) 𝒅− (𝒗) 𝒅(𝒗𝒊 ) vertex
𝑣1 0 3 3 Odd
𝑣2 2 1 3 Odd
𝑣3 2 2 4 Even
𝑣4 1 2 3 Odd
𝑣5 3 0 3 Odd
𝑣6 1 1 2 Even
𝑣7 0 0 0 Even

24
Example: Find the in degree and out degree of the vertices
in the given graph.

Solution:
Vertex(𝒗𝒊 ) In degree Out degre Total degree Odd/Even
𝒅+ (𝒗𝒊 ) 𝒅− (𝒗) 𝒅(𝒗𝒊 ) vertex
𝑟 0 1 1 Odd
𝑢 1 1 2 Even
𝑣 2 1 3 Odd
𝑤 1 1 2 Even
25
Handshaking Theorem (First Theorem of Graph Theory):
If 𝐺 = (𝑉, 𝐸) be an undirected graph with 𝑒 edges, then
d(𝑣) = 2𝑒.
𝑣∈𝑉

(i.e. In any undirected graph, the sum of degrees of all the vertices is twice the
number of edges.)

Corollary: Undirected graph has an even number of vertices of odd degree.

Theorem: If 𝐺 = (𝑉, 𝐸) be a directed graph with 𝑒 edges, then

d+ 𝑣 = d− 𝑣 = 𝑒.
𝑣∈𝑉 𝑣∈𝑉

(i.e. In any undirected graph, the sum of the in degree of the vertices equals the
sum of out degree of vertices which equals the number of edges in 𝐺.)

26
Example: Is there a simple undirected graph corresponding to the following degree
sequences (1, 1, 2, 3)?
Solution:
We know that any undirected graph has even number of vertices of odd degree. But here
in given graph total number of vertices having odd degree is 3. Hence there exists no
such graph corresponding to this given degree sequence.

Example: How many edges does an undirected graph have if it degree sequence is 4,
3, 3, 2, 2?
Solution: Using the Handshaking theorem, we know that
𝑑 𝑣 = 2𝑒 ,
𝑣∈𝑉
where 𝑑 𝑣 is degree of a vertex 𝑣 and 𝑒 is the total number of edges.
⇒ 4 + 4 + 3 + 3 + 2 + 2 = 2𝑒
⇒ 14 = 2𝑒
⇒𝑒=7

Thus, 7 edges required to construct a graph having as degree sequence is 4, 3, 3, 2, 2.

27
Example: Determine the number of edges in an undirected graph with 6
nodes(vertices), two of degree 4 and four of degree 2.
Solution:
Using the Handshaking theorem, we know that
𝑑 𝑣 = 2𝑒 ,
𝑣∈𝑉
where 𝑑 𝑣 is degree of a vertex 𝑣 and 𝑒 is the total number of edges.

⇒ 4 + 4 + (2 + 2 + 2 + 2) = 2𝑒
⇒ 16 = 2𝑒
⇒𝑒=8

Thus, the number of edges in a graph with 6 nodes(vertices), two of degree 4 and
four of degree 2 is 8.

28
Example: A non-directed graph 𝑮 has 8 edges. Find the number of vertices if
the degree of each vertex is 2.
Solution:
Suppose that 𝐺 has 𝑛 vertices say 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , … , 𝑣𝑛 . Then 𝑑 𝑣𝑖 = 2 for each 𝑖.

Using the Handshaking theorem, we know that

𝑑 𝑣 = 2𝑒
𝑣∈𝑉
where 𝑑 𝑣 is degree of vertex 𝑣 and 𝑒 is the total number of edges.
𝑛

⇒ 2 = 2(8)
𝑖=1
⇒ 2𝑛 = 16
⇒𝑛=8
Therefore the number of required vertices is 8.
29
Example: Suppose 𝑮 is non-directed graph with 𝟏𝟐 edges. If it has 𝟔 vertices each of degree 𝟑 and

rest have Equal degree less than 𝟑. Find the minimum and maximum number of vertices 𝑮 can

have.
Solution: Let 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑛 be vertices having degree less than 3.
Using the Handshaking theorem, we know that
𝑑 𝑣 = 2𝑒
𝑣∈𝑉
where 𝑑 𝑣 is degree of vertex 𝑣 and 𝑒 is the total number of edges.

⇒ 6×3 + 𝑑(𝑣𝑖 ) = 2(12)

𝑖=1
𝑛

⇒ 𝑑(𝑣𝑖 ) = 6
𝑖=1
• If 𝑑 𝑣𝑖 = 2 for all 𝑖, then 2𝑛 = 6 ⇒ 𝑛 = 3. So total number of vertices = 6 + 3 = 9.
• If 𝑑 𝑣𝑖 = 1 for all 𝑖, then 𝑛 = 6. So total number of vertices 6 + 6 = 12.

Therefore 𝐺 can have 9 and 12 minimum and maximum number of vertices respectively.

30
Regular Graph: If all vertices are of same degree in a graph, then the graph is
said to be regular graph.
𝒓-Regular Graph: If every vertex has degree 𝑟, then graph is called regular
graph of degree 𝑟.

Remarks:
1. Every null graph is a regular graph of degree zero.
𝑛𝑟
2. If a graph has 𝑛 vertex and is regular of degree 𝑟, then it has edge.
2
3. All regular graphs need not to be complete but all complete graph are
regular.

31
Isomorphic Graph: Let 𝐺1 (𝑉1 , 𝐸1 ) and 𝐺2 (𝑉2 , 𝐸2 ) be two graph. These two
graphs are said to be isomorphic if there exist one-to-one correspondence
between their vertices as well as edges.

Remarks:
1) From definition, two isomorphic graphs must have equal number of vertices
with same degree.

Procedure:
1) Check no. of vertices and edges in both the graph are same or not.
2) Check the degree sequence of vertices.
3) Find one to one correspondence between vertex set and edge set of both
graph.

32
Example: Check whether the given graphs are isomorphic or not.

Solution: Here both 𝐺 and 𝐻 have 6 vertices and 7 edges.

Both have 4 vertices of degree 2 and 2 vertices of degree 3.
One to one correspondence of vertex set:
𝑢1 ↔ 𝑣6 , 𝑢2 ↔ 𝑣3 , 𝑢3 ↔ 𝑣4, 𝑢4 ↔ 𝑣5 , 𝑢5 ↔ 𝑣1, 𝑢6 ↔ 𝑣2
One to one correspondence of edge set:
𝑢1 , 𝑢2 ↔ 𝑣6 , 𝑣3 , 𝑢2 , 𝑢3 ↔ 𝑣3 , 𝑣4 , 𝑢3 , 𝑢4 ↔ 𝑣4 , 𝑣5 ,
𝑢4 , 𝑢5 ↔ 𝑣5 , 𝑣1 , 𝑢5 , 𝑢6 ↔ 𝑣1 , 𝑣2 , 𝑢6 , 𝑢2 ↔ 𝑣2 , 𝑣3 ,
𝑢1 , 𝑢4 ↔ 𝑣6 , 𝑣5
Since one to one correspondence exist between vertex as well as edge set of the given graph,
so the graphs 𝐺 and 𝐻 are isomorphic.
33
Example: Check whether the given graphs are isomorphic or not.

Solution:
The graphs 𝐺 and 𝐻 both have eight vertices and 10 edges.
They also both have 4 vertices of degree 2 and remaining 4 vertices of degree 3.
However, 𝐺 and 𝐻 are not isomorphic.
To see this,
• Note that 𝑑 𝑎 = 2. So 𝑎 must correspond to either 𝑡, 𝑢, 𝑥 or 𝑦 in 𝐻, as these are
the vertices of degree two in 𝐻.
• However, each of these four vertices in 𝐻 is adjacent to another vertex of degree
2 in 𝐻, which is not true for 𝑎 in 𝐺.
• So one to one correspondence between vertexes does not exist. Therefore the
graphs 𝐺 and 𝐻 are not isomorphic.
34
Example: Check whether the given graphs are isomorphic or not.
(H.W.)

35
Complement of a graph: If the edges that exist in simple graph-I are absent in another
simple graph-II, and if both graph-I and graph-II with same vertices are combined
together to form a complete graph, then graph-I and graph-II are called complements of
each other.
The Complement of graph of 𝐺 is denoted by 𝐺.

SELF COMPLEMENTARY GRAPH: A simple graph is said to be self complementary

if it is isomorphic to its own complement.

36
Remarks:
Let 𝐺 be a simple graph with 𝑛 vertices and 𝐺 be its complement.
• For each vertex 𝑣 in 𝐺, we have
𝑑𝐺 𝑣 + 𝑑𝐺 𝑣 = 𝑛 − 1.
• If 𝐺 has exactly one even vertex, then 𝐺 have 𝑛 − 1 odd vertices.

• The graph 𝐺 can be obtained from the complete graph 𝐾𝑛 by

rubbing out all the edges of 𝐺.
• Null graph generated from complete graph 𝐺 by removing edges is
a complement graph of 𝐺.

37
Example: Find the complement of the graph and also find
whether it is self complementary or not.

38
39
 Matrix Representation of Graph

A diagrammatic representation of a graph has limited usefulness; such

representation is only possible when the number of vertices and
number of edges are reasonably small. Also, their representation in
computer memory requires lot of storage space. So a matrix is a
convenient and useful way of representing a graph to a computer.

There are two different ways of representing a graph inside a

computer namely by using
• Adjacency Matrix
• Incidence Matrix

40
Adjacency Matrix for Undirected Graph:
Let 𝐺 be a graph with 𝑛 vertices listed as 𝑣1 , 𝑣2 ⋯ , 𝑣𝑛 . The adjacency matrix 𝐴(𝐺)
(or 𝐴𝐺 ) of 𝐺 with respect to this particular listing of vertices of 𝐺 is the 𝑛 × 𝑛
matrix
𝐴 𝐺 = 𝑎𝑖𝑗
𝑛×𝑛
where 𝑎𝑖𝑗 is the number of edges joining the vertex 𝑣𝑖 to 𝑣𝑗 .

REMARKS:
1. In 𝐴(𝐺), we have 𝑎𝑖𝑗 = 𝑎𝑗𝑖 for each 𝑖 and 𝑗 i.e., adjacency matrix for a graph is
symmetric.
2. If 𝐺 has no loops then all the entry of the main diagonal of 𝐴(𝐺) are zero.
3. For a simple graph, the entries of adjacency matrix are either zero or one.

41
Ex: Write the adjacency matrix for following graph:
R

Solution:
The required adjacency matrix is

42
Ex: Write the adjacency matrix for following graph:
R

Solution:
The required adjacency matrix is

43
Example: Determine the number of loops and multiple edges in a multi graph
G from its adjacency matrix:
1 1 3 0
1 2 1 3 
A G   
3 1 0 1
 
0 3 1 0
Solution:
Since adjacency matrix 𝐴 is a square matrix of order 4, graph 𝐺 has four vertices
𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 .
The diagonal of 𝐴 is indicating the vertices having loops because these entries
indicate the number of edges originating and terminating at the same vertex.
Thus, there are three loop: one at 𝑣1 and two at 𝑣2 .
Multi edges are 6.

44
Incidence Matrix for Undirected Graph:
Let 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑛 be the 𝑛 vertices of a graph 𝐺 and 𝑒1 , 𝑒2 ⋯ , 𝑒𝑚 be
the 𝑚 edges of 𝐺. Then the incidence matrix of 𝐺 w.r.t to this
particular listing of vertices and edges is 𝑛 × 𝑚 matrix (vertices ×
edges). The entries of a matrix can be derived by using
𝐼 𝐺 = 𝑚𝑖𝑗
0 if 𝑣𝑖 is not end point of 𝑒𝑗
where 𝑚𝑖𝑗 = .
1 if 𝑣𝑖 is end point of 𝑒𝑗
REMARKS:
1. The sum of the elements in the 𝑖𝑡ℎ - row of 𝐼(𝐺) gives the degree
of vertex 𝑣𝑖 . (𝑣𝑖 does not contain loop).
2. The sum of the elements in each column is 2.
45
Ex: Write the incidence matrix for following graph:
R

Solution:
The required incidence matrix is

46
Ex: Write the incidence matrix for following graph: R

Solution:
The required incidence matrix is

47
 MATRIX REPRESENTATION OF DIRECTED GRAPH

Adjacency Matrix for Directed Graph:

For a directed graph 𝐺 consists of 𝑛 vertices, an 𝑛 × 𝑛 adjacency matrix 𝐴 = 𝑎𝑖𝑗 is defined
as:
𝑚 if 𝑚 edges begining at 𝑣𝑖 and ending at 𝑣𝑗
𝑎𝑖𝑗 = .
0 otherwise

Incidence matrix for Directed Graph:

For a directed graph 𝐺 consists of 𝑛 vertices and 𝑚 edges, an 𝑛 × 𝑚 incidence matrix 𝑀 =
[𝑚𝑖𝑗 ] is defined as:

1 if 𝑣𝑖 is starting vertex of edge 𝑒𝑗

𝑚𝑖𝑗 = −1 if 𝑣𝑖 is ending vertex of edge 𝑒𝑗
0 if 𝑣𝑖 neither starting nor ending vertex of edge 𝑒𝑗

48
Ex: Write the adjacency and incidence matrix for following graph:
R

Solution:
The required adjacency and incidence matrix are

49
Ex: Write the incidence matrix for following graph:
R

Solution:
The required incidence matrix is

50
Ex: Write the adjacency and incidence matrix for following graph: R

Solution:
The required adjacency and incidence matrix are

51
Remarks:
(1) The Adjacency matrix of an Undirected graph is always Symmetric
matrix.
(2) The Adjacency matrix of a directed graph may or may not be
Symmetric matrix.

52
Subgraph: Let 𝐺 = 𝑉 𝐺 , 𝐸 𝐺 and 𝐻 = 𝑉 𝐻 , 𝐸 𝐻 be graphs. Then
𝐻 is said to be subgraph of 𝐺 if 𝑉 𝐻 ⊂ 𝑉(𝐺) and 𝐸 𝐻 ⊂ 𝐸(𝐺).
𝐺 is said to be super graph of 𝐻.
If 𝐻 is subgraph of 𝐺 then it is denoted by 𝐻 ⊂ 𝐺.

53
REMARKS:
(1) Every graph is its own sub graph.
(2) Any simple graph with 𝑛 vertices is a sub graph of the complete
graph 𝐾𝑛 .

Proper Subgraph: Let 𝐻 be a subgraph of 𝐺. If 𝑉 𝐻 ≠ 𝑉(𝐺) and

𝐸 𝐻 ≠ 𝐸(𝐺) then 𝐻 is said to be a proper subgraph of 𝐺.
It is denoted by 𝐻 ≠ 𝐺.

Spanning Subgraph:
A subgraph 𝐻 of graph 𝐺 is said to be a spanning subgraph of 𝐺 if
𝑉 𝐻 = 𝑉(𝐺) (i.e. 𝐻 contains all vertices of 𝐺).

54
Vertex Deleted Subgraph:
Definition 1:
Let 𝐺 = (𝑉, 𝐸) be a graph and 𝑉 has at least two elements. For any vertex 𝑣 of 𝐺,
𝐺 − 𝑣 denotes the sub graph of 𝐺 with vertex set 𝑉 ∖ {𝑣} and whose edges are all
those edges of 𝐺 which are not incident with vertex 𝑣. i.e., graph 𝐺 − 𝑣 is obtained
from graph 𝐺 by removing vertex 𝑣 and all the edges of 𝐺 connected to 𝑣. Graph
𝐺 − 𝑣 is said to be vertex deleted subgraph.

55
Definition 2:
Let 𝐺 = (𝑉, 𝐸) be the given graph and 𝑈 be a proper subset of 𝑉, then 𝐺 − 𝑈
denotes the sub graph of 𝐺 with vertex set 𝑉 ∖ 𝑈 and whose edges are all those of 𝐺
which are not incident with any vertex of 𝑈.
For example,

56
Edge deleted subgraph:
Definition 1:
Let 𝐺 = (𝑉, 𝐸) be the given graph and 𝑒 be the edge of 𝐺 then 𝐺 − 𝑒 denotes the
subgraph of 𝐺 having 𝑉 as its vertex set and 𝐸 − {𝑒} as it edge set.
i.e. 𝐺 − 𝑒 is obtained from 𝐺 by removing edge 𝑒 (but not the end point of 𝒆).
𝐺 − 𝑒 is said to be edge deleted sub graph of 𝐺.

57
58
Definition 2:
Let 𝐺 = (𝑉, 𝐸) be the given graph. 𝐹 be a subset of edge set 𝐸. 𝐺 − 𝐹 denoted the
sub graph of 𝐺 with vertex set 𝑉 and edge set 𝐸 ∖ 𝐹 i.e. 𝐺 − 𝐹 is obtained by
deleting all the edges in 𝐹 but not their end point. 𝐺 − 𝐹 is also said to be edge
deleted sub graph of 𝐺.

59
WALK:
A walk in a graph is a finite alternating sequence of vertices and edges beginning
and ending with vertices such that each edge is incident with vertices preceding and
following it.

Remarks: For a walk 𝑊 = 𝑣0 𝑒1 𝑣1 𝑒2 𝑣2 𝑒3 𝑣3 ⋯ 𝑣𝑘−1 𝑒𝑘 𝑣𝑘 ,

1. The above walk is said to be 𝑣0 − 𝑣𝑘 walk or walk from 𝑣0 to 𝑣𝑘 .
2. The number of edges in the walk 𝑊 is said to be length of walk.
3. In a walk, there may be repetition of vertices and edges.
4. The vertex 𝑣0 is said to be origin of the walk 𝑊 and vertex 𝑣𝑘 is said to be end
of the walk.
5. For a walk 𝑊, 𝑣0 and 𝑣𝑘 need not be distinct. (i.e. origin and end need not be
distinct.)
6. Vertices 𝑣1 , 𝑣2 , 𝑣3 ⋯ 𝑣𝑘−1 are said to be internal vertices for the walk 𝑊.
7. In a simple graph, a walk 𝑊 = 𝑣0 𝑒1 𝑣1 𝑒2 𝑣2 𝑒3 𝑣3 ⋯ 𝑣𝑘−1 𝑒𝑘 𝑣𝑘 is determined by
sequence 𝑊 = 𝑣0 𝑣1 𝑣2 𝑣3 ⋯ 𝑣𝑘−1 𝑣𝑘 of vertices because for each pair 𝑣𝑖 𝑣𝑖−1
there is only one possible edge.

60
Open walk:
A walk is said to be an open walk if the starting and ending vertices
are different.
Closed walk:
A walk is said to be a closed walk if the starting and ending vertices
are same.

In the above diagram,

 𝑊 = 1𝑎2𝑑3𝑒4𝑔5𝑓3 is an open walk. Length of 𝑊 is 5.
 𝑊 = 1𝑎2𝑑3𝑒4𝑔5𝑓3𝑐1 is a closed walk. Length of 𝑊 is 6.
61
TRIVIAL WALK:
A walk containing no edge is said to be trivial walk.
For an vertex 𝑣, 𝑊 = 𝑣 is said to be trivial walk.
Length of trivial walk is zero.
In this graph, 𝑊 = 1 is a trivial walk.

TRAIL:
A trail is a walk in which no edges are repeated.
In this graph, the walk W=1a2d3e4g5 is a trail.

REMARK:
• Every trail is a walk but every walk is not a trail.
In this graph, 1a2d3c1a2 is a walk but not trail.

62
PATH:
A path is a walk in which no vertex is repeated.

The walk 1a2d3e4g5 is a path.

REMARKS:
• A path with 𝑛 vertices is denoted by 𝑃𝑛 and has length is 𝑛 − 1.
• Every path is a walk but each walk is not a path.
• A loop can be included in walk but not in a path.

63
Cycle or Circuit:
A cycle in a graph is a non-empty trail in which the only repeated
vertices are first and last vertices.
K-CYCLE:
A cycle with 𝑘 edges are said to be 𝑘-cycle.
It is denoted by 𝐶𝑛 .
e.g. W=3c1a2d3 is a 3-cycle and its length is 3.

Remarks:
• If 𝑘 is odd then 𝑘-cycle is said to be an odd and
if 𝑘 is even then 𝑘-cycle is said to be even.
• A loop is just a 1-cycle.
64
 Connectedness in Undirected Graph

Connected Vertex:
A vertex 𝑢 is said to be connected to vertex 𝑣 in a graph 𝐺 if there is a
path in 𝐺 from 𝑢 to 𝑣.

Note:
• An vertex 𝑢 is connected to itself by trivial path 𝑃 = 𝑢.
• If 𝑢 is connected to 𝑣 and 𝑣 is connected to 𝑤, then 𝑢 is connected
to 𝑤.

Connected and disconnected graph:

A graph 𝐺 is said to be connected if there is at least one path between
every pair of vertices of 𝐺 otherwise graph 𝐺 is said to be
disconnected.
65
Note:
Every disconnected graph can be split into number of connected
subgraphs, called connected components.

66
 Connectedness in Directed Graph
We cannot use the same criteria to determine the connectivity of
a directed graph as that for an undirected graph.

Weakly connected graph:

A directed graph is weakly connected if there is a path between
every two vertices in the corresponding undirected graph.

67
Strongly Connected:
A directed graph is called strongly connected if for any pair of
vertices 𝑢 and 𝑣, there exist a path from 𝑢 to 𝑣 as well as 𝑣 to
𝑢.

68
Unilaterally connected: A directed graph is called unilaterally connected
if given any two vertices of the graph there exist a path from one vertex to
another although a reverse path does not necessarily exist.

(Here 𝑣1 to 𝑣3 path exists but 𝑣3 to 𝑣1 path does not exist.)

REMARKS:
1. Every strongly connected graph is unilaterally connected but converse is
not true.
2. Every strongly connected graph is weakly connected but converse is not
true.

69
 .

Cut vertex (Articulation point): Let 𝐺 be a connected graph.

A cut vertex 𝑣 is a vertex whose removal from 𝐺 results in a
disconnected graph.

Remarks: Not all graph have cut vertices. For example, the complete
graph 𝐾𝑛 , 𝑛 ≥ 3 has no cut vertices.

70
 .
Vertex Connectivity:
Let 𝐺 be a connected graph. The minimum number of vertices that must
be removed from 𝐺 leaves either a disconnected graph or complete
graph with one vertex is said to be vertex connectivity of 𝐺.
It is denoted by 𝜅 𝐺 .

The graph 𝐺 given in the above figure has no cut vertex.

But a disconnected subgraph is obtained when two of these vertices 2

and 6 or 2 and 5 are deleted. Therefore 𝜅 𝐺 =2.

71
REMARKS:
1. For 𝑛 ≥ 2, the deletion of any vertex from 𝐾𝑛 result in
𝐾𝑛−1 . So 𝜅 𝐺 = 𝑛 − 1.

2. A connected graph 𝐺 has 𝜅 𝐺 = 1 iff 𝐺 = 𝐾2 or 𝐺 has a

cut vertex.

3. 𝜅 𝐺 = 0 iff 𝐺 = 𝐾1 or 𝐺 is disconnected.

72
Cut Edge or Bridge or Isthmus:
A cut edge is an edge whose removal increases number of connected
components of given graph. (i.e., removal of an edge in a graph results
in two or more subgraphs.)

Remark: It is not necessary that all the graph have cut edge.

Edge connectivity:
Let 𝐺 be a connected graph. The minimum number of edges must be
removed from 𝐺 leaves either a disconnected graph or complete graph
with one vertex is said to be edge connectivity of 𝐺.
It is denoted by 𝜆(𝐺).

Remarks:
(1) If 𝐺 is disconnected graph then 𝜅 𝐺 = 0 and 𝜆 𝐺 = 0.
(2) If 𝐺 is any graph, then 𝜅 𝐺 ≤ 𝜆(𝐺).
73
Example : Find the cut vertices , cut edges, vertex
connectivity and edge connectivity in the following
graph:

Solution: For 𝐺1 and 𝐺2 ,

• Cut Vertices of 𝑮𝟏 : 𝑏, 𝑐, 𝑒 and Cut Vertices of 𝑮𝟐 : 𝑐
• Cut Edges of 𝑮𝟏 : (𝑐, 𝑒), (𝑎, 𝑏) and Cut Edges of 𝑮𝟐 : Nil
• 𝜅(𝐺1 ) = 1 and 𝜅(𝐺2 ) = 1
• 𝜆(𝐺1 ) = 1 and 𝜆(𝐺2 ) = 2
74
Planar Graph: A graph is said to be planar if there exists some
geometric representation of 𝐺 which can be drawn on a plane
such that no two of its edges crossovers to each other.

75
Region of a planar graph: A region of a planar graph is
defined to be an area of the plane that is bounded by edges and is
not further divided into subareas.
Note: we also include the outside area of a graph as region.

Euler’s Formula:
If a connected planar graph 𝐺 has 𝑛 vertices, 𝑒 edges and 𝑟
number of regions, then 𝑛 − 𝑒 + 𝑟 = 2.
76
Examples:

77
Result-𝟏: If a planar graph has 𝑘 number of connected
components, then 𝑛 − 𝑒 + 𝑟 = 𝑘 + 1.

Result-𝟐: If 𝐺 is connected simple planar graph with

𝑛 vertices 𝑛 ≥ 3 and e edges, then 𝑒 ≤ 3𝑛 − 6.

Result-𝟑: If 𝐺 is connected simple planar graph with 𝑛

vertices and 𝑒 edges then 𝑒 ≤ 2𝑛 − 4.

78
Example: A connected planar graph has 10 vertices each of
degree 3. Into how many regions does a representation of this
planar graph split the plane?
Solution:
Here 𝑛 = 10 and degree of each vertex is 3.
So using Handshaking theorem, the sum of degrees of all the
vertices will be 30 and hence number of edges in a graph is 15.

Using Euler’s formula,

𝑛−𝑒+𝑟 =2
⇒ 10 − 15 + 𝑟 = 2
⇒𝑟=7

79
 EULERIAN AND HAMILTONIAN GRAPH

Eulerian Path (Eulerian Trail): An Eulerian path is a trail in a

finite graph that visits every edge exactly once (repetition of
vertices is allowed).

Note: Path in title is a word and it is not a definition of a Path.

Eulerian Cycle (Eulerian Circuit): Eulerian cycle is an Eulerian

path that starts and ends on the same vertex.

Eulerian Graph: Eulerian graph is a graph which contains at

least one Eulerian cycle.

80
Examples:

81
Exercise: Check that Euler circuits and paths exit or not if
yes then find. Also, state whether it is Euler graph or not.

82
Theorem-1: An undirected graph is an Eulerian graph if and only if all the
vertices are even.

Theorem-2: A directed graph is an Eulerian graph if and only if in degree

and out degree of for all the vertices are same.

Hamiltonian Path: Hamiltonian path in a graph is a path which passes

through all the vertices of a graph exactly once. (Repetition of edges is not
allowed)

Hamiltonian Circuit (Hamiltonian Cycle): Hamiltonian circuit in a graph

is a circuit which passes through all the vertices of a graph exactly once and
starting and ending vertex must be same. (Repetition of edges is not
allowed)

Hamiltonian Graph: Hamiltonian graph is a graph which contains at least

one Hamiltonian circuit.
83
EXAMPLE: The following graph contains Hamiltonian path
and circuit.

Path : - A F B C G D E ;
Circuit :- A F B C G D E A

84
Exercise: Check that Hamiltonian circuits and paths exit or
not if yes then find.

85
Exercise: Check that Euler path, Euler circuit,
Hamiltonian path and Hamiltonian circuit exist or not.

86
 MATCHING IN A GRAPH
Matching Graph: Let 𝐺 be a graph. A matching graph 𝑀 is a subgraph of a
graph 𝐺 where there are no edges adjacent to each other.
i.e. there should not be any common vertex between any two edges.

Remarks:
• As each vertex of 𝐺 is incident with at most one edge in matching graph 𝑀,
So the vertices of 𝑀 should have a degree of 1 or 0.
• Null graph as a sub graph of 𝐺 is always matching graph of 𝐺.

Example: Find the Matching graph of following graph.

87
Solution:

88
Maximal Matching: A matching 𝑀 of graph 𝐺 is said to
maximal if no other edges of 𝐺 can be added to 𝑀.

Maximum Matching (Largest Matching): Maximum

matching is defined as the maximal matching with
maximum number of edges.

The number of edges in the maximum matching of 𝐺 is

called its matching number.

Perfect Matching: A matching 𝑀 of graph 𝐺 is said to be a

perfect match if deg 𝑣 = 1, for every vertex 𝑣 of 𝑀.
89
Example: Find the Maximal Matching graph of following
graph.

Solution: Here 𝑀1 , 𝑀2 and 𝑀3 from the above graph are the

maximal matching of 𝐺.

90
Example: Find the matching number of following graph.

Solution:

Note that 𝑀1 and 𝑀2 are the maximum matching of 𝐺 having

maximum edges 2. Hence matching number of 𝐺 is 2.

Since degree of each vertex is 1. Therefore it is a perfect matching.

91
 Graph coloring

Graph coloring: A graph coloring is an assignment of labels or

colors, to the vertices of a graph such that no two adjacent vertices
share the same color.

The chromatic number χ(G) of a graph 𝐺 is the smallest

number of colors for which such an assignment is possible.

92
 E

93
Remarks:
1) The chromatic number of 𝐾𝑛 is 𝑛 because each vertex is adjacent to
remaining 𝑛 − 1 vertices.
2) The chromatic number of Null graph with 𝑛 vertices is 1.
3) The chromatic number of trivial graph is 1.

Edge coloring: Each edge of a graph has a color assigned to it in

such a way that no two adjacent edges are of the same color. Such
a coloring is a edge coloring.

The smallest number of colors for the edge coloring of a given

graph is called the chromatic index of the graph.

94
The chromatic index is 4.

The chromatic index is 3.

95
 APPLICATION OF GRAPH THEORY IN DIFFERENT FIELDS
The ideas and concepts of Graph theory are widely used in various
branches of science. In general, without knowing the concepts of
graph we also use these in our day to day life.
For example when we have to go to a place which is connecting with
our starting point by different ways then we use the shortest road to
arrive the destination soon. Here if we observe this problem from the
point of view of graph theory the two places can be considered as
vertices and roads are as edges. If we also consider the direction of
travel, then the graph must be directed. Similarly, we can use these
concepts of graph theory in various situations.
A graph can be used to present almost any physical situation involving
discrete and relationship among them.

96
Here the applications of graph theory in various branches of science are mention
below.
Graph Node or Vertices Edges or Arcs
Communication Telephone, Computer Fibber Optic Cable
Internet Class C Network Connection
Circuit Gate, Register, Processor Wire
Transportation Street Intersection, Highway, Airway Route
Airport
Social Relation Person Friendship

APPLICATIONS IN GOOGLE MAP

Now a days, Google map is a very useful tool for travelling anywhere in the
world. Using Google map we can find all routes from any place to any other
place and also can find the shortest route. In case of Google map, we can
consider the places as vertices of graph and the routes as the edges. Then the
software of google map, when find the routes between two places it find all
edges between these two places or vertices and also gives the shortest edge as
the shortest path.
97
APPLICATION IN INTERNET
Internet is a very useful invention of modern science. In the working
technique of internet the concepts of graph theory are used. In case of
connectivity of internet, all the users are considered as vertices and the
connection between them are edges. Then all internet users form a
very complicated graph and data and information from one user to
another user are shared through the shortest route in between them.
Similarly, in case of social networking sites one friend is connected to
all of his friend and his friends are also connected to others.
If we consider the friends as vertices of graph and define an edge in
between them if they are friend then it will be a graph. While using
Google to search for Webpages, Pages are linked to each other by
hyperlinks. Each page is a vertex and the link between two pages is an
edge.
98
APPLICATION IN COMPUTER SCIENCE
There is a major role of graph theory in computer science. Graph theory concepts
are used to develop the algorithm of different programs.
Using these algorithms and programmes we can solve different theoretical problems.
There are some algorithms listed below.
1. Shortest path algorithm in a network.
2. Finding 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 etc.

TO CLEAR ROAD BLOCKAGE:

When roads of a city are blocked due to ice. Planning is needed to put salt on the
roads. Then Euler paths or circuits are used to traverse the streets in the most
efficient way.
99
There are many computer languages which helps to solve different problems
using graph theory concepts.

Some computer languages available are listed as follows:

1. GTPL - Graph Theoretic Language

2. GASP - Graph Algorithm Software Package.
3. HINT - Extension of LISP.
4. GRASPE - Another extension of LISP.
5. DIP - Directed Graph Processor.
6. An Interactive Graph Theory System- Extension of FORTRAN.
7. GEA - Graphic Extended ALGOL.
8. GIRL - Graph Information Retrieval Language.
9. FGRAAL - FORTRAN Extended Graph Algorithmic Language.

100