Which of the following degree sequence is a valid degree sequence
4, 4, 3, 1, 1, 1
4, 4, 4, 3, 3, 2
5, 5, 5, 2, 2, 1
5, 3, 3, 2, 1, 1
Correct Answer
Option 2
Solution
As per the Havel Hakimi theorem
(A) 4, 4, 3, 1, 1, 1
⇒ 3 2 0 0 1
⇒ 3 2 1 0 0
⇒ 1 0 _ 1 0 Not a valid sequence.
(B) 4, 4, 4, 3, 3, 2
⇒ _, 3, 3, 2, 2, 2
⇒ _ _ 2 1 1 2
⇒ _ _ 2 2 1 1
⇒ _ _ _ 1 0 1
⇒ _ _ _ 1 1 0
⇒ _ _ _ _ _ _ Valid sequence.
(C) 5, 5, 5, 2, 2, 1
⇒ _ 4 4 1 1 0
⇒ _ _ 3 0 0 _ 1 Not a valid sequence.
(D) 6, 3, 3, 2, 1, 1
When there are ‘6’ vertices, the degree cannot be six.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
In a complete graph with 8 vertices, the number of cycles of length 5 are
672
Correct Answer
Option 1
Solution
In a complete graph of n vertices, the number of ways of selecting m vertices for forming a cycle with m vertices are nCm. The number of cycles formed with m vertices are (m-1)!.
If the number of distinct cycles are asked then it will be (m-1)!.
As the asked is about number of cycles, it can be (nCm)*(m-1)!
N =8, m=5
8C5 * (5-1)! = 56*4!= 56*24 = 1344. (Answer)
If it was asked distinct cycles then it ll be (nCm)*(m-1)! /2 = 1344/2= 672
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
Choose the correct statement
The number of perfect matchings in a complete bipartite graph Kn,n are (n-1)!
The number of perfect matchings in a complete graph with 5 vertiecs are 945
The number of perfect matchings in a complete graph with 4 vertices are 105
The number of perfect matchings in a complete graph of K2n vertices is same as pairing up 2n distinct people
Correct Answer
Option 4
Solution
A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching.
There will be no perfect matchings in a complete graph with an odd number of vertices. So, there will be no perfect matchings for the complete graph with 5 vertices.
The number of perfect matchings in a complete bipartite graph Kn,n are n! Is a fact.
The number of perfect matchings in a complete graph of K2n vertices is the same as pairing up 2n distinct people is also a fact. The number of perfect matchings are (2n!)/n!2^n.
When 2n=4, it is 4!/2!*2^2 = 3
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
T(n)=3n
T(n)=(2n-3)/n
T(n)=2n-3
No solution possible
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Correct Answer
Option 3
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
There is a bag of words with more than 200 words. We need a set S with size x such that there must be atleast two words begin with the same letter. The value of size of ‘x’ is _____
27
Correct Answer
Option 1
Solution
Pigeonhole Principle :
If k is a positive integer and k + 1 objects are placed into k boxes, then at least one of the
boxes will contain two or more objects.
There are 26 alphabets. We can have a set with 26 words with different starting letters. If we add any word to it, we can confirm that there are at least two words with the same beginning letter.
As per the pigeonhole principle, there are k boxes / 26alphabets. If there are k+1 boxes/26+1 words we can say that atleast box/set has more than one object/word with same beginning letter
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
The number of ways the alphabets in the word “ RAVINDRABABU” can be arranged such that all vowels are together and all consonants are together is ___
50400
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
The number of arrangements of the digits 2,3,4,4,5 such that the 5-digit number formed is divisible by 4 are -----
18
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
The chromatic number of the following graph is ________
4
Correct Answer
Option 1
Solution
Note: Every planar graph can be colored with utmost 4 colors.
It is one of the critical graphs where we must use 4 colors.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
Let ‘e’ denote the number of edges and ‘n’ denote the number of vertices in a graph G. ___ is the minimum value of e+n such that the graph G has 10 faces and minimum degree is 3.
22
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
A bucky ball consists of 12 pentagons and 20 hexagons. The number of faces in buckyballs with 60 vertices and 90 edges is______________
20
32
12
31
Correct Answer
Option 2
Solution
Euler's formula : V - E + F = 2
where
V = number of vertices
E = number of edges
F = number of faces
Here, V=60 E=90. Thus 60-90+f=2
f=32
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
There are two cyclic graphs G1 and G2.
G1 has 799 vertices and G2 has 201 vertices. It is found that G1, G2 have the same chromatic number. Then what is the chromatic number of G1 and G2 _________
3
Correct Answer
Option 1
Solution
The chromatic number of the odd-cycle is 3.
If it is an even cycle, then its chromatic number is 2.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
The vertex cut of the following graph is __
2
Correct Answer
Option 1
Solution
There are two vertices with degree 2. If we remove the edges incident on them will create a new component.
Remove the red colored vertices here. Vertex cut size is 2.
We get isolated vertex and two components
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
In a bipartite graph Km,n the maximum size of a matching is equals to
Minimum vertex cover, min(m,n)
Minimum vertex cover, max(m,n)
Maximum vertex cover min(m,n)
Maximum vertex cover max(m,n)
Correct Answer
Option 1
Solution
A matching in a graph is a set of edges that do not have a set of common vertices
A vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
If G is a bipartite graph, then maximum size of matching in G is equal to the minimum size of a vertex cover..
Minimum vertex cover in Kmn is min(m,n).
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
The number of simple graphs possible with 5 vertices are ___
1024
Correct Answer
Option 1
Solution
The number of simple graphs with ‘n’ vertices are 2^(nC2).
