Graph-Theory
Question 1 |
7 |
The vertex in the set of size 3 has 4 edges connected to 4 vertices on other set. So, edge color of G is max(3,4) i.e. 4.
When a vertex is added to the graph with 7 vertices ( K 3x4 has 7 vertices), there would be 7 edges associated to that new vertex. As per the edge coloring “no two adjacent edges have same color).
As the new vertex with 7 edges need to be colored with 7 colors, the edge color of graph G is 7.
Question 2 |
1 | |
2 | |
3 | |
4 |

Question 3 |
Let G be a graph with 100! vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G.
Then, y + 10z = ___________.
109 | |
110 | |
111 | |
112 |
There exists edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent numbers in label of ‘v’.
Example:
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it.
So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109
Question 4 |
G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.
16 | |
17 | |
18 | |
19 |
Degree of each vertex ≥ 3

|v| = 2|E|
The relation between max and min degree of graph are
m ≤ 2|E| / |v| ≤ M
Given minimum degree = 3
So, 3 ≤2 |E| / |v|
3|v| ≤ 2|E|
3(n) ≤ 2(25)
n ≤ 50/3
n ≤ 16.6
(n = 16)
Question 5 |
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
4 | |
5 | |
6 | |
7 |
Here it is asked about the sufficient number of colors, so with the worst case of 4 colors we can color any planar graph.
Question 6 |
24 | |
25 | |
26 | |
27 |
|V|+|R|=|E|+2 ------(1) where |V|, |E|, |R| are respectively number of vertices, edges and faces (regions)
Given |V|=10 ------(2) and number of edges on each face is three
∴3|R|=2|E|⇒|R|=2/3|E| ------(3)
Substituting (2), (3) in (1), we get
10+2/3|E|=|E|+2⇒|E|/3=8⇒|E|=24
Question 7 |
A tree has no bridges | |
A bridge cannot be part of a simple cycle | |
Every edge of a clique with size 3 is a bridge (A clique is any complete sub graph of a graph) | |
A graph with bridges cannot have a cycle
|
∴ (A) is false
Since, every edge in a complete graph kn(n≥3) is not a bridge ⇒
(C) is false
Let us consider the following graph G:

This graph has a bridge i.e., edge ‘e’ and a cycle of length ‘3’
∴ (D) is false
Since, in a cycle every edge is not a bridge
∴ (B) is true
Question 8 |
A multiple of 4 | |
Even | |
Odd | |
Congruent to 0 mod 4, or, 1 mod 4
|
Question 9 |
G1=(V,E1) where E1={(u,v)|(u,v)∉E} | |
G2=(V,E2 )where E2={(u,v)│(u,v)∈E} | |
G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E} | |
G4=(V4,E) where V4 is the set of vertices in G which are not isolated |
→ It strongly connected.
(A) G1=(V,E1) where E1={(u,v)|(u,v)∉E}
If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.
(B) G2=(V,E2 )where E2={(u,v)│(u,v)∈E}
Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.
Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.
(C) G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E}
This can also be true.
eg:

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.
(D) G4=(V4,E) where V4 is the set of vertices in G which are not isolated.
If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component
then no. of SCC = x + 1
G4 contain only ‘1’ component, which is not same as G.
Question 10 |
506 | |
507 | |
508 | |
509 |
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8.
From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012=2*E
⇒ E=506
Question 11 |
(1, 1, 1, 1, 1, 1) | |
(2, 2, 2, 2, 2, 2) | |
(3, 3, 3, 1, 0, 0) | |
(3, 2, 1, 1, 1, 0) |
A) (1, 1, 1, 1, 1, 1)

Yes, it is a graph.
We will see that option (C) is not graphic.
Question 12 |
36 | |
37 | |
38 | |
39 |

Total no. of edges = 6×6 = 36
Question 13 |
5 | |
6 | |
7 | |
8 |
In a cycle of n vertices, each vertex is connected to other two vertices. So each vertex degree is 2.
When we complement it, each vertex will be connected to remaining n-3 vertices ( one is self and two other vertices in actual graph).
As per given question,
n-3 =2
n=5
Cycle of 5 vertices is

Complement of the above graph1 is

Graph1 and Graph2 are complement each other.
So, the value of n is 5.
Question 14 |
4 | |
5 | |
6 | |
7 |
a*a-1 = e

1. x*x=e So x-1 is x ⇒ x is element of Group
2. y*y=e So y-1 = y ⇒ y is element of Group

4. (y*x)*(y*x)=x*y*y*x=x*x*e=e So (y*x)-1=(y*x)
In ③, ④
x*y,y*x has same inverse, there should be unique inverse for each element.
x*y=y*x (even with cumulative law, we can conclude)
So {x, y, e, x*y} are element of Group.
Question 15 |
⌊n/k⌋ | |
⌈n/k⌉ | |
n–k | |
n-k+1 |
Option 1, 2 will give answer 1. (i.e. one edge among them),
Option 3: n-k = 0 edges.
Option 4: n-k+1 : 1edge, which is false.
Question 16 |
1/8 | |
1 | |
7 | |
8 |

The probability that there exists one edge between two vertices = 1/2

So, the total probability that all three edges of the above exists
= 1/2 × 1/2 × 1/2 (as they are independent events)
= 1/8
Total number of ways in which we can select ‘3’ such vertices among ‘8’ vertices = 8C3 = 56
Total number of cycles of length ‘3’ out of 8 vertices = 56 × 1/8 = 7
Question 17 |
P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
P only | |
Q only | |
Both P and Q | |
Neither P nor Q |
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.
Question 18 |
(P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
P only | |
P and R only | |
R only | |
P, Q and S only |
R) False. We can give counter example. Let G has 5 vertices and 9 edges which is planar graph. Assume degree of one vertex is 2 and of all others are 4. Now, L(G) has 9 vertices (because G has 9 edges) and 25 edges. But for a graph to be planar,
|E| ≤ 3|v| - 6
For 9 vertices |E| ≤ 3 × 9 - 6
⇒ |E| ≤ 27 - 6
⇒ |E| ≤ 21. But L(G) has 25 edges and so is not planar.
As (R) is false, option (B) & (C) are eliminated.
Question 19 |
3 | |
4 | |
5 | |
6 |
v-e+f=2
Given 10 vertices & 15 edges
10-15+f=2
f=2+15-10
f=7
There will be an unbounded face always. So, number of faces = 6.
Question 20 |
![]() | |
![]() | |
![]() | |
![]() |

(A) 3 cycle graph not in original one.

(B) Correct 5 cycles & max degree is 4.
(C) Original graph doesn’t have a degree of 3.

(D) 4 cycles not in original one.

Question 21 |
15 | |
30 | |
45 | |
360 |
It is asked to find the distinct cycle of length 4. As it is complete graph, if we chose any two vertices, there will be an edge.
So, to get a cycle of length 4 (means selecting the 4 edges which can form a cycle) we can select any four vertices.
The number of such selection of 4 vertices from 6 vertices is 6C4 => 15.
From each set of 4 vertices, suppose a set {a, b, c, d} we can have cycles like
a-b-c-d
a-b-d-c
a-c-b-d
a-c-d-b
a-d-b-c
a-d-c-b (Total 6, which is equal to number of cyclic permutations (n-1)! )
As they are labelled you can observe, a-b-c-d and a-d-c-b are same, in different directions.
So, we get only three combinations from the above 6.
So, total number of distinct cycles of length 4 will be 15*3 = 45.
If it is asked about just number of cycles then 15*6 = 90
Question 22 |

K4 is planar while Q3 is not | |
Both K4 and Q3 are planar | |
Q3 is planar while K4 is not | |
Neither K4 not Q3 is planar |

Both the above graphs are planar.
Question 23 |
|S| = 2|T| | |
|S| = |T| - 1 | |
|S| = |T| | |
|S| = |T| + 1 |

id= no. of vertices of degree ‘d’ in ‘G’
Eg:

No. of vertices with degree ‘2’ = 3
ξ(G')=3×2='6' i.e., sum of degrees
By Handshaking Theorem,
The sum of degrees would be equal to twice the no. of edges
|V|=2|E|
It is given that ξ(G)=ξ(S) then
Sum of degrees of vertices in G is equal to sum of degrees of vertices in S
i.e., 2*(no. of edges in G)=2*no. of edges in S no. of edges in G=no. of edges in S
Eg:

ξ(G)=(2×2)+(2×3)=4+6=10

ξ(S)=2×5=10
You can observe that, though no. of vertices are different, but still no. of edges are same.
Question 24 |
(I) 7, 6, 5, 4, 4, 3, 2, 1 (II) 6, 6, 6, 6, 3, 3, 2, 2 (III) 7, 6, 6, 4, 4, 3, 2, 2 (IV) 8, 7, 7, 6, 4, 2, 1, 1
I and II
| |
III and IV | |
IV only | |
II and IV |
⇾ Arrange the degree of vertices in descending order
eg. d1,d2, d3...dn
⇾ Discard d1, subtrack ‘1’ from the next 'd1'degrees
eg:

⇒ 1 1 0 1
⇾ We should not get any negative value if its negative, this is not valid sequence
⇾ Repeat it till we get ‘0’ sequence
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. 6, 6, 6, 6, 3, 3, 2, 2
➡️5, 5, 5, 2, 2, 1, 2
put them in descending order
➡️5, 5, 5, 2, 2, 2, 1
➡️4, 4, 1, 1, 1, 1
➡️3, 0, 0, 0, 1 (descending order)
➡️3, 1, 0, 0, 0
➡️0, -1, -1, 0
[This is not valid]
III. 7, 6, 6, 4, 4, 3, 2, 2
➡️5, 5, 3, 3, 2, 1, 1
➡️4, 2, 2, 1, 0, 1
➡️4, 2, 2, 1, 1, 0 (descending order)
➡️1, 1, 0, 0, 0
➡️0, 0, 0, 0
[valid]
IV. 8, 7, 7, 6, 4, 2, 1, 1
There is a degree ‘8’, but there are only ‘8’ vertices.
A vertex cannot have edge to itself in a simple graph. This is not valid sequence.
Question 25 |
No two vertices have the same degree.
| |
At least two vertices have the same degree. | |
At least three vertices have the same degree. | |
All vertices have the same degree.
|
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n-1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n-1) vertices). Degree sequence has only (n-1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) consider a triangle, all vertices has same degree, so it is false
C) consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
Question 26 |
2 | |
3 | |
n-1 | |
n |
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 27 |
The graph is connected | |
The graph is Eulerian
| |
The graph has a vertex-cover of size at most 3n/4
| |
The graph has an independent set of size at least n/3
|
(A) Consider the following disconnected graph which is planar.

So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.

So false.
(D) Consider K4 graph. It has independent set size 1 which is less than 4/3.

So false.
Hence, option (C) is correct.
Question 28 |
2 | |
3 | |
4 | |
5 |
→ Chromatic number of a graph is the smallest number of colours needed to colour the vertices so that no two adjacent vertices share the same colour.

Question 29 |
5 | |
4 | |
3 | |
2 |
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
Question 30 |
Regular | |
Complete | |
Hamiltonian | |
Euler |
→ In Euler graph all degrees must be even for all nodes. And number of odd degree vertices should be even.
→ So, degree of this new node will be even and as a new edge is formed between this new node and all other nodes of odd degree hence here is not a single node exists with degree odd so this is Euler graph.
Question 31 |
9 edges and 5 vertices | |
9 edges and 6 vertices | |
10 edges and 5 vertices
| |
10 edges and 6 vertices
|
if n ≥ 3 then e ≤ 3n-6 (for planarity)
where n = no. of vertices
e = no. of edges
Now lets check the options.
A) e=9, n=5
9 ≤ 3(5) - 6
9 ≤ 15 - 6
9 ≤ 9
Yes, it is planar.
B) e=9, n=6
9 ≤ 3(6) - 6
9 ≤ 18 - 6 9 ≤ 12 Yes, it is planar.
iii) e=10, n=5
10 ≤ 3(5) - 6
10 ≤ 15 - 6
10 ≤ 9 No, it is not planar.
So, option C is non-planar graph.
iv) e=10, n=6
10 ≤ 3(6) - 6
10 ≤ 18 - 6
10 ≤ 12
Yes, it is planar.
Question 32 |
Any k-regular graph where k is an even number.
| |
A complete graph on 90 vertices.
| |
The complement of a cycle on 25 vertices.
| |
None of the above.
|
→ all vertices in the graph have an "even degree".
→ And the graph must be corrected.
Now in option (C) it is saying that the complement of a cycle on 25 vertices without complement the degree of each vertex is 2.
Now since there are 25 vertices, so maximum degree of each vertex will be 24 and so in complement of cycle each vertex degree will be 24 - 2 = 22.
There is a theorem which says "G be a graph with n vertices and if every vertex has a degree of atleast n-1/2 then G is connected."
So we can say that complement of cycle with 25 vertices fulfills both the conditions, and hence is Eulerian circuit.
Question 33 |
![]() | |
2n-2 | |
2n-3 × 3 | |
2n-1 |
(k(c))2 2n-k
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(c))2 2n-k w.r.t. k and equal to 0.
You will get k = 2/(loge)2 which is not an integer.
So you can see it like

∴ The maximum degree 3⋅2n-3 at k=3 or k=4.
Question 34 |
n | |
n+2 | |
2n/2 | |
2n / n |
While other nodes are connected so that total number of connected components is (n+1)+1
(here we are adding 1 because it is connected corresponding remaining vertices)
= n+2
Question 35 |
1 | |
n | |
n+1 | |
2n |
= no. of subsets with size less than or equal to 1
= n+1, because in question it is given that the two vertices are connected if and only if the corresponding sets intersect in exactly two elements.
Question 36 |
Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is
1/(2n-1) | |
1/n | |
2/n | |
3/n |
That will give us a bipartite graph, with chromatic number = 2
Also from the same we can conclude that we need for a 'n' bit string, to traverse no more than (n-1) edges or 'n' vertices to get a path between two arbitary points. So the ratio is (2/n).
Question 37 |
6 | |
8 | |
9 | |
13 |
F = E - V + 2 [From Euler's formula i.e., F + V - E = 2]
F = 19 - 13 +2
F = 8
Question 38 |
12 | |
8 | |
Less than 8
| |
More than 12
|
Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices - Minimum cover of vertex G
= 20 - 8
= 12
Question 39 |
G1 | |
G2 | |
G3 | |
G4 |

which is planar
G3 can also be drawn as

which is planar
G4 can also be drawn as

which is planar
But G1 cannot be drawn as planar graph.
Hence, option (A) is the answer.
Question 40 |
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
There exists a cutset in G having all edges of maximum weight | |
There exists a cycle in G having all edges of maximum weight | |
Edge e cannot be contained in a cycle | |
All edges in G have the same weight
|

(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.
Question 41 |
4 | |
7 | |
23 | |
99 |
j = i +1
(or)
j = 3i
Second option will help us reach from 1 to 100 rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.
So, the edge sequence with minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.
Question 42 |
2 | |
3 | |
4 | |
5 |

→ a, b, c, d = 4
→ The minimum no. of colours required to colour a graph = 4 (no two adjacent vertices have same colours)
Question 43 |
![]() | |
![]() | |
![]() | |
![]() |
Maximum no. of vertices = n(n-1)/2 = v
No. of graphs with minimum b edges is
= C(v,e) + C(v,e+1) + C(v,e+2) + ... + C(v,v)
= C((v,v-e) + C(v,v-(e+1)) + C(v,v-(e+2)) + ... + C(v,0)
= C(a,n) + C(a,n-1) + C(a,n-2) + ... + C(a,0) (since a-b=n)
= C(n(n-1)/2,n) + C(n(n-1)/2,n-1) + ... + C(n(n-1)/2,0)

Question 44 |
cannot have a cut vertex
| |
must have a cycle
| |
must have a cut-edge (bridge)
| |
has chromatic number strictly greater than those of G1 and G2
|
(A)

False, since in G1∪G2 'C' is a cut vertex.
(B) True, for all conditions.
(C)

False. G1∪G2 has no bridge.
D)

False. G1∪G2, G1, G2 all the three graphs have chromatic number of 2.
Question 45 |
n - 1 | |
n | |
n + 1 | |
2n - 1 |
= n - 1
Question 46 |
10 | |
11 | |
18 | |
19 |
By Handshaking Lemma,
6 * 2 + 3 * 4 + (x - 9) * 3 = 27 * 2
24 + (x - 9) * 3 = 54
x = 19
Question 47 |
k and n | |
k – 1 and k + 1 | |
k – 1 and n – 1
| |
k + 1 and n – k
|
If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n-1) components.
Question 48 |
15 | |
24 | |
30 | |
60 |
(2n)!/n!×2n
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×23 = 15
Question 49 |

3 | |
4 | |
5 | |
6 |
|E| ≤ 3|v| - 6
Based on handshaking lemma, the minimum degree is (min×|v|)/2
⇒ (min×|v|)/2 ≤ 3|v| - 6
Checking the options lets take min=6
(6×|v|)/2 ≤ 3|v| - 6
0 ≤ -6 (Not satisfied)
And which is inconsistent.
Question 50 |
2 | |
3 | |
4 | |
n - 2[n/2] + 2 |
Question 51 |
![]() | |
![]() | |
![]() | |
![]() |
Question 53 |
8 | |
4 | |
12 | |
25 |
1 — 9 — 17 — ......... — 97
2 — 10 — 18 — ......... — 98
3 — 11 — 19 — ......... — 99
4 — 12 — 20 — ......... — 100
5 — 13 — 21 — ......... — 93
6 — 14 — 22 — ......... — 94
7 — 15 — 23 — ......... — 95
8 — 16 — 24 — ......... — 96
We have covered all vertices using 8 vertex sets considering only |i - j| = 8. Using |i - j| = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.
Question 54 |
n - 1 | |
n | |
n + 1 | |
None of the above |
In cyclic graph:
No. of edges = No. of vertices
⇒ n = n
Question 55 |
15 | |
10 | |
7 | |
9 |

Question 56 |
d*n/2 |
d * n = 2 * |E|
∴ |E| = d*n/2
Question 57 |
3n - 6 |
⇒ (3n - 2) = 3n - 6
Question 58 |
9 edges, 6 vertices | |
6 edges, 4 vertices | |
10 edges, 5 vertices | |
9 edges, 5 vertices |

The above graph with 5 vertices and 10 edges is non-planar.
Question 59 |
![]() | |
2n | |
n! | |
![]() |
Each subset of these edges will be form a graph.
No. of possible undirected graphs is 2(n C 2)
⇒ 2(n(n-1)/2)
Question 60 |
(n-k)(n-k+1)/2 |
To get maximum, take one vertex each for each component, except last component.
Now, k-1 components have 1 vertex each and so on edges.
The last component has (n-(k-1)) vertices. So make the last component complete, i.e., it has n-(n-1)C2
= (n-k)(n-k+1)/2
= maximum no. of edges
Question 61 |
It does not contain subgraphs homeomorphic to k5 and k3,3. | |
It does not contain subgraphs isomorphic to k5 or k3,3. | |
It does not contain a subgraph isomorphic to k5 or k3,3. | |
It does not contain a subgraph homeomorphic to k5 or k3,3. |
Question 62 |
Theory Explanation is given below. |
→ Let us assume K33is a planar graph. Then it satisfy the useful corollary. As there is no triangle in K33.
Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n-4.
Where m=9, n=6
⇒ 9 ≤ 12 - 4
⇒ 9 ≤ 8, which is to be false, then K33 is non-planar graph.
(ii) G2 is a planar graph. Because it can be redrawn like as below.

(iii) Let us assume G3 be a planar graph then it also be satisfy useful corollary.
Where m=9, n=6
then 9 ≤ 12-4
9 ≤ 8 is False
So, G3 is non-planar graph.
Answer: Only G2 is planar graph.