GraphTheory
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 = 2E
The relation between max and min degree of graph are
m ≤ 2E / v ≤ M
Given minimum degree = 3
So, 3 ≤2 E / v
3v ≤ 2E
3(n) ≤ 2(25)
n ≤ 50/3
n ≤ 16.6
(n = 16)
Question 5 
The minimum number of colours that is sufﬁcient to vertexcolour 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
∴3R=2E⇒R=2/3E (3)
Substituting (2), (3) in (1), we get
10+2/3E=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 
G_{1}=(V,E_{1}) where E_{1}={(u,v)(u,v)∉E}  
G_{2}=(V,E_{2} )where E_{2}={(u,v)│(u,v)∈E}  
G_{3}=(V,E_{3}) where E_{3}={(u,v)there is a path of length≤2 from u to v in E}  
G_{4}=(V_{4},E) where V_{4} is the set of vertices in G which are not isolated 
→ It strongly connected.
(A) G_{1}=(V,E_{1}) where E_{1}={(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) G_{2}=(V,E_{2} )where E_{2}={(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) G_{3}=(V,E_{3}) where E_{3}={(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) G_{4}=(V_{4},E) where V_{4} 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
G_{4} 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 n3 vertices ( one is self and two other vertices in actual graph).
As per given question,
n3 =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  
nk+1 
Option 1, 2 will give answer 1. (i.e. one edge among them),
Option 3: nk = 0 edges.
Option 4: nk+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 = ^{8}C_{3} = 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 ≤ 3v  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 
ve+f=2
Given 10 vertices & 15 edges
1015+f=2
f=2+1510
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 ^{6}C_{4} => 15.
From each set of 4 vertices, suppose a set {a, b, c, d} we can have cycles like
abcd
abdc
acbd
acdb
adbc
adcb (Total 6, which is equal to number of cyclic permutations (n1)! )
As they are labelled you can observe, abcd and adcb 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 = 2T  
S = T  1  
S = T  
S = T + 1 
i_{d}= 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=2E
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. d_{1},d_{2}, d_{3}...d_{n}
⇾ Discard d_{1}, subtrack ‘1’ from the next 'd_{1}'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,....n1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n1) vertices). Degree sequence has only (n1) 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  
n1  
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 vertexcover 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 K_{4} 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 ≤ 3n6 (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 nonplanar graph.
iv) e=10, n=6
10 ≤ 3(6)  6
10 ≤ 18  6
10 ≤ 12
Yes, it is planar.
Question 32 
Any kregular 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 n1/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 
2^{n2}  
2^{n3} × 3  
2^{n1} 
(k(_{c}))_{2} 2^{nk}
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(_{c}))_{2} 2^{nk} w.r.t. k and equal to 0.
You will get k = 2/(log_{e})2 which is not an integer.
So you can see it like
∴ The maximum degree 3⋅2^{n3} at k=3 or k=4.
Question 34 
n  
n+2  
2^{n/2}  
2^{n} / 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  
2^{n} 
= 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/(2^{n1})  
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 (n1) 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 
G_{1}  
G_{2}  
G_{3}  
G_{4} 
which is planar
G_{3} can also be drawn as
which is planar
G_{4} can also be drawn as
which is planar
But G_{1} 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(n1)/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,ve) + C(v,v(e+1)) + C(v,v(e+2)) + ... + C(v,0)
= C(a,n) + C(a,n1) + C(a,n2) + ... + C(a,0) (since ab=n)
= C(n(n1)/2,n) + C(n(n1)/2,n1) + ... + C(n(n1)/2,0)
Question 44 
cannot have a cut vertex
 
must have a cycle
 
must have a cutedge (bridge)
 
has chromatic number strictly greater than those of G_{1} and G_{2}

(A)
False, since in G_{1}∪G_{2} 'C' is a cut vertex.
(B) True, for all conditions.
(C)
False. G_{1}∪G_{2} has no bridge.
D)
False. G_{1}∪G_{2}, G_{1}, G_{2} 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 (n1) components.
Question 48 
15  
24  
30  
60 
(2n)!/n!×2^{n}
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×2^{3} = 15
Question 49 
3  
4  
5  
6 
E ≤ 3v  6
Based on handshaking lemma, the minimum degree is (min×v)/2
⇒ (min×v)/2 ≤ 3v  6
Checking the options lets take min=6
(6×v)/2 ≤ 3v  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 nonplanar.
Question 59 
2^{n}  
n!  
Each subset of these edges will be form a graph.
No. of possible undirected graphs is 2^{(n C 2) ⇒ 2(n(n1)/2)}
Question 60 
(nk)(nk+1)/2 
To get maximum, take one vertex each for each component, except last component.
Now, k1 components have 1 vertex each and so on edges.
The last component has (n(k1)) vertices. So make the last component complete, i.e., it has ^{n(n1)}C_{2}
= (nk)(nk+1)/2
= maximum no. of edges
Question 61 
It does not contain subgraphs homeomorphic to k_{5} and k_{3,3}.  
It does not contain subgraphs isomorphic to k_{5} or k_{3,3}.  
It does not contain a subgraph isomorphic to k_{5} or k_{3,3}.  
It does not contain a subgraph homeomorphic to k_{5} or k_{3,3}. 
Question 62 
Theory Explanation is given below. 
→ Let us assume K_{33}is a planar graph. Then it satisfy the useful corollary. As there is no triangle in K_{33}.
Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n4.
Where m=9, n=6
⇒ 9 ≤ 12  4
⇒ 9 ≤ 8, which is to be false, then K_{33} is nonplanar graph.
(ii) G_{2} is a planar graph. Because it can be redrawn like as below.
(iii) Let us assume G_{3} be a planar graph then it also be satisfy useful corollary.
Where m=9, n=6
then 9 ≤ 124
9 ≤ 8 is False
So, G_{3} is nonplanar graph.
Answer: Only G_{2} is planar graph.