Semester: IV (2025-26)

DISCRETE MATHEMATICS & GRAPH THEORY

[BE04000261]
SEMESTER- 4 BRANCH:Computer Engineering

CHAPTER NO- 5: GRAPH

“BEGIN AT THE BEGINNING AND GO ON TILL

YOU COME TO THE END;
THEN STOP”

GTU SYLLABUS
WEIGHTAGE : 27%

Graph: Introduction, definition, examples; Nodes, edges, adjacent nodes, directed and
DMGT (BE04000261) Page | 1
 Semester: IV (2025-26)

undirected edge, Directed graph, undirected graph, examples;

Initiating and terminating nodes, Loop (sling), Distinct edges, Parallel edges,
Multi-graph, simple graph, weighted graphs, examples,
Isolated nodes, Null graph; Isomorphic graphs, examples;
Degree, In degree, out-degree, total degree of a node, examples;

Sub graphs: definition, examples; Converse (reversal or directional dual) of a digraph,

examples;

Path: Definition, Paths of a given graph, length of path, examples;

Simple path (edge simple),elementary path (node simple), examples;
Cycle (circuit), elementary cycle, examples;

Reachability: Definition, geodesic, distance, examples;

Properties of reachability, the triangle inequality;
Reachable set of a given node, examples, Node base, examples;

Connectedness: Definition, weakly connected, strongly connected, unilaterally

connected, examples;
Strong, weak, and unilateral components of a graph, examples,
Applications to represent Resource allocation status of an operating system, and
detection and correction of deadlocks;

Matrix representation of graph: Definition, Adjacency matrix, Boolean (or bit)

matrix, examples; Determine number of paths of length n through Adjacency matrix, examples;

Path (Reachability) matrix of a graph ,examples;

Warshall’s algorithm : to produce Path matrix, Flowchart.

Trees: Definition, branch nodes, leaf (terminal) nodes, root, examples; Different
representations of a tree, examples; Binary tree, m-ary tree, Full (or complete) binary
tree, examples; Converting any m-ary tree to a binary tree, examples; Representation
of a binary tree: Linked-list; Tree traversal: Pre-order, in-order, post-order traversal,
examples, algorithms; Applications of List structures and graphs

TOPIC:1 GRAPHS
SHORT QUESTIONS
1 Define: Graph 1
Solution

Definition:A graph G is a pair of sets (V,E)

Where V is a non-empty set of vertices(nodes) a
And E is a set of edges.

Example:
DMGT (BE04000261) Page | 2
 Semester: IV (2025-26)

𝑉 = {𝑣1 , 𝑣2 , 𝑣3 }

𝐸 = {𝑒1 , 𝑒2 , 𝑒3 }

𝐺≠∅
2 Define Adjacent Vertices and Adjacent Edges 2
Solution

Adjacent Vertices Adjacent Edges

Definition:Two vertices 𝑣𝑖 and𝑣𝑗 Definition:Twoedges 𝑒𝑖 and𝑒 𝑗

(𝑣𝑖 ≠ 𝑣𝑗 )are said to be adjacent if they are
joined (connected) by the same edge. (𝑒𝑖 ≠ 𝑒𝑗 )are said to be adjacent if they are
joined by the same end vertex.
Example: Example:

𝐴and𝐶are adjacent vertices 𝐴𝐵 and𝐴𝐶 are adjacent edges

𝐵 and𝐷 are adjacent vertices 𝐴𝐶 and𝐴𝐷 are adjacent edges

𝐴 and𝐵 are adjacent vertices 𝐵𝐷 and𝐶𝐷 are adjacent edges

𝐶 and𝐷are adjacent vertices 𝐴𝐵 and𝐵𝐷 are adjacent edges

𝐴 and𝐷are not adjacent vertices 𝐴𝐵 and𝐶𝐷 are not adjacent edges

𝐵 and 𝐶 are not adjacent vertices 𝐴𝐶 and𝐵𝐷 are not adjacent edges
3 Define: Directed graph, Non-Directed graph and Mixed graph 3

Solution:
Directed Non-Directed/Undirected Mixed Graph
graph(Digraph)(Jul-2022) graph
Definition: A graph G in Definition: A graph G in Definition: If some edge of
which each edge has a which each edge has a a graph G are directed and
directionis called a directed Nodirectionis called a non- some are undirected then G
directed graph.
graph. (Digraph) is said to be a mixed graph

Example: Example: Example:

DMGT (BE04000261) Page | 3

 Semester: IV (2025-26)

4 Define: Self-Loop(Feb-2021) and Parallel Edges. 2

Solution

Self-Loop / Sling / Loop Parallel Edges

Definition:An edge ‘e’joining a vertex to Definition:If two or more edges have same
itself is called a self-loop. end vertices then they are called parallel
edges.
Example: Example:
(2)Non-Directed graph with self-loop (1)Undirected graph with parallel edges

(2)Directed graph with self-loop (2)Directed graph with parallel edges

5 Define: Simple Graph,Multi Graph, Pseudo Graph 3

Solution
Simple Graph Multi Graph Pseudo Graph
A graph G is called Simple A graph G is called Multi A graph G is called
Graph if graph if PseudoGraphif
G has no self-loops. G has no self-loops but G has self-loops and
G has no parallel edges. G has parallel edges. G has parallel edges.

Example: Example: Example:

(1)Simple Undirected (1)Multi Undirected (1)Psuedo Undirected
graph graph graph

DMGT (BE04000261) Page | 4

 Semester: IV (2025-26)

(2)Simple Directed graph (2)Multi Directed graph (2) Psuedo Directed graph

6 Define: Weighted Graph 1

Solution: A graph G in which weight (positive real number) are assigned to every edge is
called weighted graph.
Example

7 Define: Finite Graph and Infinite Graph 2

Solution
Finite Graph Infinite Graph
A graph G with a finite number of edges A graph G is called infinite if it is not
and finite number of vertices is called a finite.
finite graph.
Example: Example:

8 Define: Null Graph and Trivial Graph 1

Solution
Null Graph Trivial Graph
A graph containing only isolated nodes is A graph where vertex set contain any one
called a null graph vertex and edge set is empty is called
trivial graph.
Example: Example:

DMGT (BE04000261) Page | 5

 Semester: IV (2025-26)

9 Define: Isolated node and Pendant vertex 1

Solution:
Isolated node(vertex) Pendant vertex / End vertex
A vertex of a graph with degree zero is A vertex of a graph with degree one is
called an isolated vertex. called a pendent vertex( or end vertex
Every vertex in a null graph is an isolated
vertex

Example: Example:

10 Define Degree of a vertex 1

Solution:The degree of a vertex v in a graph G is the number of edges incident with v
Notation: d(v)ordeg(v)
Example:

𝑑 (𝑎) = 2 𝐸𝑣𝑒𝑛 𝑣𝑒𝑟𝑡𝑒𝑥

𝑑 (𝑏) = 2 𝐸𝑣𝑒𝑛 𝑣𝑒𝑟𝑡𝑒𝑥
𝑑 (𝑐 ) = 3 𝑂𝑑𝑑 𝑣𝑒𝑟𝑡𝑒𝑥
𝑑 (𝑑 ) = 1 𝑂𝑑𝑑 𝑣𝑒𝑟𝑡𝑒𝑥
If the degree of a vertex is odd then its odd vertex.
If the degree of a vertex is even then its even vertex.

11 Define In degree and Out degree of a vertex and give example. 3

Solution:
In degree of a vertex Out degree of a vertex
In a directed graph G the no. of edge In a directed graph G the no. of edges
ending at a vertex V is called in degree of beginning from vertex V called out degree
V of V.

In degree is denoted by 𝑑 + (𝑉𝑖 ) or ⃗⃗⃗⃗⃗⃗⃗⃗⃗

𝑑(𝑉𝑖 ) or Out degree is denoted by 𝑑 − (𝑉𝑖 ) or ⃖⃗⃗⃗⃗⃗⃗⃗⃗⃗
𝑑(𝑉𝑖 )
in degree (𝑉𝑖 ) or out degree (𝑉𝑖 )
A self-loop contributes two degrees ( One out degree and One in degree)
The sum of in degree and out degree is called the total degree of a vertex
Example:

DMGT (BE04000261) Page | 6

 Semester: IV (2025-26)

VERTEX IN DEGREE OUT DEGREE

A 1 2
B 2 1
C 2 1
D 1 1
E 1 1
F 1 1
G 0 1
12 Define : Complete Graph 1
Solution:Complete Graph: A simple Graph G in which every pair of distinct vertices are
adjacent is called a complete graph
 Degree of each vertex is (𝑛 − 1)
 Complete graph with n vertices is denoted by 𝐾𝑛
 𝐾𝑛 is called (𝑛 − 1) regular graph.
𝑛(𝑛−1)
 𝐾𝑛 has exactly edges.
2
 𝐾𝑛 has neither loops nor parallel edges.

Example:

13 Define with example : (1) Order of a graph (2) Size of a graph 3

Solution:
Order of a graph Size of a graph
If G = ( V, E ) is a finite graph then If G = ( V, E ) is a finite graph then
|𝑉 | = 𝑁𝑜. 𝑜𝑓 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 𝑖𝑛 𝐺 |𝐸 | = 𝑁𝑜. 𝑜𝑓 𝑒𝑑𝑔𝑒𝑠 𝑖𝑛 𝐺
is called order of a graph G. is called size of a graph G.
Example: Example:

Order ( G ) = 4 Size ( G ) = 6
14 Define k-regular graph with example. 3
Solution:
DMGT (BE04000261) Page | 7
 Semester: IV (2025-26)

A graph G is said to be k – regular if every vertex of G have degree k.

 All the vertices of G have the same degree.
 A regular graph of degree zero has no line.
 If G is a regular graph of degree 3 it is called a cubic graph.
 Every cubic graph has an even number of points/vertices.
 Every Complete graph is regular graph, but converse is not true.
i.e. Regular graph may not be complete.
Examples:
(1) 2-Regular graph with 4 vertices (2) 3-Regular graph with 4 vertices

(3) 4-Regular graph with 5 vertices (4) K3 (2-Regular graph with 3 vertices)

(4) K1 (0-Regular graph with 1 vertex) (4) K2 (1-Regular graph with 2 vertices)

15 Define with example: (1)Bipartite graph (2)Complete Bipartite graph . 3

Solution:
Bipartite graph Complete Bipartite graph

A simple graphGis called bipartite if A bipartite graphis known as Complete

V can be partitioned in to two subsets Bipartite graph if each vertex of V1 is
V1 and V2 such that joined with each vertex of V2.
 every edge of G joins V1 with V2  It is denoted by Km,n where
 V1 ∪ V2 = V  m=number of vertices in V1
 V1 ∩ V2 = ∅  n=number of vertices in V2

 Complete bipartite graph is regular if in Km,nwe have m = n

 K1,1K2,2K3,3K4,4are regular graphs.

Examples of Bipartite graph

DMGT (BE04000261) Page | 8

 Semester: IV (2025-26)

Examples of Complete Bipartite graph

16 Define Star graph 1

Solution:
A complete bipartite graph 𝐾1,𝑛 is called star graph.
Examples

 𝐾1,6 is a complete bipartite graph which is not regular

DESCRIPTIVE QUESTIONS
1 Define Graph, Directed edge of graph, Diagraph, Mixed graph, In degree of a node 5
with suitable example.
Solution:(1)Graph:A graph G is a pair of sets (V,E) , Where
 V=V(G)= {𝑣1 , 𝑣2 , 𝑣3 , ….} is a non-empty set of vertices.( node, junction, o-simplex)
 E =E(G)={𝑒1 , 𝑒2 , 𝑒3} , , ….} is a non-empty set of edges. (line, arc, branch , 1-simplex)

(2)Directed Edges:
In a directed graph G an edge ‘e’ which has direction from ‘u’ to ‘v’ is called directed edge of
graph G.

DMGT (BE04000261) Page | 9

 Semester: IV (2025-26)

(3) Directed Graph / Digraph:

A graph in which every edge is directed is called a directed graph (Digraph)

(4) Mixed Graph:

If some edge of a graph G are directed and some are undirected then G is said to be a mixed
graph.

(5)In degree & Out degree:

In a directed graph G the no. of edge ending at a vertex V is called in degree of V &
The no. of edges beginning from vertex V called out degree of V.

 In degree is denoted by 𝑑 + (𝑉𝑖 ) or ⃗⃗⃗⃗⃗⃗⃗⃗⃗

𝑑(𝑉𝑖 ) or in degree (𝑉𝑖 )
 Out degree is denoted by 𝑑 𝑉𝑖 or ⃖⃗⃗⃗⃗⃗⃗⃗⃗⃗
−( )
𝑑(𝑉𝑖 ) or out degree (𝑉𝑖 )
 A self-loop contributes two degrees ( One out degree and One in degree)
 The sum of in degree and out degree is called the total degree of a vertex

VERTEX IN DEGREE OUT DEGREE

A 1 2
B 2 1
C 2 1
D 1 1
E 1 1
F 1 1
DMGT (BE04000261) Page | 10
 Semester: IV (2025-26)

G 0 1
2 How many nodes are necessary to construct a graph with exactly 8 edges in which each 3
node is of degree 2? (Sep-2021)
Solution:
Given that |𝐸 |= 8

We know that ∑𝑛𝑖=1 𝑑( 𝑉𝑖 ) = 2 |𝐸 |

2 |𝐸 | = 2 × 8
|𝐸 |= 8

Number of vertices in G = 8Answer

3 Draw a simple graph with 4 nodes and 7 edges if possible. If not give reason. 3
Solution:Let G be a simple graph with order 4 and size 7
i.e. |𝑉 |= 4= n = no, of vertex and |𝐸 |= 7 = no. of edges (Max. no. of edges in G)
By theorem, Maximum number of edges in a simple graph with n vertices
𝑛(𝑛 − 1) (4)(4 − 1)
= = = 6
2 2
Maximum number of edges G can have is 6
It is given that number of edges in G is 7
|𝐸 |= 7 <6 ,Which is [Link],Simple graph with order 4 and Size 7 does not exist.

4 Define simple graph, degree of a vertex and complete graph. 3

Solution:
(1) Simple Graph:A graph which has neither loop nor parallel edges is called a simple graph.

(2)Degree of a vertex:The number of edges incident to a vertex v is called the degree of the
vertex and is denoted by deg(v)

(3)Complete Graph: A simple Graph G in which every pair of distinct vertices are adjacent is called
a complete graph.

5 Draw a graph which is regular but not bipartite. 3

DMGT (BE04000261) Page | 11
 Semester: IV (2025-26)

Solution: Complete graph K4 is regular as degree of each vertex is 3

V1 V2

V3 V4
3 Regular graph with 4 vertices is not bipartite as
V1 is joined with V3 and V2 is joined with V4
6 Draw two complete bipartite graphs, which are not regular. 3
Solution:
A complete bipartite graph 𝑲𝒎 ,𝒏 is not regular if 𝒎 ≠ 𝒏
(1) 𝐾3 ,4

7 A graph G has 15 edges, 3 vertices of degree 4 and other vertices of degree 3. Find the 3
number of vertices in G.

Solution:
For the graph,∑ 𝑑(𝑉𝑖 ) = 2|𝐸 |

𝑑(𝑉1 ) = 𝑑 (𝑉2 ) = 𝑑 (𝑉3 ) = 4 and |𝐸 | = 15

Suppose there are x vertices of degree 3.

⇒ 4 + 4 + 4 + 3 × 𝑥 = 2 × 15

⇒ 12 + 3 × 𝑥 = 30

⇒ 3 × 𝑥 = 30 − 12 = 18

18
⇒𝑥= =6
3

Hence, number of vertices in G = 3 + 6 = 9

8 Prove that there are always an even number of vertices of odd degree in a graph 3

Solution: Let G = (V, E) be an undirected graph.

Let 𝑉1 be the set of vertices of even degree and

Let 𝑉2 be the set of vertices of odd degree

We know that 2 | E | =∑𝑣∈𝑉 deg(𝑣) = ∑𝑣∈𝑉1 deg(𝑣) + ∑𝑣∈𝑉2 deg(𝑣)

DMGT (BE04000261) Page | 12

 Semester: IV (2025-26)

Since deg (v) is even for 𝑣 ∈ 𝑉1

So, ∑𝑣∈𝑉1 deg(𝑣) is even for 𝑣 ∈ 𝑉1

Also the sum of the two term on RHS is even = 2 | E |

So, the second term on RHS i.e. ∑𝑣∈𝑉2 deg(𝑣) must be even.

But Since all the terms in this sum are odd so there must be an even number of such terms.
Hence we conclude that there are an even number of vertices of odd degree

9 Find the number of edges in a r – regular graph with n – vertices. 3

Solution:Consider a r-regular graph G.

Then deg (v) = r,  v V(G).

 2 |𝐸 |deg (v) = ∑𝑛𝑟=1 𝑟 = r × n

𝑟×𝑛
|𝐸| =
2

10 Define self-loop, adjacent vertices and a pendant vertex. 3

Solution:
Adjacent Vertices (Nodes): If two nodes u and v are joined by an edge e then u and v are said
to be adjacent nodes.

Self-Loop(Sling): An edge e of a graph G that joins a node u to itself is called a loop. A loop is
an edge e = (u, v).

Pendent Vertex:
A vertex of a graph with degree one is called a pendent vertex( or end vertex)
SELF LOOP

A and D are adjacent vertices.

11 Find the number of edges in G if it has 5 vertices each of degree 2. 3

Solution:Given that |𝑉|= 5

We know that ∑𝑛𝑖=1 𝑑( 𝑉𝑖 ) = 2 |𝐸 |

⇒ 2 + 2 + 2 + 2 + 2 = 2 |𝐸 |

⇒ 2 |𝐸 | = 2 × 5⇒ |𝐸 | = 5

Number of edges in G = 5

12 Determine the number of edges in a graph with 6 nodes, 2 of degree 4 and 4 of degree 2. Draw two 3
such graphs.
DMGT (BE04000261) Page | 13
 Semester: IV (2025-26)

Solution:Given that |𝑉|= 6

We know that ∑𝑛𝑖=1 𝑑( 𝑉𝑖 ) = 2 |𝐸 |

⇒ 2 + 2 + 2 + 2 + 4 + 4 = 2 |𝐸 |

⇒ 2 |𝐸 | = 16⇒ |𝐸 | = 8

Number of edges in G = 8

13 Can a single undirected graph of 8 vertices have 40 edges excluding self-loop? 3

Solution:
If there is no self-loop, to get the maximum number of edges.
𝑛(𝑛−1) 8×7
Maximum number of edges = = = 28
2 2
So, a single undirected graph of 8 vertices cannot have 40 edges excluding self-loop
14 Draw a simple graph with 4 nodes and 7 edges if possible. If not give reason. 3
Solution:
It is not possible to draw a simple graph with 4 nodes and 7 edges

15 Does a 3-regular graph with 5 vertices exist? 3

Solution:
𝒓×𝒏
The number of edges in a r – regular graph with n – vertices = |𝑬| = 𝟐

The number of edges for a 3-regular graphwith 5 vertices are

𝑟×𝑛 3×5
|𝐸 | = = = 15/2 which is not possible.
2 2

Hence, such type of graph does not exist

16 Show that sum of in-degrees of all the nodes of simple digraph is equal to the sum of out- 7
degrees of all the nodes and this sum equal to the number of edges in it.

Solution:We have to show that

If G = (V,E) is a directed graph with n nodes 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 ,…and ‘e’ number of edges, then

∑ 𝒅𝒆𝒈− (𝒗) = ∑ 𝒅𝒆𝒈+ (𝒗) = 𝒆

𝒗∈𝑽 𝒗∈𝑽

DMGT (BE04000261) Page | 14

 Semester: IV (2025-26)

 Let G = (V, E) be a directed graph with n nodes 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 ,…and ‘e’ number of edges
 Any directed edge in G contributes ‘ 1 ‘out degree and ‘ 1 ‘in degree.
 Also, a self-loop contributes two degrees (1 out degree and 1 in degree)
 Once an edge is count for in degree it will not count for out degree.
 When we are adding the in degree of nodes , each edge is counted exactly once.
 Hence, total of in degrees of all nodes is same as the number of edges.

𝒊. 𝒆. ∑ 𝒅𝒆𝒈− (𝒗) = 𝒆
𝒗∈𝑽

Similarly, we can prove that ∑𝒗∈𝑽 𝒅𝒆𝒈+ (𝒗) = 𝒆

Hence, the theorem is proved.

17 How many edges does a graph have if it has vertices of degree 4, 3, 3, 2, 2? Draw such a 7
graph.
Solution=V(G)= {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 }
𝑑(𝑉1 ) = 4

𝑑(𝑉2 ) = 3

𝑑(𝑉3 ) = 3 and |𝐸 | = 7

𝑑(𝑉4 ) = 2

𝑑(𝑉5 ) = 2

|𝐸 | =?

∑ 𝑑 (𝑉𝑖 ) = 2|𝐸 |
∑ 𝑑( 𝑉𝑖 ) = 4+3+3+2+2 = 14 = 2|𝐸 |

⇒ 2(7) = 2|𝐸 | ⇒ |𝐸 | = 7

Such a graph has 7 edges. Here is such a graph:

18 How many edges are there in a graph with 10 vertices each of degree six? 3

Solution:Given that |𝑉|= 10

We know that ∑𝑛𝑖=1 𝑑( 𝑉𝑖 ) = 2 |𝐸 |

⇒ 6 × 10 = 2 |𝐸 |

⇒ 2 |𝐸 | = 60 ⇒ |𝐸 | = 30

Number of edges in G = 30

19 Is it possible to construct a graph with 12 nodes such that 2 of the nodes are 3
DMGT (BE04000261) Page | 15
 Semester: IV (2025-26)

having degree 3 and remaining vertices are having degree 4.

Solution:Given that |𝑉|= 12

We know that ∑𝑛𝑖=1 𝑑( 𝑉𝑖 ) = 2 |𝐸 | (Hand Shaking Lemma)

⇒ (3 × 2) + (10 × 4) = 2 |𝐸 |

⇒ 2 |𝐸 | = 46⇒ |𝐸 | = 23

Number of edges in G = 23
Yes, it is possible to construct a graph with 12 nodes such that two of its vertices have degree 3
and the remaining vertices have degree 4
20 Is it possible to draw a 3-regular graph with 5 vertices? 3
Solution:
Number of vertices n = 5, r= 3
Sum of the degrees of the vertices = 5 * 3 = 15, which is not divisible by 2.
Therefore, it is not possible to draw a 3-regular with 5 vertices.
Note: A graph with n vertices is r-regular if either r or n or both are even.
21 Let G be a simple graph with 12 edges. If G has 6 vertices of degree 3 and the 7
rest of the vertices have degree less than 3, then find the
(a) Minimum number of vertices and
(b) Maximum number of vertices.
Solution:Number of edges e = 12
Suppose the total number of vertices in G is p.
Given that 6 vertices have degree 3.
Hence, the sum of degrees =3 *6 = 18.
The rest (p — 6) vertices have degree less than 3.
i.e., their degree liesinclusively between 0 and 2.
Here, to find the minimum number of vertices,
(p — 6) vertices must havemaximumdegree [i.e., 2 ]
Therefore, applying the handshaking theorem, we get
18 + 2 𝑝 - 6 = 2𝑒
18 + 2𝑝 - 12 = 24
2𝑝 + 6 = 24
2𝑝 = 18 ⇒𝑝 = 9
Minimum number of vertices = 9
To calculate the maximum number of vertices,
(p — 6) vertices must havemaximumdegree [i.e., 1]
Sum of degrees = 18 + 𝑝 - 6 = 2𝑒 = 24
𝑝 + 12 = 24⇒𝑝 = 12
Maximum number of vertices = 12
22 Show that the graph C6 is bipartite. 3
Solution:In this graph, the two distinct sets of vertices are shown in distinct colours.
Hence,C6 is bipartite.

DMGT (BE04000261) Page | 16

 Semester: IV (2025-26)

23 Prove that a graph which contains a triangle cannot be bipartite. 3

Solution:
In a bipartite graph, the vertices should be divided into twodistinct subsets.
The number of vertices of the given graph is 3, as it is a triangle.
So, it isnot possible to divide the vertices into two disjoint set of vertices since each edge
is joined by the rest two edges.
Hence, this graph may not be a bipartite graph
24 How many edges do the complete bipartite graph, Km n have? 3
Solution:
The vertex set of Km n consists of two disjoint sets A and B.
A contains m vertices and B contains n vertices.
Each vertex in A is adjacent to each vertex in B.
No two vertices either in A or in B are adjacent.
Hence, the degree of each vertex in A is n, and the degree of each vertex inBis m.
Therefore, the sum of the degrees is 2 * m* n,
and so there are m* n edges(as per the handshaking theorem).
Note :Complete bipartite graph Km,n has m + n vertices and m * n edges.
Km, n is regular if m= n.
25 Explain the following terms with proper illustrations. a) Directed graphs b) Simple and 7
elementary path c) Reachability of a vertex d) Connected graph

Solution:
(a)Directed Graph / Digraph:
A graph in which every edge is directed is called a directed graph (Digraph)

(b) Simple and elementary path

Path:A path is a walk through a sequence of vertices V1  V2  V3  ...  Vn 1  Vn
 No. of edges in a path called the length of path.
 A loop can be included in a walk but not in path

Simple Path:The path is called simple one if no edge is repeated in the path,
Elementary Path:The path is called elementary one if no vertex is repeated in the path,

Naturally, every elementary path of a diagraph is also simple.

For example, let’s consider the graph:

DMGT (BE04000261) Page | 17

 Semester: IV (2025-26)

Simple Path:
1−2−3

1−4−3

1−2−4−3

Elementary Path:
1 − 2 − 3 ⇒ Length of path = 2

1 − 4 − 3 ⇒ Length of path = 2

1 − 2 − 4 − 3 ⇒ Length of path = 3

𝟏 − 𝟐 − 𝟒 − 𝟏 − 𝟒 − 𝟑 is simple but not elementary path

(c)Reachability of a vertex:

A vertex V of a simple digraph is said to be reachable from the vertex u of the same digraph, if
there exists a path from u to v.

Every node is reachable from itself

Example:

𝑃1 = (〈1,2〉, 〈2,1〉)

𝑃2 = (〈3,4〉, 〈4,3〉)

(d)Connected Graph: A graph G is connected if every pair of vertices are joined by a path
otherwise the graph is disconnected.

DMGT (BE04000261) Page | 18

 Semester: IV (2025-26)

Connected graph

26 1) Define: i) Isolated vertex ii) Null graph 3

2) Identify Isolated vertex/vertices from the following graph

Solution:
i) Isolated vertex :A vertex of a graph with degree zero is called an isolated vertex
ii) Null graph:A graph containing only isolated nodes is called a null graph
Isolated vertices are 𝑣4 𝑎𝑛𝑑 𝑣7
27 Define the terms: Simple Graph, Multi - Graph, Weighted Graph, Degree of a vertex, in 7
degree and out degree of a vertex. Illustrate each with an example.
Solution: Discussed Earlier
28 Define Cyclic graph, Null graph and Strongly connected graph. 3
Solution:
(1)Cyclic graph: A graph containing at least one cycle in it is called as a cyclic graph.
Examples-1

.
(2)Null Graph(Empty Graph):A graph containing only isolated nodes is called a null graph.

 a null graph does not contain any edges in it.

Example

(3)Strongly Connected Graph:A directed graph is said to be strongly connected if for every
two vertices a and b in G there is a path from a to b and b to a.

DMGT (BE04000261) Page | 19

 Semester: IV (2025-26)

29 Consider the complete graph Kn 3

(1) Find the number m of edges in Kn.
(2) Find the degree of each vertex in Kn.
(3) Find those values of n for which Kn is regular.
Solution:

 Knhas nvertices.

 Each vertex has degree n − 1.

 The sum of all degrees is n(n − 1).
 Now, the Handshaking Theorem tells us that. . .
𝑛(𝑛−1)
(1)The number m of edges in Kn is 2
(2)degree of each vertex in Kn= n – 1
(3)Kn is regular if all its vertices have the same degree n.
Note:
 A graph whose all vertices have degree 2 is known as a 2-regular graph.
 A complete graph Kn is a regular of degree n-1.
30 Explain the number of vertices and number of edges of following by drawing graphs: 7
(𝟏)𝑲𝟑 (𝟐)𝑲𝟐,𝟐
Solution:

𝑲𝟑 𝐾2,2

Graph Number of vertices Number of edges

𝐾3 3 𝑛(𝑛 − 1)
=3
2
𝐾2,2 4 𝑚×𝑛 = 2×2 = 4

31 Define Graph, Diagraph, Mixed graph with suitable example 3

Solution: Discussed Earlier

32 Define Degree of a vertex. Find the in-degree and out-degree of each vertex in the graph 7
G with directed edges shown in Figure

DMGT (BE04000261) Page | 20

 Semester: IV (2025-26)

Solution:

In degree of a vertex Out degree of a vertex

In a directed graph G the no. of edge In a directed graph G the no. of edges
ending at a vertex V is called in degree of beginning from vertex V called out degree
V of V.
In degree is denoted by 𝑑 + (𝑉𝑖 ) or ⃗⃗⃗⃗⃗⃗⃗⃗⃗
𝑑(𝑉𝑖 ) or Out degree is denoted by 𝑑 − (𝑉𝑖 ) or ⃖⃗⃗⃗⃗⃗⃗⃗⃗⃗
𝑑(𝑉𝑖 )
in degree (𝑉𝑖 ) or out degree (𝑉𝑖 )

 A self-loop contributes two degrees ( One out degree and One in degree)
 The sum of in degree and out degree is called the total degree of a vertex

VERTEX IN DEGREE OUT DEGREE

a 2 4
b 2 1
c 3 2
d 2 2
e 3 3
f 0 0
33 Define Bipartite graphs. Are the graphs G and H displayed in Figure bipartite? 7

Solution:
 Graph G is bipartitebecause its vertex set is the union of two disjoint sets,
 {a, b, d}and {c, e, f, g},
 and each edge connects a vertex in one of these subsets to a vertex in the other subset.
 (Note that for G to be bipartite it is not necessary that every vertex in {a, b, d} be
adjacent to every vertex in {c, e, f, g}. For instance, b and g are not adjacent.)

 Graph H is not bipartitebecause its vertex set cannot be partitioned into two subsets
sothat edges do not connect two vertices from the same subset.
 We can verify this byconsidering the vertices a, b, and f

34 Define Cycle and Wheel with suitable example. 3

DMGT (BE04000261) Page | 21

 Semester: IV (2025-26)

Solution:

35 Define Size of a graph wih example 1

Solution:The size of a graph is the number of edges, typically denoted by m=|E|.

The size of a graph = 3

36 Define Order of a graph wih example 1
Solution:The order of a graph is thenumber of vertices, usually denoted by n = |V|.

The order of a graph = 3

37 Define Cener of a graph wih example 1
Solution: The set of all central points of 'G' is called the center of the Graph.

DMGT (BE04000261) Page | 22

 Semester: IV (2025-26)

Cener of a graph = 1
 MATRIX REPRESENTATION OF GRAPHS
DESCRIPTIVE QUESTIONS
1 Define adjacency matrix and path matrix of a graph. Find out adjacency matrix for the 4
graph given in figure(Dec–2022)

Solution:

Adjacency Matrix of a Graph:

The adjacency matrix A = [𝑎𝑖𝑗 ]for a graph G with n vertices is an n × n matrix defined by

 For Non- Directed Simple Graph

𝑎𝑖𝑗 = 1 If vertex 𝑉𝑖 is adjacent to 𝑉𝑗

= 0 otherwise
 For Pseudo/Multi Graph
𝑎𝑖𝑗 = 𝑘 ,k is vertex 𝑉𝑖 is adjacent to 𝑉𝑗

= 0 otherwise
 For Directed Graph:
𝑎𝑖𝑗 = 1 If edge beginning at vertex 𝑉𝑖 end at 𝑉𝑗

= 0 otherwise

Path Matrix (Reachability Matrix):

The Path matrix P = [𝑝𝑖𝑗 ]for a directed graph G with n vertices is an n × n matrix defined by
𝑝𝑖𝑗 = 1 If there exists a path from 𝑝𝑖 to 𝑝𝑗

= 0 otherwise

The adjacency matrix of graph G

𝟎 𝟏 𝟎 𝟎 𝟎 𝟎
𝟏 𝟎 𝟐 𝟏 𝟎 𝟎
𝑨= 𝟎 𝟐 𝟎 𝟏 𝟎 𝟎
𝟎 𝟏 𝟏 𝟎 𝟏 𝟎
𝟎 𝟎 𝟎 𝟏 𝟎 𝟑
[𝟎 𝟎 𝟎 𝟎 𝟑 𝟎]

2 1) Define incidence Matrix of a Graph 4

2) Find incidence matrix for the following graph
DMGT (BE04000261) Page | 23
 Semester: IV (2025-26)

Solution:

(1) Incidence Matrix of Non-directed Graph:

Let G be a non-directed graph with n vertices and m edges. The incidence matrix of graph G is
M = [𝑚𝑖𝑗 ] of order n× mand is defined by

1, If vertex 𝑣𝑖 is incident on edge 𝑒𝑗

𝑚𝑖𝑗 = {
0, 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

(2)Incidence Matrix of directed Graph:

Let G be a directed graph with n vertices and m edges. The incidence matrix of graph G is M =
[𝑚𝑖𝑗 ] of order n× mand is defined by

1, If vertex 𝑣𝑖 is the initial vertex of edge 𝑒𝑗

𝑚𝑖𝑗 = { (−1), If vertex 𝑣𝑖 is the end vertex of edge 𝑒𝑗
0 If vertex 𝑣𝑖 is not incident on edge 𝑒𝑗

𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔 ℎ
𝑣1 0 0 0 1 0 1 0 0
𝑣2 0 0 0 0 1 1 1 1
𝑣
𝑀 = 𝑣3 0 0 0 0 0 0 0 1
4
𝑣5 1 1 1 0 1 0 0 0
𝑣6 0 0 1 1 0 0 1 0
[1 1 0 0 0 0 0 0]

3 Draw the non-directed multigraph corresponding to each of the following 3

adjacency matrices

DMGT (BE04000261) Page | 24

 Semester: IV (2025-26)

𝟏 𝟏 𝟏 𝟐
[𝟏 𝟎 𝟎 𝟎]
𝟏 𝟎 𝟎 𝟐
𝟐 𝟎 𝟐 𝟐
Solution:

4 Draw di-graph and find in-degree and out-degree of each vertex from the given 7
adjacency matrix. Use adjacency matrix, find total no. of path of length 1 and 2 between
each vertex.
𝟏 𝟏 𝟏
𝐀 = [𝟏 𝟏 𝟏 ]
𝟏 𝟏 𝟏

Solution:Directed Graph / Digraph:

A graph in which every edge is directed is called a directed graph (Digraph)

Digraph of adjacency matrix

VERTEX IN DEGREE OUT DEGREE TOTAL DEGREE

𝒂 3 3 6

𝒃 3 3 6

𝒄 3 3 6

Path of Length 1
(𝟏)𝒗𝟏 − 𝒗𝟐 (𝟐)𝒗𝟐 − 𝒗𝟏 (𝟑)𝒗𝟏 − 𝒗𝟑 (𝟒)𝒗𝟑 − 𝒗𝟏 (𝟓)𝒗𝟑 − 𝒗𝟐 (𝟔)𝒗𝟐 − 𝒗𝟑

Path of Length 2
(𝟏)𝒗𝟏 − 𝒗𝟐 − 𝒗𝟏 (𝟐)𝒗𝟐 − 𝒗𝟏 − 𝒗𝟐 (𝟑)𝒗𝟏 − 𝒗𝟑 − 𝒗𝟏 (𝟒)𝒗𝟑 − 𝒗𝟏 − 𝒗𝟑
(𝟓)𝒗𝟑 − 𝒗𝟐 − 𝒗𝟑 (𝟔)𝒗𝟐 − 𝒗𝟑 − 𝒗𝟐

5 Define adjacency matrix of a digraph. Obtain the adjacency matrix A of the given 7
digraph. Find the elementary paths of lengths 1 and 2 from v1 to v4 .

DMGT (BE04000261) Page | 25

 Semester: IV (2025-26)

Solution:
Adjacency Matrix of directed Graph:
The adjacency matrix A = [𝑎𝑖𝑗 ]for a directed graph G with n vertices is an n × n matrix defined by

𝑎𝑖𝑗 = 1 If edge beginning at vertex 𝑉𝑖 end at 𝑉𝑗

= 0 otherwise

The adjacency matrix of Digraph G

0 1 0 1
0 0 1 1
A= 
0 1 0 1
 
0 1 0 0

Elementary path of length 1 from vertex 𝒗𝟏 to 𝒗𝟒

𝒗𝟏 - 𝒗𝟒
Elementary path of length 2 from vertex 𝒗𝟏 to 𝒗𝟒
𝒗𝟏 − 𝒗𝟐 − 𝒗𝟒
6 Define Adjacency matrix and path matrix of a graph. Explain each with example. 4
Solution:
Adjacency Matrix of a Graph:

The adjacency matrix A = [𝑎𝑖𝑗 ]for a graph G with n vertices is an n × n matrix defined by

 For Non- Directed Simple Graph

𝑎𝑖𝑗 = 1 If vertex 𝑉𝑖 is adjacent to 𝑉𝑗

= 0 otherwise
 For Pseudo/Multi Graph

𝑎𝑖𝑗 = 𝑘 ,k is vertex 𝑉𝑖 is adjacent to 𝑉𝑗

= 0 otherwise
 For Directed Graph:

𝑎𝑖𝑗 = 1 If edge beginning at vertex 𝑉𝑖 end at 𝑉𝑗

= 0 otherwise

Path Matrix(Reachability Matrix):

DMGT (BE04000261) Page | 26

 Semester: IV (2025-26)

The Path matrix P = [𝑝𝑖𝑗 ]for a directed graph G with n vertices is an n × n matrix defined by

𝑝𝑖𝑗 = 1 If there exists a path from 𝑝𝑖 to 𝑝𝑗

= 0 otherwise

The adjacency matrix of Digraph G

0 0 0 1
1 0 0 0
A= 
1 1 0 1
 
0 1 1 0

= 0 otherwise

. The War shall Algorithm is often used to compute the path matrix.

The Path matrix of Digraph G

1 1 1 1
1 1 1 1
P= 
1 1 1 1
 
1 1 1 1

Key difference between Adjacency Matrix and Path Matrix is that

 An adjacency matrix is about direct edge

 Where a path matrix is about whether can be traveled or not.

 Path matrix include both direct and indirect edges.

7 Define adjacency matrix of a graph and obtain the adjacency matrix (A) for the following 4
graph. State the in degree and out degree of all the vertices.

DMGT (BE04000261) Page | 27

 Semester: IV (2025-26)

Solution:

Adjacency Matrix of a Graph:

The adjacency matrix A = [𝑎𝑖𝑗 ]for a graph G with n vertices is an n × n matrix defined by

 For Non- Directed Simple Graph

𝑎𝑖𝑗 = 1 If vertex 𝑉𝑖 is adjacent to 𝑉𝑗

= 0 otherwise
 For Pseudo/Multi Graph

𝑎𝑖𝑗 = 𝑘 ,k is vertex 𝑉𝑖 is adjacent to 𝑉𝑗

= 0 otherwise
 For Directed Graph:

𝑎𝑖𝑗 = 1 If edge beginning at vertex 𝑉𝑖 end at 𝑉𝑗

= 0 otherwise

(2)The adjacency matrix of Digraph G

0 0 0 1
1 0 0 0
A= 
1 1 0 1
 
0 1 1 0

In Graph G

Vertex In degree Out degree

𝒗𝟏 𝑑𝑒𝑔+ (𝒗𝟏 ) = 𝟐 𝑑𝑒𝑔− (𝒗𝟏 ) = 𝟏

𝒗𝟐 𝑑𝑒𝑔+ (𝒗𝟐 ) = 𝟐 𝑑𝑒𝑔− (𝒗𝟐 ) = 𝟏

𝒗𝟑 𝑑𝑒𝑔+ (𝒗𝟑 ) = 𝟏 𝑑𝑒𝑔− (𝒗𝟑 ) = 𝟑

𝒗𝟒 𝑑𝑒𝑔+ (𝒗𝟒 ) = 𝟐 𝑑𝑒𝑔− (𝒗𝟒 ) = 𝟐

8 Define adjacency matrix and find the same for (Feb–2021) (Feb–2021) 4

Solution:
Adjacency Matrix of a Graph:
The adjacency matrix A = [𝑎𝑖𝑗 ]for a graph G with n vertices is an n × n matrix defined by

 For Non- Directed Simple Graph

DMGT (BE04000261) Page | 28

 Semester: IV (2025-26)

𝑎𝑖𝑗 = 1 If vertex 𝑉𝑖 is adjacent to 𝑉𝑗

= 0 otherwise
 For Pseudo/Multi Graph

𝑎𝑖𝑗 = 𝑘 ,k is vertex 𝑉𝑖 is adjacent to 𝑉𝑗

= 0 otherwise
 For Directed Graph:

𝑎𝑖𝑗 = 1 If edge beginning at vertex 𝑉𝑖 end at 𝑉𝑗

= 0 otherwise
(2)The adjacency matrix of simple graph G

0 1 1 1 0
1 0 1 0 0

A = 1 1 0 1 0
 
1 0 1 0 1
0 0 0 1 0

9 Draw a graph with the adjacency matrix 3

𝟎 𝟏 𝟏 𝟎
[𝟏 𝟎 𝟎 𝟏]
𝟏 𝟎 𝟎 𝟏
𝟎 𝟏 𝟏 𝟎

with respect to the ordering of vertices a, b, c, d.

Solution:

10 Use an adjacency matrix to represent the pseudograph shown in Figure 3

Solution:

The adjacency matrix using the ordering of vertices a, b, c, d is

𝑎 𝑏 𝑐 𝑑

DMGT (BE04000261) Page | 29

 Semester: IV (2025-26)

𝒂 𝟎 𝟑 𝟎 𝟐
𝑨=𝒃 𝟑
𝒄 [𝟎
𝟎 𝟏 𝟏]
𝟏 𝟏 𝟐
𝒅 𝟐 𝟏 𝟐 𝟎

11 Represent the graph shown in Figure with an incidence matrix. 7

Solution:The incidence matrix is

12 Define Boolean Matrix (Bit) 1

Solution:A Boolean Matrix is a real matrix whose entries are either 0 or 1.

 The Binary digits (Bits) are the symbols 0 and 1.

+ 0 1
0 0 1
1 1 1

× 0 1
0 0 0
1 0 1

13 Represent the pseudo graph shown in Figure using an incidence matrix 7

Solution:
The incidence matrix is

DMGT (BE04000261) Page | 30

 Semester: IV (2025-26)

 ISOMORPHIC GRAPHS
1 Define Isomorphic graph with example 3
Solution: Two graphs G1 and G2 are said to be isomorphic if −
 Their number of vertices are same.
 Their number of edges are same.
 If𝑮𝟏 has n vertices of degree k then 𝑮𝟐 has n vertices of degree k.
 Adjacency is preserved.
Example:

(2) Graphs G and H are isomorphic.

DMGT (BE04000261) Page | 31

 Semester: IV (2025-26)

(1)|V(G)| = |V(H)| = 5
(2)|E(G)| = |E(H)| = 5

In graph G In graph H
d(y) = 2
d(a) = 2
d(b) = 2 d(v) = 2

d(c) = 2 d(x) = 2

d(d) = 2 d(z) = 2

d(e) = 2 d(w) = 2

(3) Adjacency is also preserved

Hence, G is isomorphic to H

2 Define Isomorphic graphs. What are the necessary conditions for two graphs to be 4
isomorphic? Are they sufficient also? Justify your answer
Solution:
Two graphs G1 and G2 are said to be isomorphic if −
 Their number of vertices are same.
 Their number of edges are same.
 If𝑮𝟏 has n vertices of degree k then 𝑮𝟐 has n vertices of degree k.
 Adjacency is preserved.

Necessary conditions for the graphs G1 and G2 to be isomorphic

If G1 ≡ G2 then
(1)|V(G1)| = |V(G2)|
(2)|E(G1)| = |E(G2)|
(3)Degree sequences of G1 and G2 are same.
If the vertices {𝑣1 ,𝑣2 , …𝑣𝑘 } form a cycle of length k in G1, then the vertices {f(𝑣1 ), f(𝑣2 ),…
f(𝑣𝑘 )} should form a cycle of length k in G2.
All the above conditions are necessary for the graphs G1 and G2 to be isomorphic, but not
sufficient to prove that the graphs are isomorphic.

DMGT (BE04000261) Page | 32

 Semester: IV (2025-26)

Sufficient conditions for the graphs G1 and G2 to be isomorphic.

 The adjacency matrices of G1 and G2 are same.
 Their complement graphs are isomorphic.
The corresponding sub graphs of G1 and G2 are isomorphic.(Obtained by deleting some
vertices in G1 and their images in graph G2)

3 Give an abstract definition of graph. When are two simple graphs said to be isomorphic? 7
Give an example of two simple digraphs having 4 nodes and 4 edges which are not
isomorphic

Solution: Graph:
Let V be the non-empty set of point and E be the set of lines between points, then

Ordered pair (V, E) is known as graph.

 Two graphs G1 and G2 are said to be isomorphic if −

 Their number of vertices are same.. i.e. |V(G1)| = |V(G2)|
 Their number of edges are same. i.e. |E(G1)| = |E(G2)|
 An equal number of vertices with given degree
 Adjacency is preserved

An example of two simple digraphs having 4 nodes and 4 edges which are not isomorphic

Graph G1 Graph G2

To check Isomorphism:
(1) |V(G1)| = |V(G2)| = 4
(2) |E(G1)| = |E(G2)| = 4
(3) To checkAdjacency:
In Graph G1

Vertex In degree Out degree

A 𝑑𝑒𝑔+ (𝑨) = 𝟎 𝑑𝑒𝑔− (𝑨) = 𝟑

B 𝑑𝑒𝑔+ (𝑩) = 𝟏 𝑑𝑒𝑔− (𝑩) = 𝟎

DMGT (BE04000261) Page | 33

 Semester: IV (2025-26)

C 𝑑𝑒𝑔+ (𝑪) = 𝟏 𝑑𝑒𝑔− (𝑪) = 𝟏

D 𝑑𝑒𝑔+ (𝑫) = 𝟐 𝑑𝑒𝑔− (𝑫) = 𝟎

In Graph G2

Vertex In degree Out degree

A 𝑑𝑒𝑔+ (𝑨) = 𝟎 𝑑𝑒𝑔− (𝑨) = 𝟐

B 𝑑𝑒𝑔+ (𝑩) = 𝟏 𝑑𝑒𝑔− (𝑩) = 𝟏

C 𝑑𝑒𝑔+ (𝑪) = 𝟏 𝑑𝑒𝑔− (𝑪) = 𝟏

D 𝑑𝑒𝑔+ (𝑫) = 𝟐 𝑑𝑒𝑔− (𝑫) = 𝟎

In graph 𝑮𝟏

No. of vertices having 0 in degree and 3 out degree =1

No. of vertices having 1in degree and 0 out degree =1
No. of vertices having 1in degree and 1 out degree=1
No. of vertices having 2 in degree and o out degree=1

In graph 𝑮𝟐

No. of vertices having 0 in degree and 2 out degree =1

No. of vertices having 1in degree and 1 out degree=2
No. of vertices having 2 in degree and o out degree=1

Adjacency is not preserved,

So, G1 and G2 are not isomorphic

4 Define isomorphic graphs. State whether the following graphs are isomorphic or not. 4

Solution: Isomorphic graphs Two graphs G1 and G2 are said to be isomorphic if −

 Their number of vertices are same. . i.e. |V(G1)| = |V(G2)|
 Their number of edges are same. i.e. |E(G1)| = |E(G2)|
 An equal number of vertices with given degree
 Adjacency is preserved

DMGT (BE04000261) Page | 34

 Semester: IV (2025-26)

Notation: G1 ≡ G2
To check Isomorphism:
(1) |V(G1)| = |V(G2) |= 5
(2) |E(G1)| = |E(G2)| = 6
(3) To check Adjacency:

In Graph 𝑮𝟏 In Graph 𝑮𝟐

𝒅(𝒖𝟏 ) = 𝟐 𝒅(𝒗𝟏 ) = 𝟐
𝒅(𝒖𝟐 ) = 𝟐
𝒅(𝒗𝟐 ) = 𝟒
𝒅(𝒖𝟑 ) = 𝟑
𝒅(𝒗𝟑 ) = 𝟑
𝒅(𝒖𝟒 ) = 𝟑
𝒅(𝒗𝟒 ) = 𝟏
𝒅(𝒖𝟓 ) = 𝟐
𝒅(𝒗𝟓 ) = 𝟐

In graph 𝑮𝟏
No. of vertices having 3 degree=2
No. of vertices having 2 degree=3

In graph 𝑮𝟐
No. of vertices having 4 degree=1
No. of vertices having 3 degree=1
No. of vertices having 2 degree=2
No. of vertices having 1 degree=1
Adjacency is not preserved,

So, G1 and G2 are not isomorphic.

5 Define isomorphic graphs. State whether the following digraphs are Isomorphic or not. 7
Justify your answer.

Solution:Two graphs G1 and G2 are said to be isomorphic if −

 Their number of vertices are same.. i.e. |V(G1)| = |V(G2)|
 Their number of edges are same. i.e. |E(G1)| = |E(G2)|
 An equal number of vertices with given degree
 Adjacency is preserved
To check Isomorphism:
(4) |V(G1)| = |V(G2)| = 6
(5) |E(G1)| = |E(G2)| = 9

DMGT (BE04000261) Page | 35

 Semester: IV (2025-26)

(6) To check Adjacency:

In Graph G1
Vertex In degree Out degree

𝒖𝟏 𝑑𝑒𝑔+ (𝒖𝟏 ) = 𝟎 𝑑𝑒𝑔− (𝒖𝟏 ) = 𝟑

𝒖𝟐 𝑑𝑒𝑔+ (𝒖𝟐 ) = 𝟑 𝑑𝑒𝑔− (𝒖𝟐 ) = 𝟎

𝒖𝟑 𝑑𝑒𝑔+ (𝒖𝟑 ) = 𝟎 𝑑𝑒𝑔− (𝒖𝟑 ) = 𝟑

𝒖𝟒 𝑑𝑒𝑔+ (𝒖𝟒 ) = 𝟑 𝑑𝑒𝑔− (𝒖𝟒 ) = 𝟎

𝒖𝟓 𝑑𝑒𝑔+ (𝒖𝟓 ) = 𝟎 𝑑𝑒𝑔− (𝒖𝟓 ) = 𝟑

𝒖𝟔 𝑑𝑒𝑔+ (𝒖𝟔 ) = 𝟑 𝑑𝑒𝑔− (𝒖𝟔 ) = 𝟎

In Graph G2
Vertex In degree Out degree

𝒗𝟏 𝑑𝑒𝑔+ (𝒗𝟏 ) = 𝟎 𝑑𝑒𝑔− (𝒗𝟏 ) = 𝟑

𝒗𝟐 𝑑𝑒𝑔+ (𝒗𝟐 ) = 𝟑 𝑑𝑒𝑔− (𝒗𝟐 ) = 𝟎

𝒗𝟑 𝑑𝑒𝑔+ (𝒗𝟑 ) = 𝟎 𝑑𝑒𝑔− (𝒗𝟑 ) = 𝟑

𝒗𝟒 𝑑𝑒𝑔+ (𝒗𝟒 ) = 𝟑 𝑑𝑒𝑔− (𝒗𝟒 ) = 𝟎

𝒗𝟓 𝑑𝑒𝑔+ (𝒗𝟓 ) = 𝟎 𝑑𝑒𝑔− (𝒗𝟓 ) = 𝟑

𝒗𝟔 𝑑𝑒𝑔+ (𝒗𝟔 ) = 𝟑 𝑑𝑒𝑔− (𝒗𝟔 ) = 𝟎

𝑢1 is correspondent to 𝑣1
𝑢2 is correspondent to 𝑣2
𝑢3 is correspondent to 𝑣3
𝑢4 is correspondent to 𝑣4
𝑢5 is correspondent to 𝑣5
𝑢6 is correspondent to 𝑣6
Adjacency is preserved

So, G1 and G2 are isomorphic.

6 Define Isomorphic Graphs. Verify the following graphs are Isomorphic or not (Justify). 7

DMGT (BE04000261) Page | 36

 Semester: IV (2025-26)

Solution: Two graphs G1 and G2 are said to be isomorphic if −

 Their number of vertices are same. . i.e. |V(G1)| = |V(G2)|
 Their number of edges are same. i.e. |E(G1)| = |E(G2)|
 An equal number of vertices with given degree
 Adjacency is preserved
Notation: G1 ≡ G2
Condition-01:
 Number of vertices in graph G1 = 8
 Number of vertices in graph G2 = 8
 Both the graphs G1 and G2 have same number of vertices.
 So, Condition-01 satisfies
Condition-02:
 Number of edges in graph G1 = 10
 Number of edges in graph G2 = 10
 Both the graphs G1 and G2 have same number of edges.
 So, Condition-02 satisfies.
Condition-03:
 In G1, degree-3 vertices form a cycle of length 4.
 In G2, degree-3 vertices do not form a 4-cycle as the vertices are not adjacent.
 Both the graphs G1 and G2 do not contain same cycles in them.
 So, Condition-03 violates.
So given graphs cannot be isomorphic.
OR

DMGT (BE04000261) Page | 37

 Semester: IV (2025-26)

6 Define isomorphism of graphs and find whether K 6 and K3,3graphsare isomorphic or not. 5

Solution:
Two graphs G1 and G2 are said to be isomorphic if −
 Their number of vertices are same. . i.e. |V(G1)| = |V(G2)|
 Their number of edges are same. i.e. |E(G1)| = |E(G2)|
 An equal number of vertices with given degree
 Adjacency is preserved
Notation: G1 ≡ G2
To check Isomorphism
𝑛(𝑛−1)
𝐾𝑛 has exactly edges
2

DMGT (BE04000261) Page | 38

 Semester: IV (2025-26)

6(6−1) 30
∴ 𝐾6 = = = 15
2 2

𝐾6 have 15 edges

All 6 vertices are of degree 5

𝐾𝑚 ,𝑛 has mn edges

∴ 𝐾3 ,3 𝑖𝑠 𝑎 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 𝑏𝑖𝑝𝑎𝑟𝑡𝑖𝑡𝑒 𝑔𝑟𝑎𝑝ℎ

∴ No. of edges = 3 × 3= 9

|E(G1)| ≠ |E(G2)|

Hence, K6 and K3,3 graphsare not isomorphic

7 1) Define Isomorphic Graphs 4

2) Verify the following graphs are Isomorphic or not (Justify).

DMGT (BE04000261) Page | 39

 Semester: IV (2025-26)

Solution:

(1)Isomorphic graphs: Two graphs G1 and G2 are said to be isomorphic if −

 Their number of vertices are same. . i.e. |V(G1)| = |V(G2)|
 Their number of edges are same. i.e. |E(G1)| = |E(G2)|
 An equal number of vertices with given degree
 Adjacency is preserved
Notation: G1 ≡ G2
To check Isomorphism:
(1)|V(G1)| = |V(G2) |= 6
(2) |E(G1)| = |E(G2)| = 5
(3)To check Adjacency:

In Graph 𝑮𝟏 In Graph 𝑮𝟐

𝒅(𝒙) = 𝟑 𝒅(𝒚) = 𝟑
𝒅(𝒖) = 𝟏
𝒅(𝒘) = 𝟏
𝒅(𝒗) = 𝟏

In graph 𝑮𝟏

We have a vertex 𝒙 of degree 3 , there are two pendent vertices u and v adjacent to x in
𝑮𝟏

But in graph 𝑮𝟐 ,

We have a vertex 𝒚 of degree 3 , there is one pendent vertex w adjacent to y in 𝑮𝟐

Adjacency is not preserved,

So, G1 and G2 are not isomorphic.

8 Define isomorphic graphs. State whether the following graphs are isomorphic or 4
not.

DMGT (BE04000261) Page | 40

 Semester: IV (2025-26)

Solution:
The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there exists a
Oneto-one and onto function f from V1 to V2 with the property that
aand b are adjacent in G1 ifand only if f (a) and f (b) are adjacent in G2, for all a ,bin V1. Such
a function f is calledanisomorphism
∗ Two simple graphs that are not isomorphic are called nonisomorphic.

1)|V(𝑮𝟏 )| = |V(𝑮𝟐 )| = 8
(2)|E(𝑮𝟏 )| = |E(𝑮𝟐 )| = 10
(3)To check Adjacency:

In Graph 𝑮𝟏 In Graph 𝑮𝟐
𝒅(𝒂) = 𝟑 𝒅 ( 𝟏) = 𝟑
𝒅(𝒃) = 𝟐 𝒅 ( 𝟐) = 𝟐
𝒅(𝒄) = 𝟑 𝒅 ( 𝟑) = 𝟑
𝒅(𝒅) = 𝟐 𝒅 ( 𝟒) = 𝟐
𝒅(𝒆) = 𝟑 𝒅 ( 𝟓) = 𝟑
𝒅(𝒇) = 𝟐 𝒅 ( 𝟔) = 𝟐
𝒅 ( 𝒈) = 𝟑 𝒅 ( 𝟕) = 𝟑
𝒅(𝒉) = 𝟐 𝒅 ( 𝟖) = 𝟐

In graph 𝑮𝟏
No. of vertices having 3 degrees=4
No. of vertices having 2 degrees=4
In graph 𝑮𝟐
No. of vertices having 3 degrees=4
No. of vertices having 2 degrees=4
(4)The function f with
f (a) = 1, f (b) = 2, f (c) =3, f(d) = 4 ,
f (e) = 5, f (f) = 6, f (g) =7, f(h) = 8
is a one to-one correspondence between 𝑮𝟏 and 𝑮𝟐
These correspondence preserves adjacency
So, G1 and G2 are isomorphic.
9 Are the following graphs isomorphic? Justify your answer. 4

DMGT (BE04000261) Page | 41

 Semester: IV (2025-26)

Solution:
1)|V(E)| = |V(F)| = 6
(2)|E(E)| = |E(F)| = 8
(3) The degree sequence of E is 2 − 3 − 3 − 2 − 3 − 3 − 2
The degree sequence of F is 2 − 3 − 3 − 2 − 3 − 3 − 2
(4)Graph E contain 2 cycle of length 3→ 𝑣1 − 𝑣2 − 𝑣6 𝑎𝑛𝑑 𝑣3 − 𝑣4 − 𝑣5
But graph F does not contain any cycle of length 3
So, E is not isomorphic to F

10 Show that the graphs G = (V, E) and H = (W, F) are isomorphic.

Solution:
1)|V(G)| = |V(H)| = 4
(2)|E(G)| = |E(H)| = 8
(3) The degree sequence of G is 2 − 2 − 2 − 2
The degree sequence of H is 2 − 2 − 2 − 2
(4)Graph G contain 1 cycle of length 4→ 𝑢1 − 𝑢2 − 𝑢3 − 𝑢4
And graph H also contain 1 cycle of length 4→ 𝑣1 − 𝑣4 − 𝑣2 − 𝑣3
So, G is isomorphic to H

11 Determine whether the graphs G and H displayed in Figure are isomorphic.

DMGT (BE04000261) Page | 42

 Semester: IV (2025-26)

Solution:
1)|V(G)| = |V(H)| = 6
(2)|E(G)| = |E(H)| = 7
(3) To check Adjacency:

In Graph G In Graph H

𝒅(𝒖𝟏 ) = 𝟐 𝒅(𝒗𝟏 ) = 𝟐
𝒅(𝒖𝟐 ) = 𝟑
𝒅(𝒗𝟐 ) = 𝟐
𝒅(𝒖𝟑 ) = 𝟐
𝒅(𝒗𝟑 ) = 𝟑
𝒅(𝒖𝟒 ) = 𝟑
𝒅(𝒗𝟒 ) = 𝟐
𝒅(𝒖𝟓 ) = 𝟐
𝒅(𝒗𝟓 ) = 𝟑
𝒅(𝒖𝟔 ) = 𝟐
𝒅(𝒗𝟔 ) = 𝟐

In graph G
No. of vertices having 3 degree=2
No. of vertices having 2 degree=4

In graph 𝑯
No. of vertices having 3 degree=2
No. of vertices having 2 degree=4

We now will define a function f and then determine whether it is an isomorphism.

Becausedeg(u1) = 2 and because u1 is not adjacent to any other vertex of degree two,
the image of u1 must be either v4 or v6, the only vertices of degree two in H not adjacent to a
vertex of degreetwo.
We arbitrarily set f (u1) = v6.
Because u2 is adjacent to u1, the possible images of u2 are v3 and v5.
We arbitrarily set f (u2) = v3.
Continuing in this way, using adjacency of vertices and degrees
f (u3) = v4,

DMGT (BE04000261) Page | 43

 Semester: IV (2025-26)

f (u4) = v5,
f (u5) = v1, and
f (u6) = v2.
We now have a one-to-one correspondence between the vertex set of G and the vertex set of H,
namely,
f (u1) = v6,
f (u2) = v3,
f (u3) = v4,
f (u4) = v5,
f (u5) = v1,
f (u6) = v2.
To see whether f preserves edges, we examine the adjacency matrix of G,

and the adjacency matrix of H with the rows and columns labelled by the images of the
corresponding vertices in G

Because AG = AH,

it follows that f preserves edges. We conclude that f is an isomorphism,

So G and H are isomorphic.

12 Check wheher the following graphs are isomorphic 4

DMGT (BE04000261) Page | 44

 Semester: IV (2025-26)

(Feb–2024)
Solution: To check Isomorphism:
 |V(G1)| = |V(G2)| = 6
 |E(G1)| = |E(G2)| = 9
 To checkAdjacency:
In Graph H
Vertex In degree Out degree
𝒂 𝑑𝑒𝑔+ (𝒂) = 𝟎 𝑑𝑒𝑔− (𝒂) = 𝟑
𝒃 𝑑𝑒𝑔+ (𝒃) = 𝟑 𝑑𝑒𝑔− (𝒃) = 𝟎
𝒄 𝑑𝑒𝑔+ (𝒄) = 𝟎 𝑑𝑒𝑔− (𝒄) = 𝟑
𝒅 𝑑𝑒𝑔+ (𝒅) = 𝟑 𝑑𝑒𝑔− (𝒅) = 𝟎
𝒆 𝑑𝑒𝑔+ (𝒆) = 𝟎 𝑑𝑒𝑔− (𝒆) = 𝟑
𝒇 𝑑𝑒𝑔+ (𝒇) = 𝟑 𝑑𝑒𝑔− (𝒇) = 𝟎
In Graph G
Vertex In degree Out degree
𝒗𝟏 𝑑𝑒𝑔+ (𝒗𝟏 ) = 𝟎 𝑑𝑒𝑔− (𝒗𝟏 ) = 𝟑
𝒗𝟐 𝑑𝑒𝑔+ (𝒗𝟐 ) = 𝟑 𝑑𝑒𝑔− (𝒗𝟐 ) = 𝟎
𝒗𝟑 𝑑𝑒𝑔+ (𝒗𝟑 ) = 𝟎 𝑑𝑒𝑔− (𝒗𝟑 ) = 𝟑
𝒗𝟒 𝑑𝑒𝑔+ (𝒗𝟒 ) = 𝟑 𝑑𝑒𝑔− (𝒗𝟒 ) = 𝟎

𝒗𝟓 𝑑𝑒𝑔+ (𝒗𝟓 ) = 𝟎 𝑑𝑒𝑔− (𝒗𝟓 ) = 𝟑

𝒗𝟔 𝑑𝑒𝑔+ (𝒗𝟔 ) = 𝟑 𝑑𝑒𝑔− (𝒗𝟔 ) = 𝟎
𝑎 is correspondent to 𝑣1
𝑏 is correspondent to 𝑣2
𝑐 is correspondent to 𝑣3
𝑑 is correspondent to 𝑣4
𝑒 is correspondent to 𝑣5
𝑓 is correspondent to 𝑣6
Adjacency is preserved

So, H and G are isomorphic

13 Define isomorphic graphs. Determine whether the following graphs are isomorphic or 7
not.

DMGT (BE04000261) Page | 45

 Semester: IV (2025-26)

(Jul–2023)
Solution:
1)|V(G)| = |V(H)| = 5
(2)|E(G)| = |E(H)| = 6
(3)To check Adjacency:

In Graph G In Graph H

𝒅(𝒂) = 𝟑 𝒅 ( 𝟏) = 𝟑
𝒅(𝒃) = 𝟐
𝒅 ( 𝟐) = 𝟐
𝒅(𝒄) = 𝟑
𝒅 ( 𝟑) = 𝟑
𝒅(𝒅) = 𝟑
𝒅 ( 𝟒) = 𝟑
𝒅(𝒆) = 𝟏
𝒅 ( 𝟓) = 𝟏

𝑽𝟏 = {𝒂, 𝒃, 𝒄, 𝒅, 𝒆}and
𝑉2 = {1, 2, 3, 4, 5}
Define 𝑓: 𝑉1 → 𝑉2 by
𝑓(𝑎) = 1,
𝑓(𝑏) = 2,
𝑓(𝑐 ) = 3,
𝑓(𝑑) = 4 and
𝑓(𝑒) = 5
Then, f is one-one correspondence.

0 1 1 1 0
1 0 1 0 1
𝐴𝐺 = 1 1 0 1 0 = 𝐴𝐻
1 0 1 0 1
[0 0 0 1 0]
It follows that 𝐺 ≅ 𝐻
14 Define isomorphic graphs. Determine whether the following graphs are isomorphic or not. 7

DMGT (BE04000261) Page | 46

 Semester: IV (2025-26)

.
Solution:
Isomorphic graphs: Two graphs G1 and G2 are said to be isomorphic if −
 Their number of vertices are same. . i.e. |V(G1)| = |V(G2)|
 Their number of edges are same. i.e. |E(G1)| = |E(G2)|
 An equal number of vertices with given degree
 Adjacency is preserved
Notation: G1 ≡ G2
1)|V(G)| = |V(H)| = 5
(2)|E(G)| = |E(H)| = 5
(3)To check Adjacency:

In Graph 𝑮𝟏 In Graph 𝑮𝟐

𝒅 ( 𝟏) = 𝟐 𝒅 ( 𝟏) = 𝟐
𝒅 ( 𝟐) = 𝟐
𝒅 ( 𝟐) = 𝟐
𝒅 ( 𝟑) = 𝟐
𝒅 ( 𝟑) = 𝟐
𝒅 ( 𝟒) = 𝟐
𝒅 ( 𝟒) = 𝟐
𝒅 ( 𝟓) = 𝟐
𝒅 ( 𝟓) = 𝟐

Adjacency is also preserved as all vertices are having same degree.

So, G1 ≡ G2

15 Define isomorphic graphs. Check whether the following graphs are isomorphic? 7

(Jul–2023)
Solution:
To check Isomorphism:
 |V(G1)| = |V(G2)| = 6
DMGT (BE04000261) Page | 47
 Semester: IV (2025-26)

 |E(G1)| = |E(G2)| = 9
 To checkAdjacency:
In Graph G
Vertex In degree Out degree

𝟏 𝑑𝑒𝑔+ (𝟏) = 𝟑 𝑑𝑒𝑔− (𝟏) = 𝟎

2 𝑑𝑒𝑔+ (𝟐) = 𝟎 𝑑𝑒𝑔− (𝟐) = 𝟑

𝟑 𝑑𝑒𝑔+ (𝟑) = 𝟑 𝑑𝑒𝑔− (𝟑) = 𝟎

𝟒 𝑑𝑒𝑔+ (𝟒) = 𝟎 𝑑𝑒𝑔− (𝟒) = 𝟑

𝟓 𝑑𝑒𝑔+ (𝟓) = 𝟑 𝑑𝑒𝑔− (𝟓) = 𝟎

𝟔 𝑑𝑒𝑔+ (𝟔) = 𝟎 𝑑𝑒𝑔− (𝟔) = 𝟑

In Graph H
Vertex In degree Out degree

𝒂 𝑑𝑒𝑔+ (𝒂) = 𝟑 𝑑𝑒𝑔− (𝒂) = 𝟎

𝒃 𝑑𝑒𝑔+ (𝒃) = 𝟎 𝑑𝑒𝑔− (𝒃) = 𝟑

𝒄 𝑑𝑒𝑔+ (𝒄) = 𝟑 𝑑𝑒𝑔− (𝒄) = 𝟎

𝒅 𝑑𝑒𝑔+ (𝒅) = 𝟎 𝑑𝑒𝑔− (𝒅) = 𝟑

𝒆 𝑑𝑒𝑔+ (𝒆) = 𝟑 𝑑𝑒𝑔− (𝒆) = 𝟎

𝒇 𝑑𝑒𝑔+ (𝒇) = 𝟎 𝑑𝑒𝑔− (𝒇) = 𝟑

𝑎 is correspondent to 1
𝑏 is correspondent to 2
𝑐 is correspondent to 3
𝑑 is correspondent to 4
𝑒 is correspondent to 5
𝑓 is correspondent to 6
Adjacency is preserved

So, H and G are isomorphic

 SUB GRAPHS
SHORT QUESTIONS
1 Define sub graph. 1

Solution:

DMGT (BE04000261) Page | 48

 Semester: IV (2025-26)

Sub graph:

If G = (V,E) and H = ( V1 , E1 ) are two graphs such that V1 ⊆ V and E1  E then H is called a
sub graph of G.

Examples: (1)

A sub graph ofK5

(2)

Properties of Sub graph

(1) Every graph is a sub graph of it self

(2) Null graph obtained by deleting all edges of G is also a sub graph of G

(3) A single edge along with end vertices is also a sub graph of G

(4) A sub graph of a sub graph of a graph G is a sub graph of G

2 Define union and intersection of two graphs

Solution: 1

DMGT (BE04000261) Page | 49

 Semester: IV (2025-26)

3 Define induced sub graph 1

Solution:

A subgraph obtained from graph G by vertex deletion only is an induced subgraph of G.

If X is the set of deleted vertices, the induced subgraph is denoted G − X.
With Y = V (G) \ X, the induced subgraph is denoted G[Y ]
and called the subgraph of G induced by vertex set Y .

DESCRIPTIVE QUESTIONS
1 Explain converse (reverse) of a digraph with an example. 3
Solution:
Converse ( reversal/Directional dual) of a digraph:

The converse of a diagraph G =<V,E> to be a diagraph G  V, E  in which

 The relation E is the converse of the relation E.
 The diagram G is obtained from G by simply reversing the directions of the edges in G.
DMGT (BE04000261) Page | 50
 Semester: IV (2025-26)

The converse G is also called the reversal or directional dual of a diagraph G

2 Define sub-graph. Find all sub-graphs for the given graph. 7

Solution:
Sub graph: If G = (V,E) and H = ( V1 , E1 ) are two graphs such that V1 ⊆ V and E1  E
then H is called a sub graph of G.

3 Define vertex disjoint and edge disjoint sub graphs by drawing the relevant graphs. 4

Solution:

Disjoint sub graph – It is of two types

(i) Edge- disjoint sub graph and (ii) Vertex -disjoint sub graph.

DMGT (BE04000261) Page | 51

 Semester: IV (2025-26)

Edge- disjoint sub graph– (G-e)

Let G be a graph and 𝐺1and 𝐺2 be two sub graphs of G. Then 𝐺1and 𝐺2 are called edge disjoint
if they have no edge in common

Symbolically, E(𝐺1)∩E (𝐺2 ) = 

Vertex-disjoint sub graphs(G-V)

– Let G be a graph and𝐺1 and 𝐺2 be two sub graphs of G. Then𝐺1 and 𝐺2 are called vertex-
disjoint sub graph of G if they have no vertex in common.

Symbolically, V(𝐺1) ∩V(𝐺2 ) = 

Figure

4 Define complement of a sub graph by drawing the graphs. 4

Solution:Complement of a sub graph :

Let G be a graph and H be a sub graph of [Link] complement H in G is the graph obtained by
deleting the edges of H from those of G

(Complement of H in G is denoted by H )

DMGT (BE04000261) Page | 52

 Semester: IV (2025-26)

Graph G Sub graph H Complement of sub graph H = H

5 Define: Spanning Sub graph 3
Solution:
Spanning Sub graph
Consider the graph G(V,E). A spanning sub graph is a sub graph that contains all the vertices
of the original graph G
that is G'(V’,E’) is spanning if V’=V and E’ is a subset of E.
Example:

Note :
Suppose a graph G has n number of vertices (i.e., |V| = n)
and m number of edges (i.e., |E|=n)

Then, number of non-empty subsets of V as 2n - 1 and

Number of subsets of E as 2m.

Thus, the total number of non-empty sub graphs of G is (2n - 1) * 2m.

6 For the graph G draw the sub graphs 3

(a) G — e (here, e is one edge)

(b) G — a (here, a is one vertex)

Solution :The sub graphs are shown below

DMGT (BE04000261) Page | 53
 Semester: IV (2025-26)

G –e G – a
7 Draw some sub graph of the graph 3

Solution:

8 Define Complement of a set with suitable example. 3

Solution:
Complement of a graph :The complement G' of G is defined as a simple graph (parallel edge
and self-loop are ignored) with the same vertex set as G,
and where two vertices u and v are adjacent only when they are not
adjacent in G

 PATH
 A path in a graph is a sequence of vertices such that from each of its vertices there is an
edge to the next vertex in the sequence.
 Clearly, vertices as well as edges may be repeated in a path.
 A path from u to w is a sequence of edges
𝑢, 𝑣1 ,1, 𝑣2 … . , 𝑣𝑘-1, 𝑤connecting u with w.
 A path may be termed as walkalso.

DMGT (BE04000261) Page | 54

 Semester: IV (2025-26)

 The number of edges in a path is termed as its length of the path.

 (a, b), (b,b), (b, d), (d, c), (c, b), (b, d) is one path of the graph. and its length is 6.
 A path with no repeated vertex is called a simple path.
(a, b), (b, d), (d, c) is simple path.
 A path with no repeated edge is termed as trail.
 In a closed trail, the first and the last vertices are same.
 A closed path is a path that starts and ends at the same point, otherwise the
path is open.
 Edge repetition is allowed on the closed path.
(a, b), (b, d), (d, c),(c,a) is a closed path.
 A Cycle (circuit/tour) is a closed path of non-zero length that does not
contain any repeated edges. Vertices other than the end (i.e., start) vertex may
also be repeated.
 (a, b), (b, b), (b, d), (d, c),(c, a) is a cycle.
 A simple cycleis a cycle that does not have any repeated vertex except the
first and the last vertex.
 (a, b),(b, d), (d, c),(c, a) is an example of simple cycle.
 A graph without cycles is called acyclic.

SHORT QUESTIONS
1 Define Cyclic graph 1

Solution:
(1)Cyclic graph: A graph containing at least one cycle in it is called as a cyclic graph.

Examples-1

DMGT (BE04000261) Page | 55

 Semester: IV (2025-26)

Example-2

Here,
 This graph contains two cycles in it.
 Therefore, it is a cyclic graph.

2 Define circuit of a graph 1

Solution:
Circuit: (Cycle) : A closed path begin and ends at same vertex is called a circuit or elementary circuit

V0 , e1 , V1 , e2 ,..., Vn 1 , en , Vn . is circuit then V0  Vn

DESCRIPTIVE QUESTIONS
DMGT (BE04000261) Page | 56
 Semester: IV (2025-26)

1 Define a path in graph. Define length of the path. What is difference between a simple 3
path and an elementary path?

Solution:

(1) Path:

A path is a walk through a sequence of vertices V1  V2  V3  ...  Vn 1  Vn

 No. of edges in a path called the length of path.

 A loop can be included in a walk but not in path

(2) Length of a Path:

No. of edges in a path is called the length of path.

(1) Length of shortest circuit (if any) in G is called Girth of G, denoted by g(G)

(2) Length of longest circuit is called Circumference of G, denoted by C(G)

Difference between a simple path and an elementary path

A Simple Path:The path is called simple one if no edge is repeated in the path,

An Elementary Path:The path is called elementary one if no vertex is repeated in the path,

Naturally, every elementary path of a diagraph is also simple.

For example, let’s consider the graph:

Simple Path:

1−2−3

1−4−3

1−2−4−3

Elementary Path:

DMGT (BE04000261) Page | 57

 Semester: IV (2025-26)

1 − 2 − 3 ⇒ Length of path = 2

1 − 4 − 3 ⇒ Length of path = 2

1 − 2 − 4 − 3 ⇒ Length of path = 3

𝟏 − 𝟐 − 𝟒 − 𝟏 − 𝟒 − 𝟑 is simple but not elementary path

2 Define path and circuit of a graph by drawing the graphs

Explain Path and Circuit of a graph
Solution:
Path:A path is a walk through a sequence of vertices V1  V2  V3  ...  Vn 1  Vn

Without any repetition of vertices such a path is known as simple path.

Path:

𝑣1 − 𝑣2 − 𝑣3 − 𝑣4 − 𝑣5 is a path.

𝑣1 − 𝑣3 − 𝑣4 − 𝑣5 is a path.

Note:

(1) No. of edges in a path called the length of path.

(2) A loop can be included in a walk but not in path

Circuit: (Cycle)

A closed path begin and ends at same vertex is called a circuit or elementary circuit

V0 , e1 , V1 , e2 ,..., Vn 1 , en , Vn . is circuit then V0  Vn

Simple Circuit:

A circuit is said to be simple circuit if it does not include same edge twice

Elementary Circuit:

A circuit is said to be Elementary circuit if it does not include same vertex twice except the end
vertex.

DMGT (BE04000261) Page | 58

 Semester: IV (2025-26)

Circuit:

𝑣6 − 𝑣4 − 𝑣5 − 𝑣6

𝑣1 − 𝑣2 − 𝑣3 − 𝑣4 − 𝑣1

Example: 2

Note:

(1) Length of shortest circuit (if any) in G is called Girth of G, denoted by g(G).

(2) Length of longest circuit is called circumference of G, denoted by C(G)

TOPIC:2 REACHABILITY
DESCRIPTIVE QUESTIONS
1 Define Reachable set of a node𝐯. Find the reachable sets of (1) node 𝐯𝟏 and (2) node 𝐯𝟖 for 4
the digraph given in following Figure

Solution: Reachable set:A vertex V of a simple digraph is said to be reachable from the vertex
u of the same digraph, if there exists a path from u to v.

The set of vertices which are reachable from a given vertex v is said to be the reachable set of
V.

It is denoted by R(v).

𝑅(𝑣1 ) = 𝑅(𝑣2 ) = 𝑅 (𝑣3 ) = 𝑅(𝑣4 ) = 𝑅(𝑣5 ) = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 }

𝑅(𝑣8 ) = {𝑣8 , 𝑣7 , 𝑣6 }
DMGT (BE04000261) Page | 59
 Semester: IV (2025-26)

2 Define node base of a simple digraph. Find reachability set of all nodes for the following 7
diagraph.

Solution: Node Base: In a digraph G =< V,E> a subset X  V is called a node base if reachable set
of X is V and no proper subset of X has this property

Reachability set of all nodes

𝑅(𝑣1 ) = 𝑅(𝑣2 ) = 𝑅 (𝑣3 ) = 𝑅(𝑣4 ) = 𝑅(𝑣5 ) = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 }

𝑅(𝑣6 ) = {𝑣6 }

𝑅(𝑣7 ) = {𝑣7 , 𝑣6 }

𝑅(𝑣8 ) = {𝑣8 , 𝑣7 , 𝑣6 }

𝑅(𝑣9 ) = {𝑣9 }

𝑅(𝑣10 ) = {𝑣10 }

Node base: 𝑅(𝑣5 , 𝑣8 , 𝑣9 , 𝑣10 ) = 𝑉 = 𝑅 (𝑣1 , 𝑣8 , 𝑣9 , 𝑣10 )

3 Find node base of the following graph. 4

Node base: 𝑅(𝑣5 , 𝑣8 , 𝑣9 ) = 𝑉 = 𝑅 (𝑣1 , 𝑣8 , 𝑣9 )

4 Find node base of the following graph. 4

DMGT (BE04000261) Page | 60

 Semester: IV (2025-26)

Node base: 𝑉 = 𝑅(𝑢1 , 𝑢8 , 𝑢9 , 𝑢11, 𝑢13 , 𝑢14 )

5 Find the shortest path matrix between each pair of vertices for a digraph using 7

Wars hall’s Algorithm.

Solution:

DMGT (BE04000261) Page | 61

 Semester: IV (2025-26)

DMGT (BE04000261) Page | 62

 Semester: IV (2025-26)

DMGT (BE04000261) Page | 63

 Semester: IV (2025-26)

DMGT (BE04000261) Page | 64

 Semester: IV (2025-26)

6 Find the shortest path matrix between each pair of vertices for a digraph using 7
Warshall’s Algorithm.

Solution: As above

7 Explain geodesic with an example. 5

Solution:Geodesic:
If vertex V is reachable from the vertex u, then a path of minimum length from u to v is called
geodesic.

 The most familiar examples are the straight lines in Euclidean geometry.
 On a sphere, the images of geodesics are the great circles.
The shortest path from point A to point B on a sphere is given by the shorter arc of the great
circle passing through A and B.
PROCEDURE OF WARSHAL’S ALGORITHM TO FIND PATH MATRIX

DMGT (BE04000261) Page | 65

 Semester: IV (2025-26)

8 Use Warshall’s algorithm to obtain path matrix from the adjacency matrix of 4

Solution:

The adjacency matrix of digraph G

0 0 0 1 0
1 0 0 0 0
𝐴=𝑃= 0 1 0 0 0
0 1 1 0 0
[0 0 1 0 0]

0 0 0 1 0
1 0 0 1 0
𝑃(𝑣1 ) = 0 1 0 0 0
0 1 1 0 0
[0 0 1 0 0]

0 0 0 1 0
1 0 0 1 0
𝑃(𝑣2 ) = 1 1 0 1 0
1 1 1 1 0
[0 0 1 0 0]

DMGT (BE04000261) Page | 66

 Semester: IV (2025-26)

0 0 0 1 0
1 0 0 1 0
𝑃(𝑣3 ) = 1 1 0 1 0
1 1 1 1 0
[1 1 1 1 0]

1 1 1 1 0
1 1 1 1 0
𝑃(𝑣4 ) = 1 1 1 1 0
1 1 1 1 0
[1 1 1 1 0]

1 1 1 1 0
1 1 1 1 0
𝑃(𝑣5 ) = 1 1 1 1 0
1 1 1 1 0
[1 1 1 1 0]
9 Find the shortest distance matrix between each pair of vertices for a given 7
digraph using Warshall’s Algorithm.

Solution: R S T U
𝑅 7 5 ∞ ∞
𝐷0 = 𝑆 [∞7 0 ∞ 2]
𝑇 ∞ 0 ∞
𝑈 4 ∞ 1 0

TOPIC: 3 CONNECTEDNESS
SHORT QUESTIONS
1 Define connected graph 1
Solution:

 An undirected graph is called connected if there is a path between every pair of distinct
vertices of the graph.
 An undirected graph that is not connected is called disconnected.
DMGT (BE04000261) Page | 67
 Semester: IV (2025-26)

 We say that we disconnect a graph when we remove vertices or edges, or both, to

produce a disconnected sub graph.

2 Define Strongly connected graph 1

Solution:
Strongly connected graph:A directed graph is said to be strongly connected if every two vertices a
and b in G there is a path from a to b and b to a.

3 Define edge connectivity 1

An undirected graph is called connected if there is a path between every pair of distinct
vertices of the graph. An undirected graph that is not connected is called disconnected.
We say that we disconnect a graph when we remove vertices or edges, or both, to produce
a disconnected sub graph.

DESCRIPTIVE QUESTIONS
1 Define a unilateral component and strong component. Write unilateral and strong and 7
weak components of the Graph given in following figure.

Solution:

For a simple digraph,

 A maximal weakly connected sub graph is called a weak component

 A maximal unilaterally connected sub graph is called a

unilateral component

 A maximal strongly connected sub graph is called a strong component..

For the diagraph,

{1,2,3}, {4}, {5}, {6}arestrong components.

{1,2,3,4,5}, {6}are the unilateral components.

{1,2,3,4,5,6}is the weak component because the graph is weakly connected.

2 Find all the in degrees and out degrees of the nodes of the graph given in 7
following figure. Give all the elementary cycles of this graph. List all the nodes which are
DMGT (BE04000261) Page | 68
 Semester: IV (2025-26)

reachable from another node of the diagraph

Solution:
In Graph

Vertex In degree Out degree

𝒗𝟏 𝑑𝑒𝑔+ (𝒗𝟏 ) = 𝟏 𝑑𝑒𝑔− (𝒗𝟏 ) = 𝟏

𝒗𝟐 𝑑𝑒𝑔+ (𝒗𝟐 ) = 𝟏 𝑑𝑒𝑔− (𝒗𝟐 ) = 𝟐

𝒗𝟑 𝑑𝑒𝑔+ (𝒗𝟑 ) = 𝟏 𝑑𝑒𝑔− (𝒗𝟑 ) = 𝟐

𝒗𝟒 𝑑𝑒𝑔+ (𝒗𝟒 ) = 𝟏 𝑑𝑒𝑔− (𝒗𝟒 ) = 𝟐

𝒗𝟓 𝑑𝑒𝑔+ (𝒗𝟓 ) = 𝟐 𝑑𝑒𝑔− (𝒗𝟓 ) = 𝟎

Elementary Cycle:

𝒗𝟏 − 𝒗𝟐 − 𝒗𝟒 − 𝒗𝟏
𝒗𝟏 − 𝒗𝟐 − 𝒗𝟑 − 𝒗𝟒 − 𝒗𝟏

List of all the nodes which are reachable from another node of the diagraph

𝑅(𝑣1 ) = 𝑅(𝑣2 ) = 𝑅(𝑣3 ) = 𝑅 (𝑣4 ) = 𝑅 (𝑣5 ) = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 }

3 Define weakly connected, unilaterally connected and strongly connected graphs 3

Solution:

Strongly connectedA directed graph is said to be strongly connected it every two vertices and
b in G there is a path from a to b and b to a.

DMGT (BE04000261) Page | 69

 Semester: IV (2025-26)

Weekly connected: A directed graph is weekly connected if it is not strongly connected.

Disconnected graph: A directed graph which is neither strongly connected nor weekly
connected is known as disconnected graph.

Unilaterally connected graph: A directed graph is said to be

Unilaterally connected graph if for any pair of vertices of the graph at least one
of the vertex of pair is reachable from other vertex

DMGT (BE04000261) Page | 70

 Semester: IV (2025-26)

4 Explain the application of graphs in resource allocation and deadlock detection in 7

Operating Systems with an example
Solution:

DMGT (BE04000261) Page | 71

 Semester: IV (2025-26)

Define cut vertex. List out all the cut vertices of the graph given in figure 3
DMGT (BE04000261) Page | 72
 Semester: IV (2025-26)

Solution:
 Let G' be a connected graph. A vertex V ∈ G is called a cut vertex of G,
if 'G-V' (Delete 'V' from 'G') is a disconnected graph.
 Removing a cut vertex from a graph breaks it in to two or more graphs.

 B ,D and E are cut vertices.

6 Find the cut vertices and cut edges in the graph G 1 shown in Figure 7

7 Are the directed graphs G and H shown in Figure strongly connected? Are they weakly 4
connected?

8 Determine whether the graphs G and H shown in Figure are isomorphic using the 7
concept of paths and circuits.

DMGT (BE04000261) Page | 73

 Semester: IV (2025-26)

9 How many paths of length four are there from a tod in the simple graph G in Figure? 7

10 Show that the following graph is connected. 7

11 Check given graph in the following figure is weakly connected, unilaterally connected and 7
strongly connected graphs? Why ?

12 Check given graph in the following figure is weakly connected, unilaterally connected and 7
strongly connected graphs? Why ?

TOPIC: 4 TREE
SHORT QUESTIONS
1 Define Binary Tree 1

DMGT (BE04000261) Page | 74

 Semester: IV (2025-26)

Solution:

An m-ary tree is known as binary tree if every branch node has at most 2
2 Define Tree 1

Solution:

A tree is a connected acyclic graph

DESCRIPTIVE QUESTIONS
1 Which trees are complete bipartite graphs? 3
Solution:

Let T be a tree which is a complete bipartite graph.

Let 𝑇 = 𝐾𝑚,𝑛 then the total number of vertices in T is (m+n).

Hence the tree contains (m+n+1) number of edges.

But the graph 𝐾𝑚,𝑛 has (mn) number of edges.

Therefore

𝑚 + 𝑛 − 1 = 𝑚𝑛

⟹ (𝑚 − 1) (𝑛 − 1) = 0

⟹ 𝑚 = 1 𝑜𝑟 𝑛=1

This means T is either 𝐾1,𝑛 or 𝐾𝑚,1

2 Show that it is possible to draw a tree with 10 vertices which has vertices either of degree 1 or of degree 3
3. Draw the tree. Is it possible to draw the same type of tree with 11 vertices?

Solution:

𝑥 + 𝑦 = 10
𝑛

2𝑒 = ∑ 𝑑(𝑣𝑖 )
𝑖=1

⟹ 2 × 9 = 𝑥 + 3𝑦

⟹ 18 = 𝑥 + 3𝑦

⟹ 𝑥 =6 𝑎𝑛𝑑 𝑦 = 4

Now if number of vertices are 11

Then, 𝑒 = 10

Hence,
𝑛

2𝑒 = ∑ 𝑑(𝑣𝑖 )
𝑖=1

20 = 𝑥 + 3𝑦

DMGT (BE04000261) Page | 75

 Semester: IV (2025-26)
13 9
Hence, 𝑥 = 2
, 𝑦 = 2

Which is not possible.

Therefore, it is not possible to draw a tree with 11

vertices which has vertices of degree 1 or 3.

3 What is the total number of nodes in a full binary tree with 20 leaves? 3
Solution:

Let n represent the total number of nodes in a full binary tree.

Then by the result

𝑛 = 𝑚𝑖 + 1

𝑚 = 2

Hence, 𝑛 = 2𝑖 + 1

Where, i is the number of branch nodes,

Total number of nodes in a tree are the sum branch nodes and leaves.

Hence,
𝑛 = 𝑖 + 20

𝑖 = 𝑛 − 20

𝑛 = 2(𝑛 − 20) + 1

𝑛 = 39

Hence total number of nodes in a full binary tree with 20 leaves are 3
4 Construct binary search tree for the following data 7
10,3,15,22,6,45,65,23,78,34,5

Find its in order, preorder and post order traversal

Solution:

5 Create a Binary Search Tree for the following data and do in-order, Preorder and Post-order traversal of 7
the tree.

50, 60, 25, 40, 30, 70, 35, 10, 55, 65, 5

Solution:

DMGT (BE04000261) Page | 76

 Semester: IV (2025-26)

6 Create a Binary Search Tree for the following data and do in-order, Preorder and Post-order traversal of 7
the tree.

40, 60, 15, 4, 30, 70, 65, 10, 95, 25, 34

Solution:

7 Construct a binary search tree from the following traversals: 7

Inorder: 3 4 5 6 7 9 17 20 22
Preorder: 9 4 3 6 5 7 17 22 20

8 Define Binary tree. Obtain Binary tree representation for the following

DMGT (BE04000261) Page | 77

 Semester: IV (2025-26)

9 Form a binary search tree for the data 16, 24, 7, 5, 8, 20, 40, 3. 4
Solution:

10 Define: M‐ary Tree and Binary Tree. 7

Represent the following directed tree as Binary tree

Solution:
M‐ary Tree:
An m-array tree can be described as a generalization of a tree in which each and every node has
m or less children (i.e. at most m-children)

Binary Tree:
A tree which in which each node has at most two children.

23

6 7 8 4

5
DMGT (BE04000261) Page | 78
 Semester: IV (2025-26)

9 10

11

11 Define Subtree and Degree of a Node 7

Determine degree of the each node for the following tree.

SOLUTION:

Subtree:

The definition of subtree of a tree is a tree that descends from a node of

the starting tree.

Degree of node: No. of children to a Nodes called Degree of Node in tree graph

Degree of Each node of above graph

deg (A) = 2 (because Node A has Two children B & C)

deg (B) = 3 (because Node B has Three childrenD,E,F)

deg (C) = 2 (because Node C has Two child G&H)

deg (D) = 0 (because Node D is leaf NODE)

deg (I) = 0 (because Node I is leaf NODE)

deg (J) = 0 (because Node J is leaf NODE)

deg (K) = 0 (because Node K is leaf NODE)

deg (H) = 0 (because Node H is leaf NODE)

deg (E) = 2 (because Node E has Two childrenI&J)

deg (G) = 1 (because Node G has one child K)

12 Give traversal order of following tree into inorder, preorder and postorder.

DMGT (BE04000261) Page | 79

 Semester: IV (2025-26)

SOLUTION:In ABOVE tree

Pre-order: 1, 2, 3, 4, 5

Post Order: 2, 5, 4, 3, 1

In order: 2, 1 , 4, 5, 3
13 Find a post order and preorder traversal of a following tree. 4

SOLUTION:In ABOVE tree

Pre-order: A, B, D, E, F, C, G

Post Order: D, F, E, B, G, C, A

In order: D, B, F, E, A, C, G

14 Define the inorder, postorder and preorder traversal for the following tree. 4

SOLUTION:

Pre-order:
A type of tree traversal that follows the Root-Left-Right policy where:
DMGT (BE04000261) Page | 80
 Semester: IV (2025-26)

 The root node of the subtree is visited first.

 Then the left subtree is traversed.
 At last, the right subtree is traversed.
Pre-order of above tree: A, B, C, D, E, F, G

POST-order:
A type of tree traversal which follows the Left-Right-Root policy such that for each
node:

 The left subtree is traversed first.

 Then the right subtree is traversed
 Finally, the root node of the subtree is traversed.
Post Orderof above tree: C, B, F, E, G, D, A

In order:
A type of tree traversal technique which follows the Left-Root-Right pattern, such
that:

 The left subtree is traversed first.

 Then the root node for that subtree is traversed
 Finally, the right subtree is traversed.
In orderof above tree: C, B, A, E, F, D, G
15 Perform inorder, postorder and preorder traversals for the following binary tree. 4

SOLUTION:In ABOVE tree

Pre-order: 8, 5, 9, 7, 1, 12, 2, 4, 11, 3

Post Order: 9, 1, 2, 12, 7, 5, 3, 11, 4, 8

In order: 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
16 Define: (1) A leaf (2) A branch node of a directed tree. (3) A binary tree 7
(4) A complete binary tree.
Also write the order of nodes for the following tree, if it is
traversed in
(1) Pre order (2) in order (3) post order

DMGT (BE04000261) Page | 81

 Semester: IV (2025-26)

SOLUTION:

(1) Leaf Node:

A node that does not have any child node is called a leaf node.

(2) A branch node of a directed tree:

A non-leaf node is often called a branch node.
(3) Binary Tree:
A tree which in which each node has at most two children.

(4) Complete Binary Tree:

A binary tree has a limitation as any node of the tree has at most two
children: a left and a right child.

In ABOVE tree

Pre-order: A, B, C, D, E, F, G, H

Post Order: C, D, B, H, G, F, E, A.

In order: C, B, D, A, E, G, H, F.
17 Explain Post order traversal. Given the postorder and inorder traversal of a binary tree, draw 7
the unique binary tree.
Postorder: d e c f b h I g a
Inorder: d c e b f a h g i. (Dec-2022)

SOLUTION:

Explanation of Post order traversal

A type of tree traversal which follows the Left-Right-Root policy such that for
each node:


The left subtree is traversed first.
 Then the right subtree is traversed
Finally, the root node of the subtree is traversed.

Post order: d e c f b h i g a
In order: d c e b f a h g i.

Last Node of Post orderis a Root Node, so root node is “a”

According to in-order Node left side to (Root Node) “a”are d, c, e, b,

DMGT (BE04000261) Page | 82
 Semester: IV (2025-26)

f and right side to (Root node) “a”are h, g, i.

bg

c f h i

d e

18 Obtain the binary tree equivalent to the tree given in the following figure. 78

DMGT (BE04000261) Page | 83

 Semester: IV (2025-26)

SOLUTION:V0

V1(ROOT)V7

V2 V3 V8 V12

V4V9 V10

V5 V6V11

19 [Link]-order,in-orderandpost-ordertraversal visit the vertices of the 7

ordered rooted tree shown in figure? (Feb-2024)

DMGT (BE04000261) Page | 84

 Semester: IV (2025-26)

In ABOVE tree

Pre-order: a, b, d, h, e, i, j, c, f, g, k.

Post Order: h, d, i, j, e, b, f, k, g, c, a.

In order: d, h, b, i, e, j, a, f, c, g,

DMGT (BE04000261) Page | 85