Unit 4 – Graph Theory - I

Index

Unit – 4 ⇝ Graph Theory – I (E-Notes) ............................................................. 3

1) Method 1 ⇝ Basic Terminologies .......................................................................................... 3

2) Method 2 ⇝ First and Second Theorem of Graph Theory .................................................. 12
3) Method 3 ⇝ Special Types of a Graph ................................................................................ 18
4) Method 4 ⇝ Graph Isomorphism ........................................................................................ 27
5) Method 5 ⇝ Connectivity .................................................................................................... 31
6) Method 6 ⇝ Matrix Representation of a Graph.................................................................. 40
7) Method 7 ⇝ Warshall’s Algorithm ...................................................................................... 46

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 1
Unit 4 – Graph Theory - I

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 2
Unit 4 – Graph Theory - I

Unit – 4 ⇝ Graph Theory – I (E-Notes)

Method 1 ⇝ Basic Terminologies

Introduction
→ Graph theory in discrete mathematics a branch of mathematics that deals with the
study of graphs, which are mathematical structures used to represent relationships
between objects.

→ The applications of the linear graph are used not only in Mathematics but also in other
fields such as Computer Science, Social Sciences, Biology, Transportation, Cyber
Security, Finance, etc.

• Computer Networks: Routing, Data Transfer, Network Technology

• Social Networks: Modelling relationships and influence

• Search Engines: Page Rank algorithm is based on graphs

• Biology: Gene sequencing and protein interaction networks

• Operation Research: Project planning using PERT and CPM

• Artificial Intelligence: State-space search trees in problem-solving

• Transportation: GPS navigation, traffic optimization

Problem Graph Theory Concept Benefit

Finding Best Data

Shortest Path Algorithms Faster Data Transfer
Routes
Lower Cost, Better
Network Design Spanning Trees
Efficiency

Load Balancing Flow Networks Avoid Congestion

Fault Tolerance Connectivity Analysis High Reliability

Wireless
Graph Coloring Minimized Interference
Communication

→ In real – life, the best example of graph structure is GPS, where you can track the path
or know the direction of the road.

→ Graph theory continues to play a crucial role in advancing our understanding of

complex systems and optimizing processes in our interconnected world.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 3
Unit 4 – Graph Theory - I

Basic Terminologies
(1) Graph

→ A graph G = (V, E) consists of a non – empty set V = { v1 , v2 , v3 , … } of vertices and a

set E = { e1 , e2 , e3 , … } of edges such that each edge is incident to an
ordered/unordered pair (vi , vj ) of vertices.

→ Example:

(2) Vertex

→ A vertex (plural vertices) is represented by circle or dot.

→ The set of vertices of a graph G is denoted as V or V(G).

→ Vertex is known as Node, Point, Dot or Junction.

→ Example:

• Vertex Set V = {v1 , v2 , v3 , v4 }

(3) Edge

→ An edge is represented by line or arc.

→ The set of edges of a graph G is denoted as E or E(G).

→ E(G) = { e = (u, v) | u, v ∈ V(G) }

→ Edge is known as Branch, Line or Arc.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 4
Unit 4 – Graph Theory - I

→ Example:

• Edge Set V = {e1 , e2 , e3 , e4 , e5 }

→ Any edge e can be made by one or two vertices.

• Example:

𝐞 = (u, u) 𝐞 = (u, v)
or unordered pair
𝐞 = (v, u)

(4) Self – Loop

→ An edge e of a graph G that joins a vertex u to itself is called a Self - Loop.

→ Self – Loop is also known as Loop or Sling.

→ Example:

i.e., a self – loop is an edge e = (u, u).

(5) Adjacent Vertices

→ If two vertices u and v are joined by an edge e, then u and v are said to be adjacent
vertices.

(6) Incident Edge

→ If an edge e from the edge set joins the vertices u and v, then the edge e is said to be
incident to the vertices u and v.

→ The vertices u and v are the end points of an edge e.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 5
Unit 4 – Graph Theory - I

Remark

→ In drawing a graph, it is immaterial whether the edges or lines are drawn straight or
curved, long or short, what is important is the incidence between edges and vertices
are the same in both cases.

(7) Parallel Edges

→ If two vertices of a graph are joined by more than one edge then these edges are called
parallel edges or multiple edges.

→ Example:

• Here e1 , e2 and e3 are parallel edges.

(8) Isolated Vertex

→ In a graph, a vertex which is not adjacent/associated to any other vertex is known as

isolated vertex.

→ Example:

• Here, vertex v4 and v5 are isolated vertices.

(9) Null Graph

→ A graph without edges is known as null graph.

→ Also, a graph which contains only isolated vertices is known as null graph.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 6
Unit 4 – Graph Theory - I

→ Example:

(10) Directed Edge

→ In a graph G an edge e which is associated with an ordered pair of vertices u to v is

called directed edge of a graph G.

→ Directed edge from vertex u to v is denoted as 〈u, v〉.

→ Example:

• Edge 𝐞 = 〈u, v〉 is a directed edge.

→ Suppose e = 〈u, v〉 is a directed edge, then

• vertex u is known as the initial vertex and vertex v is known as the terminal
vertex of e.

• 𝐞 is said to be incident from u to v.

(11) Directed Graph

→ A graph in which every edge is directed edge is known as Directed Graph or Digraph.

→ A digraph is denoted as G = 〈 V, E 〉; where V = Vertex Set and E = Edge Set.

→ Example:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 7
Unit 4 – Graph Theory - I

(12) Undirected Edge

→ In a graph G, an edge e which is associated with an unordered pair of vertices u to v

is called an undirected edge of a graph G.

→ Undirected edge from vertex u to v is denoted as (u, v).

→ Example:

• Edge e = (u, v) is an undirected edge.

(13) Undirected Graph

→ A graph in which every edge is undirected edge is known as undirected graph.

→ An undirected graph is denoted as G = (V, E); where V = Vertex Set and E = Edge Set

→ Example:

(14) Mixed Graph

→ If some edges of a graph G are directed and some edges are undirected, then G is
known as a mixed graph.

→ Example:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 8
Unit 4 – Graph Theory - I

(15) Distinct Edge

→ In a directed graph, the two possible edges between a pair of vertices which are
opposite in direction are known as distinct edges.

→ Example:

• Here, edge 𝐞𝟏 and 𝐞𝟑 , 𝐞𝟐 and 𝐞𝟑 are distinct edges.

• Edge 𝐞𝟏 and 𝐞𝟐 , are not distinct edges as they are in same direction.

Remark

→ In a directed graph, more than one directed edge in a particular direction is

considered as parallel edge.

→ Example:

• Edge 𝐞𝟏 and 𝐞𝟐 are parallel edges as they are in same direction.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 9
Unit 4 – Graph Theory - I

Examples of Method-1: Basic Terminologies

C 1 Determine the vertex set, edge set and incidence relation of the following
graph G:

𝐀𝐧𝐬𝐰𝐞𝐫: 𝐕𝐞𝐫𝐭𝐞𝐱 𝐒𝐞𝐭 𝐕 = { 𝐯𝟏 , 𝐯𝟐 , 𝐯𝟑 , 𝐯𝟒 , 𝐯𝟓 , 𝐯𝟔 , 𝐯𝟕 , 𝐯𝟖 , 𝐯𝟗 },

𝐄𝐝𝐠𝐞 𝐒𝐞𝐭 𝐄 = { 𝐞𝟏 , 𝐞𝟐 , 𝐞𝟑 , 𝐞𝟒 , 𝐞𝟓 , 𝐞𝟔 , 𝐞𝟕 , 𝐞𝟖 , 𝐞𝟗 },

𝐈𝐧𝐜𝐢𝐝𝐞𝐧𝐜𝐞 𝐑𝐞𝐥𝐚𝐭𝐢𝐨𝐧 ⇝ 𝐞𝟏 = (𝐯𝟏 , 𝐯𝟏 ), 𝐞𝟐 = (𝐯𝟏 , 𝐯𝟐 ), 𝐞𝟑 = (𝐯𝟐 , 𝐯𝟒 ),

𝐞𝟒 = (𝐯𝟏 , 𝐯𝟒 ), 𝐞𝟓 = (𝐯𝟐 , 𝐯𝟑 ), 𝐞𝟔 = (𝐯𝟒 , 𝐯𝟓 ), 𝐞𝟕 = (𝐯𝟓 , 𝐯𝟔 ), 𝐞𝟖 = (𝐯𝟒 , 𝐯𝟗 ),

𝐞𝟗 = (𝐯𝟏 , 𝐯𝟒 ), 𝐞𝟏𝟎 = (𝐯𝟏 , 𝐯𝟒 )

C 2 Draw the undirected graph G = (V, E), where V = {a, b, c, d, e} and
E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 } and its incidence relations given as: e1 = (a, b),
e2 = (a, b), e3 = (b, c), e4 = (c, d), e5 = (b, b), e6 = (a, d) & e7 = (e, d).
Determine self – loop, parallel edges, one pair of adjacent and non – adjacent
vertices, isolated vertex.

𝐀𝐧𝐬𝐰𝐞𝐫:

(𝟏) 𝐞𝐝𝐠𝐞 𝐞𝟓 𝐢𝐬 𝐬𝐞𝐥𝐟 − 𝐥𝐨𝐨𝐩, (𝟐) 𝐞𝟏 𝐚𝐧𝐝 𝐞𝟐 𝐚𝐫𝐞 𝐩𝐚𝐫𝐚𝐥𝐥𝐞𝐥 𝐞𝐝𝐠𝐞𝐬,

(𝟑) 𝐕𝐞𝐫𝐭𝐢𝐜𝐞𝐬 𝐞 𝐚𝐧𝐝 𝐝 𝐚𝐫𝐞 𝐚𝐝𝐣𝐚𝐜𝐞𝐧𝐭, 𝐰𝐡𝐢𝐥𝐞 𝐞 𝐚𝐧𝐝 𝐜 𝐚𝐫𝐞 𝐧𝐨𝐧 − 𝐚𝐝𝐣𝐚𝐜𝐞𝐧𝐭,

(𝟒) 𝐓𝐡𝐞𝐫𝐞 𝐚𝐫𝐞 𝐧𝐨 𝐢𝐬𝐨𝐥𝐚𝐭𝐞𝐝 𝐯𝐞𝐫𝐭𝐢𝐜𝐞𝐬.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 10
Unit 4 – Graph Theory - I

C 3 Draw the directed graph G = (V, E), where V = {a, b, c, d, e, f, g} and

E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 } and its incidence relation given as:
e1 = < b, a >, e2 = < d, a >, e3 = < b, c >, e4 = < d, c >, e5 = < c, f >,
e6 = < f, f >, e7 = < e, c > & e8 = < c, e >.
Determine self – loop, parallel edges, one pair of adjacent and non – adjacent
vertices, isolated vertex.

𝐀𝐧𝐬𝐰𝐞𝐫:

(𝟏) 𝐞𝐝𝐠𝐞 𝐞𝟔 𝐢𝐬 𝐬𝐞𝐥𝐟 − 𝐥𝐨𝐨𝐩, (𝟐) 𝐓𝐡𝐞𝐫𝐞 𝐚𝐫𝐞 𝐧𝐨 𝐩𝐚𝐫𝐚𝐥𝐥𝐞𝐥 𝐞𝐝𝐠𝐞𝐬,

(𝟑) 𝐕𝐞𝐫𝐭𝐢𝐜𝐞𝐬 𝐛 𝐚𝐧𝐝 𝐜 𝐚𝐫𝐞 𝐚𝐝𝐣𝐚𝐜𝐞𝐧𝐭, 𝐰𝐡𝐢𝐥𝐞 𝐛 𝐚𝐧𝐝 𝐟 𝐚𝐫𝐞 𝐧𝐨𝐧 − 𝐚𝐝𝐣𝐚𝐜𝐞𝐧𝐭,

(𝟒) 𝐕𝐞𝐫𝐭𝐞𝐱 𝐠 𝐢𝐬 𝐢𝐬𝐨𝐥𝐚𝐭𝐞𝐝.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 11
Unit 4 – Graph Theory - I

Method 2 ⇝ First and Second Theorem of Graph Theory

(1) Order of a Graph

→ The number of vertices in a graph G is called order of a graph G.

→ The order of a graph G with the vertex set V is denoted as |V(G)|.

→ Example:

• Here, |V(G)| = 9

(2) Size of a Graph

→ The number of edges in a graph G is called size of a graph G.

→ The size of a graph G with the edge set E is denoted as |E(G)|.

→ Example:

• Here, |E(G)| = 10

(3) Degree of a Vertex

→ Let G be an undirected graph then, the degree of a vertex v ∈ G is defined as the

number of edges incident on v.

→ The degree of a vertex v ∈ G is denoted by d(v) OR dG (v) OR deg(v).

→ Note that, self - loop will be counted twice in the degree of a corresponding vertex.

(4) Odd Vertex

→ A vertex with odd degree is known as odd vertex.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 12
Unit 4 – Graph Theory - I

(5) Even Vertex

→ A vertex with even degree is known as even vertex.

(6) Isolated Vertex

→ A vertex with degree zero is known as isolated vertex.

(7) Pendent Vertex

→ A vertex with degree one is known as pendent vertex.

→ Example:

• d(v1 ) = 4, d(v2 ) = 3, d(v3 ) = 1, d(v4 ) = 6, d(v5 ) = 2, d(v6 ) = 1, d(v7 ) = 0,

d(v8 ) = 0, d(v9 ) = 3

• In above graph, odd vertices ⇝ v2 , v3 , v6 , v9 , even vertices ⇝ v1 , v4 , v5 , v7 , v8

isolated vertices ⇝ v7 , v8 , pendent vertices ⇝ v3 , v6

First Theorem of Graph Theory

→ Statement:

• Any graph G with ‘n’ vertices v1 , v2 , … , vn and ‘e’ edges,

n

∑ d(vi ) = d(v1 ) + d(v2 ) + ⋯ + d(vn ) = 2e

i=1

→ i.e., the sum of degree of all the vertices is twice the number of edges.

→ i.e., the sum of degree of all the vertices is even.

→ This theorem is also known as Handshaking Theorem or Degree Sum Formula.

Second Theorem of Graph theory

→ Statement:

• In any undirected graph G, the number of odd vertices is even.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 13
Unit 4 – Graph Theory - I

→ Example:

• Graph G has 4(even) odd vertices, namely v2 , v3 , v6 and v9 .

(8) Out – Degree of a Vertex

→ In a directed graph, the number of edges directed outwards vertex is called out –
degree of the vertex.

→ Let G be a directed graph, then for any vertex u ∈ G, the number of edges which have
u as their initial vertex is called the out – degree of the vertex u.

→ The out – degree of the vertex u is denoted by d+ (u).

(9) In – Degree of a vertex

→ In a directed graph, the number of edges directed towards vertex is called in – degree
of the vertex.

→ Let G be a directed graph, then for any vertex u ∈ G, the number of edges which have
u as their terminal vertex is called the in – degree of the vertex u.

→ The in – degree of the vertex u is denoted by d− (u).

(10) Total Degree of a vertex

→ Let G be a directed graph, then the sum of indegree and outdegree of vertex is called
the total degree of the vertex.

→ The total degree of the vertex u is denoted by d(u).

→ d(u) = d+ (u) + d− (u)

Remark

→ The in – degree and out – degree of an isolated vertex is 0.

Thus, the total degree of an isolated vertex is always 0.

→ A self – loop at a vertex contributes 1 to both the in – degree and out – degree of that
vertex.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 14
Unit 4 – Graph Theory - I

Degree Sum Formula for a Directed Graph

→ Statement:

→ In a directed graph G = 〈 V, E 〉 with ‘n’ vertices v1 , v2 , … , vn and ‘e’ edges,

n n n

∑ d+ (vi ) =∑ d− (vi ) = e and ∑ d(vi ) = 2e.

i=1 i=1 i=1

→ i.e., the sum of in – degrees of all the vertices of a digraph is equal to sum of out –
degrees of all its vertices which is equal to the number of edges of the graph.

Examples of Method-2: First and Second Theorem of Graph Theory

C 1 Verify Handshaking theorem for the following graph G:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 15
Unit 4 – Graph Theory - I

C 2 Find out – degree, in – degree and total degree of all the vertices of following
graph G:

𝐀𝐧𝐬𝐰𝐞𝐫:

In – degree Out – degree Total degree

𝐝− (𝐯𝟏 ) = 𝟐 𝐝+ (𝐯𝟏 ) = 𝟏 𝐝(𝐯𝟏 ) = 𝟑

𝐝− (𝐯𝟐 ) = 𝟏 𝐝+ (𝐯𝟐 ) = 𝟐 𝐝(𝐯𝟐 ) = 𝟑

𝐝− (𝐯𝟑 ) = 𝟐 𝐝+ (𝐯𝟑 ) = 𝟐 𝐝(𝐯𝟑 ) = 𝟒

𝐝− (𝐯𝟒 ) = 𝟐 𝐝+ (𝐯𝟒 ) = 𝟐 𝐝(𝐯𝟒 ) = 𝟒

C 3 Verify degree sum formula for the following directed graph G:

C 4 Find the number of vertices in an undirected graph G = (V, E) with 27 edges

in which 6 vertices of degree 2, 3 vertices of degree 4 and remaining vertices
of degree 3.

𝐀𝐧𝐬𝐰𝐞𝐫: 𝟏𝟗

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 16
Unit 4 – Graph Theory - I

C 5 Either draw a graph with specified properties or explain why no such graph
exists.
a) graph with four vertices of degrees 1, 2, 3 and 3
b) graph with five vertices of degrees 1, 2, 3, 3 and 5

𝐀𝐧𝐬𝐰𝐞𝐫: 𝐚) 𝐈𝐭 𝐢𝐬 𝐧𝐨𝐭 𝐩𝐨𝐬𝐬𝐢𝐛𝐥𝐞 𝐭𝐨 𝐝𝐫𝐚𝐰 𝐬𝐮𝐜𝐡 𝐠𝐫𝐚𝐩𝐡 𝐚𝐬 𝐢𝐧 𝐠𝐢𝐯𝐞𝐧 𝐝𝐚𝐭𝐚 𝐚𝐬

𝐧𝐮𝐦𝐛𝐞𝐫 𝐨𝐟 𝐨𝐝𝐝 𝐯𝐞𝐫𝐭𝐢𝐜𝐞𝐬 𝐚𝐫𝐞 𝟑 𝐚𝐧𝐝 𝐧𝐮𝐦𝐛𝐞𝐫 𝐨𝐟 𝐨𝐝𝐝 𝐯𝐞𝐫𝐭𝐢𝐜𝐞𝐬

𝐦𝐮𝐬𝐭 𝐛𝐞 𝐞𝐯𝐞𝐧.

𝐛)

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 17
Unit 4 – Graph Theory - I

Method 3 ⇝ Special Types of a Graph

(1) Undirected Multigraph

→ An undirected graph which contains some parallel edges and does not contain self –
loop is known as undirected multigraph.

→ Example:

(2) Directed Multigraph

→ A directed graph which contains parallel edges and self – loop is known as directed
multigraph.

→ Example:

(3) Simple Graph

→ A graph without parallel edges and self – loop is known as Simple Graph.

→ Example:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 18
Unit 4 – Graph Theory - I

Remark

Type Edges Multiple Edges Self - Loop

Directed
Simple Graph Not Allowed Not Allowed
Undirected

Directed Allowed Allowed

Multigraph
Undirected Allowed Not Allowed

Directed
Mixed Graph Allowed Allowed
Undirected

(4) Regular Graph

→ A graph is a regular graph, if the degree of each vertex is same.

→ If the degree of each vertex of a graph G is k (k ∈ ℕ ∪ {0}), then the graph G is known
as k – regular graph.

→ Note that, if graph G has n vertices and is regular graph of degree k, then G has
kn
edges.
2
→ Example:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 19
Unit 4 – Graph Theory - I

(5) Complete Graph

→ A simple graph G in which there is an edge between every pair of vertices is known
as complete graph.

→ A complete graph with n vertices is denoted by K n .

→ The complete graph with n vertices is (n − 1) - regular.

→ Thus, the degree of each vertex of complete graph with n vertices is (n − 1).

→ Example:

→ The complete graph with n vertices (K n ) has

n(n − 1)
edges.
2
→ Example:
5(5 − 1)
The complete graph with n = 5 vertices (K 5 ) has = 10 edges.
2
(6) Cycle Graph

→ The cycle graph Cn (n ≥ 3) of length n is a graph which contains n vertices and n

edges (v1 , v2 ), (v2 , v3 ), (v3 , v4 ), … , (vn−1 , vn ), (vn , v1 ).

→ Example:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 20
Unit 4 – Graph Theory - I

→ Notes

• Cn (n ≥ 3) is a regular graph of degree 2.

• Every self – loop is a cycle graph.

(7) Bipartite Graph

→ The simple graph G is known as bipartite if,

• the vertex set V can be partitioned into two non – empty subsets V1 and V2 such
that each edge of G has one end vertex in V1 and another in V2

• V1 ∪ V2 = V and V1 ∩ V2 = ϕ

→ Here, V1 and V2 are called bipartition of the vertex set V.

→ Note that, a bipartite graph can have no self – loop as self – loop connects the same
vertex which is not permitted in bipartite graph.

→ Example:

• Here, V = { v1 , v2 , v3 , v4 , u1 , u2 , u3 , u4 }

• Partitions: V1 = { u1 , u2 , u3 , u4 }, V2 = { v1 , v2 , v3 , v4 }

• Also, V1 ∪ V2 = V and V1 ∩ V2 = ϕ

(8) Complete Bipartite Graph

→ A bipartite graph is known as complete bipartite if, each vertex of set V1 is joined with
each vertex of set V2 .

→ A complete bipartite graph is denoted by K m, n

where, m = number of vertices of set V1 and n = number of vertices of set V2

→ Note

• K m, n has m + n vertices and mn edges; m, n ∈ ℕ.

• A complete bipartite graph K m, n is regular if m = n.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 21
Unit 4 – Graph Theory - I

→ Example:

Subgraph
→ Consider a graph G = (V, E). A graph H = (V ′ , E ′ ) is called subgraph of G, if V ′ (H) ⊆
V(G), E ′ (H) ⊆ E(G).

→ Here G is known as Super graph of H.

→ Properties

• Every graph is a subgraph of itself.

• Every single vertex in a graph G is a subgraph of G.

• Every single edge in a graph G is a subgraph of G.

→ Example:

→ Vertex Deleted Subgraph

• The graph obtained by deleting a vertex v and all the edges incident to it from a
given graph G = (V, E) is called a vertex deleted subgraph of G.

• The resulting subgraph is denoted by G − v.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 22
Unit 4 – Graph Theory - I

• If we remove more than one vertex from a graph G = (V, E), then vertex deleted
subgraph will be denoted as H = (V ∖ V ′ , E ∖ E ′ ); where V ′ = the set of removed
vertices and E ′ = the set of edges which are incident with removed vertices

• Example:

→ Edge Deleted Subgraph

• The graph obtain by deleting an edge e from a given graph G = (V, E) is called
an edge deleted subgraph of G.

• The resulting subgraph is denoted by G − e.

• If we remove more than one edge from a graph G = (V, E), then edge deleted
subgraph will be denoted as H = (V, E ∖ E ′ ); where E ′ = the set of removed
edges.

• Example:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 23
Unit 4 – Graph Theory - I

Examples of Method-3: Special Types of a Graph

C 1 Answer the following questions for the undirected graph G:

(1). Check whether the graph is simple or not. Justify it.

(2). Check whether the graph is multigraph or not. Justify it.
(3). Check whether the graph is mixed or not. Justify it.

𝐀𝐧𝐬𝐰𝐞𝐫:

(𝟏) 𝐓𝐡𝐞 𝐠𝐫𝐚𝐩𝐡 𝐢𝐬 𝐧𝐨𝐭 𝐬𝐢𝐦𝐩𝐥𝐞, 𝐚𝐬 𝐢𝐭 𝐜𝐨𝐧𝐭𝐚𝐢𝐧𝐬 𝐬𝐞𝐥𝐟 – 𝐥𝐨𝐨𝐩 𝐞𝟓 𝐚𝐧𝐝 𝐩𝐚𝐫𝐚𝐥𝐥𝐞𝐥

𝐞𝐝𝐠𝐞𝐬 𝐞𝟏 𝐚𝐧𝐝 𝐞𝟐 .

(𝟐) 𝐓𝐡𝐞 𝐠𝐫𝐚𝐩𝐡 𝐢𝐬 𝐧𝐨𝐭 𝐚 𝐦𝐮𝐥𝐭𝐢𝐠𝐫𝐚𝐩𝐡 𝐚𝐬 𝐢𝐧 𝐮𝐧𝐝𝐢𝐫𝐞𝐜𝐭𝐞𝐝 𝐦𝐮𝐥𝐭𝐢𝐠𝐫𝐚𝐩𝐡

𝐬𝐞𝐥𝐟 – 𝐥𝐨𝐨𝐩𝐬 𝐚𝐫𝐞 𝐧𝐨𝐭 𝐚𝐥𝐥𝐨𝐰𝐞𝐝.

(𝟑) 𝐓𝐡𝐞 𝐠𝐫𝐚𝐩𝐡 𝐢𝐬 𝐧𝐨𝐭 𝐚 𝐦𝐢𝐱𝐞𝐝 𝐠𝐫𝐚𝐩𝐡 𝐚𝐬 𝐚𝐥𝐥 𝐭𝐡𝐞 𝐞𝐝𝐠𝐞𝐬 𝐚𝐫𝐞 𝐮𝐧𝐝𝐢𝐫𝐞𝐜𝐭𝐞𝐝.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 24
Unit 4 – Graph Theory - I

C 2 Answer the following questions for the directed graph G:

(1). Check whether the graph is simple or not. Justify it.

(2). Check whether the graph is multigraph or not. Justify it.
(3). Check whether the graph is mixed or not. Justify it.

𝐀𝐧𝐬𝐰𝐞𝐫:

(𝟏) 𝐓𝐡𝐞 𝐠𝐫𝐚𝐩𝐡 𝐢𝐬 𝐧𝐨𝐭 𝐬𝐢𝐦𝐩𝐥𝐞, 𝐚𝐬 𝐢𝐭 𝐜𝐨𝐧𝐭𝐚𝐢𝐧𝐬 𝐬𝐞𝐥𝐟 – 𝐥𝐨𝐨𝐩 𝐞𝟔 .

(𝟐) 𝐓𝐡𝐞 𝐠𝐫𝐚𝐩𝐡 𝐢𝐬 𝐚 𝐦𝐮𝐥𝐭𝐢𝐠𝐫𝐚𝐩𝐡 𝐚𝐬 𝐢𝐧 𝐝𝐢𝐫𝐞𝐜𝐭𝐞𝐝 𝐦𝐮𝐥𝐭𝐢𝐠𝐫𝐚𝐩𝐡 𝐬𝐞𝐥𝐟 – 𝐥𝐨𝐨𝐩𝐬

𝐚𝐫𝐞 𝐚𝐥𝐥𝐨𝐰𝐞𝐝.

(𝟑) 𝐓𝐡𝐞 𝐠𝐫𝐚𝐩𝐡 𝐢𝐬 𝐧𝐨𝐭 𝐚 𝐦𝐢𝐱𝐞𝐝 𝐠𝐫𝐚𝐩𝐡 𝐚𝐬 𝐚𝐥𝐥 𝐭𝐡𝐞 𝐞𝐝𝐠𝐞𝐬 𝐚𝐫𝐞 𝐝𝐢𝐫𝐞𝐜𝐭𝐞𝐝
C 3 Draw a complete graph K 6 and answer the following questions:
(1). Check whether K 6 is regular graph or not. Justify it.
(2). Find the total number of edges of K 6 .

𝐀𝐧𝐬𝐰𝐞𝐫:

(𝟏) 𝐊 𝟔 𝐢𝐬 𝐚 𝐫𝐞𝐠𝐮𝐥𝐚𝐫 𝐠𝐫𝐚𝐩𝐡, 𝐚𝐬 𝐝𝐞𝐠𝐫𝐞𝐞 𝐨𝐟 𝐞𝐚𝐜𝐡 𝐯𝐞𝐫𝐭𝐞𝐱 𝐢𝐬 𝟓.

(𝟐) 𝐊 𝟔 𝐡𝐚𝐬 𝟏𝟔 𝐞𝐝𝐠𝐞𝐬.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 25
Unit 4 – Graph Theory - I

C 4 Draw a graph which is

(1). regular but not complete (4). regular but not cycle
(2). regular and complete (5). cycle but not complete
(3). neither regular nor complete (6). bipartite but not regular

𝐀𝐧𝐬𝐰𝐞𝐫:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 26
Unit 4 – Graph Theory - I

Method 4 ⇝ Graph Isomorphism

Graph Isomorphism
→ Two graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are isomorphic if there exists a function
f: V1 → V2 such that

• f is one – one and onto

• (a, b) is an edge in E1 if an only if (f(a), f(b)) is an edge in E2 ; for any a, b ∈ V1

→ Such a function f is known as graph isomorphism.

→ If G1 and G2 are isomorphic, then it is denoted as 𝐆𝟏 ≅ 𝐆𝟐

→ If G1 and G2 are not isomorphic, then it is denoted as 𝐆𝟏 ≇ 𝐆𝟐

Another Definition of Graph Isomorphism

→ Two graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are isomorphic if

• |V1 | = |V2 | i.e., number of vertices are same

• |E1 | = |E2 | i.e., number of edges are same

• G1 and G2 have same degree sequence

▪ i.e., if G1 has n vertices of degree k, then G2 must have exactly n vertices of

degree k.

• adjacency is preserved.

▪ i.e., if edge e is incident on vertices v1 and v2 in G1 , then the corresponding

edge e′ in G2 must be incident on the vertices v1′ and v2′ that correspond to
v1 and v2 respectively.

Degree Sequence of a Graph

→ For a graph G = (V1 , E1 ), if v1 , v2 , v3 , … , vn are n vertices of G and let d1 , d2 , d3 , … , dn
be their degrees respectively.

→ If the sequence (d1 , d2 , d3 , … , dn ) is monotonically increasing (i. e. , d1 ≤ d2 ≤ d3 ≤

⋯ ≤ dn ), then it called degree sequence of graph G.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 27
Unit 4 – Graph Theory - I

→ Example:

→ The degree sequence of the graph shown in figure is (2, 2, 3, 5) as d(v1 ) = 2, d(v2 ) =
3, d(v3 ) = 2 and d(v4 ) = 5.

→ Procedure to check whether the undirected graphs are isomorphic or not:

• Let G1 = (V1 , E1 ) and G2 = (V2 , E2 ) be two undirected graphs.

▪ Step:1 |V1 | = |V2 |

▪ Step:2 |E1 | = |E2 |

▪ Step:3 G1 and G2 must have same degree sequence.

i.e., if G1 has n vertices of degree k, then G2 must have exactly n

vertices of degree k.

▪ Step:4 Adjacency must be preserved.

i.e., if edge e is incident on vertices v1 and v2 in G1 , then the

corresponding edge e′ in G2 must be incident on the vertices v1′ and
v2′ that correspond to v1 and v2 respectively.

• If all the four steps are satisfied, then we can say G1 and G2 are isomorphic.

• If any of the above step does not satisfy, then G1 and G2 are not isomorphic.

→ Procedure to check whether the directed graphs are isomorphic or not:

• Let G1 = 〈V1 , E1 〉 and G2 = 〈V2 , E2 〉 be two directed graphs.

▪ Step:1 |V1 | = |V2 |

▪ Step:2 |E1 | = |E2 |

▪ Step:3 If G1 has n vertices of in – degree k1 and out – degree k 2 , then G2

must have exactly n vertices of in – degree k1 and out – degree k 2 .

▪ Step:4 Adjacency must be preserved.

i.e., if edge e is incident on vertices v1 and v2 in G1 , then the

corresponding edge e′ in G2 must be incident on the vertices v1′ and
v2′ that correspond to v1 and v2 respectively.

• If all the four steps are satisfied, then we can say G1 and G2 are isomorphic.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 28
Unit 4 – Graph Theory - I

• If any of the above step does not satisfy, then G1 and G2 are not isomorphic.

Remark

→ Every graph G is isomorphic to itself. (Reflexive)

→ If G1 ≅ G2 ⇒ G2 ≅ G1 (Symmetric)

→ If G1 ≅ G2 and G2 ≅ G3 ⇒ G1 ≅ G3 (Transitive)

Examples of Method-4: Graph Isomorphism

C 1 Check whether the given pair of graphs are isomorphic or not.

𝐀𝐧𝐬𝐰𝐞𝐫: 𝐆𝟏 ≅ 𝐆𝟐
C 2 Check whether the given pair of graphs are isomorphic or not.

𝐀𝐧𝐬𝐰𝐞𝐫: 𝐆 ≇ 𝐇

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 29
Unit 4 – Graph Theory - I

C 3 Check whether the given pair of graphs are isomorphic or not.

𝐀𝐧𝐬𝐰𝐞𝐫: 𝐆𝟏 ≅ 𝐆𝟐
C 4 Check whether the given pair of graphs are isomorphic or not.

𝐀𝐧𝐬𝐰𝐞𝐫: 𝐆𝟏 ≇ 𝐆𝟐

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 30
Unit 4 – Graph Theory - I

Method 5 ⇝ Connectivity
Path of Graph
→ A path of a graph G is an alternating sequence of vertices and edges of the form
𝐯𝟏 𝐞𝟏 𝐯𝟐 𝐞𝟐 𝐯𝟑 … 𝐯𝐧−𝟏 𝐞𝐧 𝐯𝐧 ; where the vertices vi and vi−1 are the end points of the edge
ei , i = 1, 2, 3, … , n − 1

• Here, v1 is a starting or initial vertex, vn is end vertex and v2 , v3 , … , vn−1 are

called internal vertices.

→ If 𝐯𝟏 𝐞𝟏 𝐯𝟐 𝐞𝟐 𝐯𝟑 … 𝐯𝐧−𝟏 𝐞𝐧 𝐯𝐧 , we can say the path is from v1 to vn or the path between v1

and vn or connects v1 to vn .

→ If 𝐯𝟏 = 𝐯𝐧 (i.e., starting and end vertices are same), then the path is known as closed
path.

→ The total number of edges which are present in a path is called length of a path.

• A path of length n is denoted by Pn .

• A path of length zero consists of a single vertex.

→ Simple Path

• A path in a graph is known as simple if the edges do not repeat in path.

→ Elementary Path

• A path in a graph is known as elementary if the vertices do not repeat in path.

→ Note

• Every elementary path is always a simple path.

• Closed path can never be elementary path.

→ Example:

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 31
Unit 4 – Graph Theory - I

Closed Elementary Simple

Path Length
Path Path Path

𝐯𝟑 𝐞𝟓 𝐯𝟏 1 No Yes Yes

𝐯𝟑 𝐞𝟑 𝐯𝟒 𝐞𝟒 𝐯𝟏 2 No Yes Yes

𝐯𝟑 𝐞𝟖 𝐯𝟒 𝐞𝟑 𝐯𝟑 𝐞𝟓 𝐯𝟏 3 No No Yes

𝐯𝟏 𝐞𝟕 𝐯𝟏 1 Yes No Yes

𝐯𝟏 𝐞𝟓 𝐯𝟑 𝐞𝟑 𝐯𝟒 𝐞𝟒 𝐯𝟏 3 Yes No Yes

𝐯𝟐 𝐞𝟔 𝐯𝟒 𝐞𝟖 𝐯𝟑 𝐞𝟑 𝐯𝟒 𝐞𝟔 𝐯𝟐 4 Yes No No

Cycle or Circuit
→ A closed path in a graph G is known as a cycle or circuit.

i.e., a path of length greater than zero that begins and ends at the same vertex is called
a circuit or cycle.

→ A cycle of length n is known as n – cycle and is denoted as 𝐂𝐧 .

→ Example:

• Cycle of length 3 ⇝ v3 e2 v2 e6 v4 e3 v3

• Cycle of length 4 ⇝ v1 e4 v4 e3 v3 e2 v2 e1 v1

• Cycle of length 5 ⇝ v3 e8 v4 e3 v3 e2 v2 e6 v4 e3 v3

→ Elementary Cycle

• A cycle is known as elementary if all the vertices in a cycle are distinct except
the end vertices.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 32
Unit 4 – Graph Theory - I

→ Simple Cycle or Trail

• A cycle is known as simple if all the edges in cycle are distinct.

i.e., a simple closed path is known as trail or simple cycle.

→ Example:

• C3 = v3 e2 v2 e6 v4 e3 v3 is an elementary as well as simple cycle.

• C5 = v3 e8 v4 e3 v3 e2 v2 e6 v4 e3 v3 is neither elementary nor simple cycle.

Connected Graph
→ An undirected graph is called connected if there is at least one path between every
pair of distinct vertices of the graph.

→ An undirected graph that is not connected is called disconnected.

→ We can produce a disconnected subgraph by removing vertices or edges, or both.

Strongly Connected Digraph

→ A directed graph G is said to be strongly connected if for each pair of vertices u, v in
G, there must be a path from u to v and from v to u.

→ Example:

• Here, there is a path between every pair of vertices.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 33
Unit 4 – Graph Theory - I

• Hence, the above graph is strongly connected.

Unilaterally Connected Digraph

→ A directed graph G is said to be unilaterally connected if for each pair of vertices u, v
in G, either there is a path from u to v or there is a path from v to u.

→ Example:

• Here, there is a path from v1 to v2 but there is no path from v2 to v1 .

• Hence, the above graph is unilaterally connected.

Weakly Connected Graph

→ A directed graph G is said to be weakly connected if its underlying undirected graph
is connected.

→ i.e., a directed graph G is said to be weakly connected if there is a path between every
two vertices when the directions of edges are removed.

→ Example:

Remarks

→ Any strongly connected directed graph is unilaterally connected as well as weakly

connected.

→ Any unilaterally connected directed graph is weakly connected.

→ But every weakly connected directed graph is not necessarily unilaterally connected
directed graph.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 34
Unit 4 – Graph Theory - I

→ Example:

• Here, digraph G1 is strongly connected.

• Digraph G2 is weakly connected but not strongly and unilaterally connected as

there is no path from v1 to v3 and/or v3 to v1 .

• Digraph G3 is unilaterally connected but not strongly connected as there is no

path from v6 to v1 .

Strongly Connected Components (SCC)

→ The maximal strongly connected subgraphs, are called the strongly connected
components or strong components of a digraph G.

→ Maximal strongly connected subgraphs means a subgraph S of G which is strongly

connected but no super graph of S which is strongly connected.

→ Algorithm to find Strongly Connected Components

• Find largest possible cycle in a given digraph. That cycle is an SCC.

• The remaining vertices independently makes SCC.

• If there is no cycle, then all the vertices make SCC independently.

→ Example:

• Here, vertex v1 , v2 and v3 forms a cycle, so they form a SCC S1.

• Also, there is a path from v4 to v5 and v6 to v5 but there is no path from v5 to v4

and v5 to v6 . So, the vertices v4 , v5 and v6 forms a single SCC.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 35
Unit 4 – Graph Theory - I

• Strongly Connected Components: { v1 , v2 , v3 }, { v4 }, { v5 }, { v6 }

Unilaterally Connected Components (UCC)

→ The maximal unilaterally connected subgraphs, are called the unilaterally connected
components or unilateral components of a digraph G.

→ Maximal unilaterally connected subgraphs means a subgraph S of G which is

unilaterally connected but no super graph of S which is unilaterally connected.

→ Algorithm to find Unilaterally Connected Components

• Find largest possible path in a given digraph. That path is a UCC.

• The remaining vertices independently makes UCC.

→ Example:

• Here, S is unilaterally connected but it is not maximal unilaterally connected

subgraph as S1 is a super graph of S and S1 is maximal unilaterally connected
subgraph.

• Unilaterally Connected Components: { v1 , v2 , v3 , v4 , v5 }, { v6 }

Weakly Connected Components (WCC)

→ The maximal weakly connected subgraphs, are called the weakly connected
components or weak components of a digraph G.

→ Maximal weakly connected subgraphs means a subgraph S of G which is weakly

connected but no super graph of S which is weakly connected.

→ Algorithm to find Weakly Connected Components

• Construct the underlying undirected graph of the given undirected graph.

• Find all the connected components of the undirected graph.

• The connected components of the undirected graph with the directions will be
the weakly connected components of the given directed graph.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 36
Unit 4 – Graph Theory - I

→ Example

Examples of Method-5: Connectivity

C 1 From the given directed graph determine
(1) path of length 3, 4, 5 and 6
(2) closed path of length 4
(3) an elementary path length 7
(4) a simple but not elementary path

𝐀𝐧𝐬𝐰𝐞𝐫: (𝟏) 𝐏𝟑 = 𝐮𝟖 𝐞𝟏𝟏 𝐮𝟑 𝐞𝟑 𝐮𝟒 𝐞𝟓 𝐮𝟓 ,

𝐏𝟒 = 𝐮𝟏 𝐞𝟏 𝐮𝟐 𝐞𝟐 𝐮𝟑 𝐞𝟑 𝐮𝟒 𝐞𝟒 𝐮𝟏 ,

𝐏𝟓 = 𝐮𝟏 𝐞𝟏 𝐮𝟐 𝐞𝟐 𝐮𝟑 𝐞𝟑 𝐮𝟒 𝐞𝟓 𝐮𝟓 𝐞𝟔 𝐮𝟔 ,

𝐏𝟔 = 𝐮𝟏 𝐞𝟏 𝐮𝟐 𝐞𝟏𝟎 𝐮𝟕 𝐞𝟖 𝐮𝟖 𝐞𝟏𝟏 𝐮𝟑 𝐞𝟑 𝐮𝟒 𝐞𝟒 𝐮𝟏

(𝟐) 𝐏𝟒 = 𝐮𝟏 𝐞𝟏 𝐮𝟐 𝐞𝟐 𝐮𝟑 𝐞𝟑 𝐮𝟒 𝐞𝟒 𝐮𝟏

(𝟑) 𝐏𝟕 = 𝐮𝟑 𝐞𝟑 𝐮𝟒 𝐞𝟒 𝐮𝟏 𝐞𝟏 𝐮𝟐 𝐞𝟏𝟎 𝐮𝟕 𝐞𝟖 𝐮𝟖 𝐞𝟗 𝐮𝟓 𝐞𝟔 𝐮𝟔

(𝟒) 𝐏𝟒 = 𝐮𝟏 𝐞𝟏 𝐮𝟐 𝐞𝟐 𝐮𝟑 𝐞𝟑 𝐮𝟒 𝐞𝟒 𝐮𝟏 ,

𝐏𝟓 = 𝐮𝟒 𝐞𝟒 𝐮𝟏 𝐞𝟏 𝐮𝟐 𝐞𝟐 𝐮𝟑 𝐞𝟑 𝐮𝟒 𝐞𝟓 𝐮𝟓

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 37
Unit 4 – Graph Theory - I

C 2 From the given directed graph determine

(1) circuit of length 3, 4, 5
(2) elementary cycle length 4
(3) trail of length 7
(4) an elementary as well as simple cycle
(5) simple but not elementary cycle
(6) neither elementary nor simple cycle

𝐀𝐧𝐬𝐰𝐞𝐫: (𝟏) 𝐂𝟑 = 𝐯𝟏 𝐞𝟓 𝐯𝟐 𝐞𝟐 𝐯𝟑 𝐞𝟏𝟎 𝐯𝟏 , 𝐂𝟒 = 𝐯𝟑 𝐞𝟕 𝐯𝟒 𝐞𝟖 𝐯𝟏 𝐞𝟓 𝐯𝟐 𝐞𝟐 𝐯𝟑

𝐂𝟓 = 𝐯𝟏 𝐞𝟓 𝐯𝟐 𝐞𝟐 𝐯𝟑 𝐞𝟕 𝐯𝟒 𝐞𝟑 𝐯𝟑 𝐞𝟏𝟎 𝐯𝟏

(𝟐) 𝐂𝟒 = 𝐯𝟐 𝐞𝟐 𝐯𝟑 𝐞𝟕 𝐯𝟒 𝐞𝟖 𝐯𝟏 𝐞𝟓 𝐯𝟐

(𝟑) 𝐂𝟕 = 𝐯𝟏 𝐞𝟓 𝐯𝟐 𝐞𝟔 𝐯𝟑 𝐞𝟕 𝐯𝟒 𝐞𝟖 𝐯𝟏 𝐞𝟏 𝐯𝟐 𝐞𝟐 𝐯𝟑 𝐞𝟏𝟎 𝐯𝟏

(𝟒) 𝐂𝟒 = 𝐯𝟏 𝐞𝟓 𝐯𝟐 𝐞𝟔 𝐯𝟑 𝐞𝟕 𝐯𝟒 𝐞𝟒 𝐯𝟏

(𝟓) 𝐂𝟕 = 𝐯𝟐 𝐞𝟔 𝐯𝟑 𝐞𝟕 𝐯𝟒 𝐞𝟒 𝐯𝟏 𝐞𝟓 𝐯𝟐 𝐞𝟐 𝐯𝟑 𝐞𝟏𝟎 𝐯𝟏 𝐞𝟏 𝐯𝟐

(𝟔) 𝐂𝟖 = 𝐯𝟐 𝐞𝟔 𝐯𝟑 𝐞𝟕 𝐯𝟒 𝐞𝟒 𝐯𝟏 𝐞𝟓 𝐯𝟐 𝐞𝟐 𝐯𝟑 𝐞𝟕 𝐯𝟒 𝐞𝟒 𝐯𝟏 𝐞𝟏 𝐯𝟐
C 3 Check whether the graph G is strongly connected, unilaterally connected or
weakly connected. Also, find its component.

𝐀𝐧𝐬𝐰𝐞𝐫: 𝐆 𝐢𝐬 𝐮𝐧𝐢𝐥𝐚𝐭𝐞𝐫𝐚𝐥𝐥𝐲 𝐚𝐬 𝐰𝐞𝐥𝐥 𝐚𝐬 𝐰𝐞𝐚𝐤𝐥𝐲 𝐜𝐨𝐧𝐧𝐞𝐜𝐭𝐞𝐝 𝐠𝐫𝐚𝐩𝐡.

𝐒𝐂𝐂: { 𝐯𝟏 , 𝐯𝟐 , 𝐯𝟑 }, { 𝐯𝟒 }, { 𝐯𝟓 },

𝐔𝐂𝐂 & 𝐖𝐂𝐂: { 𝐯𝟏 , 𝐯𝟐 , 𝐯𝟑 , 𝐯𝟒 , 𝐯𝟓 }

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 38
Unit 4 – Graph Theory - I

C 4 Check whether the graph G is strongly connected, unilaterally connected or

weakly connected. Also, find its component.

𝐀𝐧𝐬𝐰𝐞𝐫: 𝐓𝐡𝐞 𝐠𝐢𝐯𝐞𝐧 𝐠𝐫𝐚𝐩𝐡 𝐢𝐬 𝐝𝐢𝐬𝐜𝐨𝐧𝐧𝐞𝐜𝐭𝐞𝐝.

𝐒𝐂𝐂: { 𝐯𝟏 , 𝐯𝟒 , 𝐯𝟓 , 𝐯𝟑 , 𝐯𝟐 }, { 𝐯𝟔 }, { 𝐯𝟕 }, { 𝐯𝟖 }, { 𝐯𝟗 }, { 𝐯𝟏𝟎 }

𝐔𝐂𝐂: { 𝐯𝟏 , 𝐯𝟒 , 𝐯𝟑 , 𝐯𝟐 , 𝐯𝟓 , 𝐯𝟔 }, { 𝐯𝟕 , 𝐯𝟖 }, { 𝐯𝟗 }, { 𝐯𝟏𝟎 }

𝐖𝐂𝐂: {𝐯𝟏 , 𝐯𝟐 , 𝐯𝟑 , 𝐯𝟒 , 𝐯𝟓 , 𝐯𝟔 , 𝐯𝟕 , 𝐯𝟖 }, { 𝐯𝟗 }, { 𝐯𝟏𝟎 }

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 39
Unit 4 – Graph Theory - I

Method 6 ⇝ Matrix Representation of a Graph

Adjacency Matrix for an Undirected Graph
→ Let G = (V, E) be an undirected graph with n vertices and without parallel edges.

→ The adjacency matrix of graph G = (V, E) is denoted as A or AG and is defined as an

n × n matrix A = [aij ] whose elements aij are given as follows:

1, if there is an edge between the vertex vi and vj

aij = {
0, otherwise

Adjacency Matrix for a Directed Graph

→ Let G = 〈V, E〉 be a directed graph with n vertices and without multi edges.

→ The adjacency matrix of graph G = 〈V, E〉 is denoted as A or AG and is defined as an

n × n matrix A = [aij ] whose elements aij are given as follows:

1, if there is a directed edge between the vertex vi and vj

aij = {
0, otherwise
→ Observations

• For a directed graph,

▪ The sum of all 1’s in a row indicates the out – degree of the corresponding
vertex.

▪ The sum of all 1’s in a column indicates the in – degree of the corresponding
vertex.

• For a null graph which consists of only n vertices but no edges, the adjacency
matrix is a null matrix.

• If a graph has no self – loops, then the diagonal entries of the adjacency matrix
are zero.

• If there are loops at each vertex but no other edges in the graph, then the
adjacency matrix is the identity matrix.

Incidence Matrix for an Undirected Graph

→ Let G be an undirected graph with n vertices, m edges and without self – loops.

→ The incidence matrix of graph G is denoted as M or MG and is defined as an n × m

matrix M = [aij ] whose rows corresponds to vertices and columns corresponds to
edges such that

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 40
Unit 4 – Graph Theory - I

1, if edge ej is incident on the vertex vi

aij = {
0, otherwise

Incidence Matrix for a Digraph

→ Let G be a directed graph with n vertices, m edges and without self – loops.

→ The incidence matrix of graph G is denoted as M or MG and is defined as an n × m

matrix M = [aij ] whose rows corresponds to vertices and columns corresponds to
edges such that
1, if edge ej is incident out of the vertex vi
aij = { −1, if edge ej is incident in of the vertex vi
0, otherwise
→ Observations

• For the Undirected Graph

▪ Since every edge is incident on exactly two vertices, each column of

incidence matrix has exactly two 1′ s.

▪ The number of 1′ s in each row equals the degree of the corresponding

vertex.

▪ A row with all the entries zero in an incidence matrix represents isolated
vertex.

▪ The columns corresponding to parallel edges in an incidence matrix are

always same.

Path Matrix for a Directed Graph

→ Let G be a simple digraph with n vertices v1 , v2 , … , vn .

• The path matrix of a digraph graph G is denoted as P and is defined as an n × n

matrix P = [aij ] whose elements aij are given as follows:

1, if there is a path from the vertex vi to vj

aij = {
0, otherwise

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 41
Unit 4 – Graph Theory - I

Examples of Method-6: Matrix Representation of a Graph

C 1 Find an adjacency matrix for the following graph:

𝐀𝐧𝐬𝐰𝐞𝐫:

𝐯𝟏 𝐯𝟐 𝐯𝟑 𝐯𝟒
𝐯𝟏 𝟏 𝟏 𝟎 𝟏

𝐯𝟐 𝟏 𝟎 𝟏 𝟏
𝐀=
𝐯𝟑 𝟎 𝟏 𝟎 𝟏

𝐯𝟒 [ 𝟏 𝟏 𝟎 𝟎 ]
C 2 Find an adjacency matrix for the following directed graph:

𝐀𝐧𝐬𝐰𝐞𝐫:

𝐯𝟏 𝐯𝟐 𝐯𝟑 𝐯𝟒
𝐯𝟏 𝟏 𝟏 𝟎 𝟏

𝐯𝟐 𝟎 𝟎 𝟎 𝟏
𝐀=
𝐯𝟑 𝟏 𝟏 𝟎 𝟏

𝐯𝟒 [ 𝟎 𝟎 𝟏 𝟎 ]

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 42
Unit 4 – Graph Theory - I

1 0 1 0
0 0 1 0
C 3 Draw the directed graph having adjacency matrix A = .
1 0 0 1
[ 0 0 1 0 ]

𝐀𝐧𝐬𝐰𝐞𝐫:

C 4 Find an incidence matrix for the following graph:

𝐀𝐧𝐬𝐰𝐞𝐫:

𝐞𝟏 𝐞𝟐 𝐞𝟑 𝐞𝟒 𝐞𝟓 𝐞𝟔
𝐯𝟏 𝟏 𝟎 𝟎 𝟏 𝟎 𝟎

𝐯𝟐 𝟏 𝟏 𝟎 𝟎 𝟏 𝟎
𝐌=
𝐯𝟑 𝟎 𝟏 𝟏 𝟎 𝟎 𝟏

𝐯𝟒 [ 𝟎 𝟎 𝟏 𝟏 𝟏 𝟏]

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 43
Unit 4 – Graph Theory - I

C 5 Find an incidence matrix for the following directed graph:

𝐀𝐧𝐬𝐰𝐞𝐫:

𝐞𝟏 𝐞𝟐 𝐞𝟑 𝐞𝟒 𝐞𝟓 𝐞𝟔
𝐯𝟏 𝟏 𝟎 𝟎 −𝟏 𝟎 𝟎

𝐯𝟐 −𝟏 −𝟏 𝟎 𝟎 −𝟏 𝟎
𝐌=
𝐯𝟑 𝟎 𝟏 −𝟏 𝟎 𝟎 𝟏

𝐯𝟒 [ 𝟎 𝟎 𝟏 𝟏 𝟏 −𝟏 ]
C 6 Determine the incidence matrix for the following directed graph:

𝐀𝐧𝐬𝐰𝐞𝐫:

𝐞𝟏 𝐞𝟐 𝐞𝟑 𝐞𝟒 𝐞𝟓 𝐞𝟔 𝐞𝟕 𝐞𝟖
𝐯𝟏 𝟏 𝟎 𝟎 𝟏 𝟎 −𝟏 𝟏 𝟎

𝐯𝟐 −𝟏 −𝟏 𝟎 𝟎 𝟏 𝟎 −𝟏 𝟎
𝐌=
𝐯𝟑 𝟎 𝟏 −𝟏 𝟎 𝟎 𝟏 𝟎 𝟏

𝐯𝟒 [ 𝟎 𝟎 𝟏 −𝟏 −𝟏 𝟎 𝟎 −𝟏 ]

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 44
Unit 4 – Graph Theory - I

C 7 Draw the directed graph having incidence matrix

1 0 0 1 −1 1 0 0
−1 1 0 0 0 0 −1 0
A= 0 −1 1 0 1 −1 1 1
0 0 −1 −1 0 0 0 −1
[0 0 0 0 0 0 0 0]

𝐀𝐧𝐬𝐰𝐞𝐫:

C 8 Find the path matrix for the following directed graph:

𝐀𝐧𝐬𝐰𝐞𝐫:

𝟏 𝟎 𝟏 𝟏

𝟏 𝟎 𝟏 𝟏
𝐏=
𝟏 𝟎 𝟏 𝟏

[ 𝟏 𝟎 𝟏 𝟏 ]

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 45
Unit 4 – Graph Theory - I

Method 7 ⇝ Warshall’s Algorithm

Warshall’s Algorithm to Produce a Path Matrix
→ Let G be a directed graph with n vertices v1 , v2 , … , vn and suppose we want to find the
path matrix P of the graph G.

→ Define n + 1 square Boolean matrices P0 , P1 , P2 , … , Pn as follows:

• Let Pk [i, j] denotes the ijth entry of the matrix Pk . Then

1, if there is a simple path from vi and vj which does not
Pk [i, j] = { use any other vertices except possible v1 , v2 , … , vk
0, otherwise
• That means,

▪ P0 [i, j] = 1, if there is an edge from vi to vj .

Note that, P0 = A is the adjacency matrix of G.

▪ P1 [i, j] = 1, if there is a simple path from vi to vj which does not use any
vertex except possibly v1 .

▪ P2 [i, j] = 1, if there is a simple path from vi to vj which does not use any
vertex except possibly v1 and v2 .

▪ Continue this process until we obtain Pn [i, j] or Pn .

• Since G has only n vertices, the last matrix Pn = P is the path matrix of G.

Computation of 𝐏𝐤 from 𝐏𝐤 −𝟏

→ Keep all 1’s of Pk−1 as it is in Pk .

• i.e., if an element of Pk−1 is 1, then the corresponding entry of Pk is also 1.

→ Consider the k th column of Pk−1 and list out locations/positions u1 , u2 , … , ur ;

1≤r≤n

→ Consider the k th row of Pk−1 and list out locations/positions v1 , v2 , … , vt ; 1 ≤ t ≤ n

→ Place 1 at the location (ui , vj ) in Pk if 1 is not already there.

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 46
Unit 4 – Graph Theory - I

Examples of Method-7: Warshall’s Algorithm

C 1 Apply Warshall’s algorithm to produce a path matrix for the given graph.

𝐀𝐧𝐬𝐰𝐞𝐫:

𝟎 𝟏 𝟎 𝟏 𝟏

𝟎 𝟏 𝟎 𝟏 𝟏

𝐏= 𝟏 𝟏 𝟎 𝟏 𝟏

𝟎 𝟏 𝟎 𝟏 𝟏

[ 𝟎 𝟏 𝟎 𝟏 𝟏 ]
C 2 Apply Warshall’s algorithm to produce a path matrix for the given graph.

𝐀𝐧𝐬𝐰𝐞𝐫:

𝟎 𝟏 𝟏 𝟏

𝟎 𝟎 𝟎 𝟎
𝐏=
𝟎 𝟏 𝟏 𝟏

[ 𝟎 𝟏 𝟏 𝟏 ]

* * * * * End of the Unit * * * * *

Discrete Mathematics (2301HS301)

B.Tech., B.Sc. (H) - CS 2025(e) – Page 47