Graph Theory ESA Sample I

1) Answer any 10 questions:

a) Define ‘Induced Subgraph’.
Ans) In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed
from a subset of the vertices of the graph and all of the edges, from the original graph, connecting pairs of
vertices in that subset.
Formally, let 𝐺 = (𝑉, 𝐸) be any graph, and let 𝑆 ⊆ 𝑉 be any subset of vertices of G. Then the induced
subgraph 𝐺[𝑆] is the graph whose vertex set is 𝑆 and whose edge set consists of all of the edges in 𝐸 that
have both endpoints in 𝑆. That is, for any two vertices 𝑢, 𝑣 ∈ 𝑆, 𝑢 and 𝑣 are adjacent in 𝐺[𝑆] if and only if
they are adjacent in 𝐺.

b) Define ‘Regular graph’.

Ans) A graph is called regular graph if degree of each vertex is equal. A graph is called K regular if degree of
each vertex in the graph is K.

Degree of each of the vertices of this graph is 2. So, the graph is 2 Regular.

c) Define a ‘Null graph’.

Ans) A null graph is a graph in which there are no edges between its vertices. In other words, it is a graph
with only vertices and no connections between them. A null graph can also be referred to as an edgeless
graph, an isolated graph, or a discrete graph.

d) Define with example the term ‘Spanning Subgraph’.

Ans) Consider the graph G(V, E) as shown below. A spanning subgraph is a subgraph that contains all the
vertices of the original graph G, i.e., G'(V’, E’) is spanning if V’=V and E’ is a subset of E.
So, one of the spanning subgraphs can be as shown below G'(V’, E’). It has all the vertices of the original
graph G and some of the edges of G.

e) Define with example ‘Spanning Tree’.

Ans) A spanning tree is a subset of Graph G, such that all the vertices are connected using minimum
possible number of edges. Hence, a spanning tree does not have cycles and a graph may have more than
one spanning tree.

• A Spanning tree does not exist for a disconnected graph.

• For a connected graph having N vertices then the number of edges in the spanning tree for that
graph will be N-1.
• A Spanning tree does not have any cycle.
_______________________________________________________________________________________
f) Explain the term ‘Radius of a Connected Graph’ with a suitable example.
Ans) A radius of the graph exists only if it has the diameter. The minimum among all the maximum
distances between a vertex to all other vertices is considered as the radius of the Graph G. It is denoted as
r(G). It can also be found by finding the minimum value of eccentricity from all the vertices.
Radius: 2
All available minimum radius:
BC → CF,
BC → CE,
BC → CD,
BC → CA
_______________________________________________________________________________________
f)

The two graphs shown above are isomorphic to each other – True or False? Give reason for your answer.
Ans) Two graphs that are not isomorphic.
If the graph in (a) were to be isomorphic to the one in (b), vertex x must correspond to y, because there are
no other vertices of degree three. Now in (b) there is only one pendant vertex, w, adjacent to y, while in (a)
there are two pendant vertices, u and v, adjacent to x.
_______________________________________________________________________________________
g) Define the term ‘Centre of a Graph’ and list down the points which are at the center of the graph
shown in the adjacent figure.

Ans) The center of a graph is the set of all vertices of minimum eccentricity, that is, the set of all vertices u
where the greatest distance d(u, v) to other vertices v is minimal. Equivalently, it is the set of vertices with
eccentricity equal to the graph's radius.
E(a) = 2, E(b) = 2, E(c) = 2, E(d) = 2, E(e) = 2
E(f) = 3, E(g) = 3, E(h) = 3, E(i) = 3
Therefore, the center points are a, b, c, d, e
_______________________________________________________________________________________
g) Define the term ‘Hamiltonian Graph’. Give an example.
Ans) A Hamiltonian graph is a graph which has a closed path (cycle) that visits each vertex exactly once, ending on
the same vertex as it began. This closed path is also called a Hamiltonian cycle.
h) Find the number of 5 letter words, that can be created with the letters from the word ‘COMPUTE’.
Ans)

_______________________________________________________________________________________
i) How many 4-letter words can be formed using the letters of the word "ALGORITHM"?
Ans) The word "ALGORITHM" has 9 different letters.
We want to form 4-letter words.
We can make 9P4 different 4-letter words:
9P4 = 9! / (9 – 4)!
= 9! / 5!
=9*8*7*6
= 3024
_______________________________________________________________________________________
j) According to the recurrence relation and with the initial condition of , what will be the value of ?
Ans) To be done later.
_______________________________________________________________________________________
2) Prove that a graph of order n is a tree if and only if it is acyclic and contains n − 1 edges.
Ans)

_______________________________________________________________________________________
3) Define Hamiltonian Circuit. Show how in a complete graph with n vertices, you can draw (n - 1)/2
edge-disjoint Hamiltonian circuits, if n is an odd number > 3.
Ans) A Hamiltonian circuit is a circuit that visits every vertex once with no repeats. Being a circuit, it must
start and end at the same vertex.

_______________________________________________________________________________________
3) Define Distance between two vertices in a Graph. Prove that in a connected graph if u, v and w are
three arbitrary vertices and d(u, v) denotes the distance between the vertices u and v, then
Ans) The distance between two vertices in a graph is the number of edges in a shortest or minimal path. It
gives the available minimum distance between two edges. There can exist more than one shortest path
between two vertices.
_______________________________________________________________________________________
4) a) State Pigeon-Hole theorem.
Ans) The Pigeonhole Principle can be formally stated as follows:
If n items are distributed among m containers and n > m, then at least one container must contain more
than one item.
_______________________________________________________________________________________
b) A bowl contains 5 marbles each of colors green, blue and black. I want to have at least three marbles
of same color. Minimum how many marbles I need to draw?
Ans) To solve the problem, we will use the Pigeonhole Principle, which states that if n items are put into m
containers, with n>m, then at least one container must contain more than one item.
In this case, we have 15 marbles distributed among 3 colors (green, blue, black). Since we are looking for at
least three marbles of the same color, we consider the worst-case scenario where we draw just enough
marbles to not yet have three of any color.
Draw 2 marbles of each color: 2×3=6 marbles drawn (2 green, 2 blue, 2 black).
With 6 marbles, we could have drawn 2 marbles from each color, which is still less than 3 marbles of any
single color. Therefore, drawing 6 marbles is not enough to guarantee at least three marbles of the same
color.
Now, draw one more marble, making it 7 marbles drawn:
Worst-case scenario: 2 green, 2 blue, 2 black, and 1 additional marble (could be any color).
In this case, regardless of the color of the 7th marble drawn, at least one color will have three marbles
(since only one color has fewer than 3 marbles). Thus, drawing 7 marbles guarantees that we have at least
three marbles of the same color.
Therefore, the minimum number of marbles needed to draw to ensure at least three marbles of the same
colour is 7.
_______________________________________________________________________________________
5) What do you mean by cut set and cut vertex. Explain with proper example.
Ans) Let 'G'= (V, E) be a connected graph. A subset E' of E is called a cut set of G if deletion of all the edges
of E' from G makes G disconnect.
If deleting a certain number of edges from a graph makes it disconnected, then those deleted edges are
called the cut set of the graph.
Take a look at the following graph. Its cut set is E1 = {e1, e3, e5, e8}.

After removing the cut set E1 from the graph, it would appear as follows –

Let 'G' be a connected graph. A vertex V ∈ G is called a cut vertex of 'G', if 'G-V' (Delete 'V' from 'G') results
in a disconnected graph. Removing a cut vertex from a graph breaks it in to two or more graphs.
Note − Removing a cut vertex may render a graph disconnected.
A connected graph 'G' may have at most (n–2) cut vertices.
In the following graph, vertices 'e' and 'c' are the cut vertices.

By removing 'e' or 'c', the graph will become a disconnected graph.

_______________________________________________________________________________________________
6) Solve the recurrence relation with the initial condition of 5 and using the iteration technique.
Ans) To be done later.
_______________________________________________________________________________________
7) Prove that every bipartite graph does not contains any odd cycle.
Ans) In a bipartite graph, vertices can be divided into two sets such that there are no edges between
vertices within the same set.
Proof: Suppose G = (V, E) is a bipartite graph with bipartition (V1, V2) where V1 and V2 are two disjoint
subset of vertices.
Suppose G contains an odd cycle C = (v1, v2, …., vk, v1), where k is odd.

Assume, Vi ∈ A, i is odd

Vi ∈ B, i is even

But then (vk, v1) ∈ E is an edge with both endpoints belongs to A. This is a contradiction since G is bipartite.
Therefore, there does not exist any odd cycles.
_______________________________________________________________________________________
8)

From the above diagram, assuming A as the starting node and H as the terminal node, compute the
optimal path, according to Breadth-First-Search (BFS) algorithm. Write down each intermediate step
clearly.
OR
From the above diagram, find the Minimal Spanning Tree using Prim’s Algorithm. Show each
intermediate steps clearly.
Ans) To be done later.
_______________________________________________________________________________________
9) a) Define Tree.
Ans) In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one
path, or equivalently a connected acyclic undirected graph.
_______________________________________________________________________________________
b) Any connected graph G of order n is a tree if and only if its size is n-1.
Ans) Proof: We know that the minimum number of edges required to make a graph of n vertices
connected is (n-1) edges. We can observe that removal of one edge from the graph G will make it
disconnected. Thus, a connected graph of n vertices and (n-1) edges cannot have a circuit. Hence a graph G
is a tree.

_______________________________________________________________________________________________

c) In a tree of size 10, there are 7 leaf nodes and only one node of degree 2. How many such trees are
possible? Write down their degree sequences.
Ans) To be done later.
_______________________________________________________________________________________
10) a) How many ways are there to distribute 6 distinct books to 4 students such that each student gets
at least one book?
Ans) First, distribute 1 book to each student, then distribute the remaining 2 books.
There are 4 x C (4, 2) ways.
_______________________________________________________________________________________
b) Check whether the following degree sequences are valid or not. The degree sequences are as follows.
i) 7, 6, 5, 4, 4, 3, 2, 1
ii) 8, 7, 7, 6, 4, 2, 1, 1
Ans) i) 7, 6, 5, 4, 4, 3, 2, 1
5, 4, 3, 3, 2, 1, 0
3, 2, 2, 1, 0, 0
1, 1, 0, 0, 0
0, 0, 0, 0 (valid)
ii) 8, 7, 7, 6, 4, 2, 1, 1 (invalid) (Degree 8 but only 8 vertices available, simple graph cannot have self-loop)
_______________________________________________________________________________________