Paper 2 CS · UNIT 01 · MOCK TEST

Mock 8 – Graph Theory (Part 1)

Unit 1: Discrete Structures and Optimisation · 18 questions · about 21 minutes. Press End Mock any time to see your score and the correct answers.

All 14 topic-wise mocks in this unit

0 / 18 answered 00:00

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

A60 B15 C20 D30

Q2. A tree is :
A. a circuitless connected graph
B. a connected graph of 'n' vertices with (n − 1) edges
C. a circuitless graph of 'n' vertices with (n − 1) edges
D. a minimally connected graph
Choose the correct answer from the options given below :

AA, B and C only BB, C and D only CA, B, C and D DA and B only

Q3. Consider the following List-I and List-II in context of graph & model.

LIST-I	LIST-II
A. Planar Graph	I. Probabilistic Model
B. Bipartite Graph	II. Deterministic Model
C. PERT	III. 4 - Colorable
D. CPM (Critical Path Method)	IV. 2 - Colorable

Choose the correct answer from the options given below:

AA-III, B-IV, C-I, D-II BA-IV, B-III, C-I, D-II CA-II, B-IV, C-I, D-III DA-III, B-IV, C-II, D-I

Q4. The number of vertices of odd degree in any graph of 'n' vertices with 'e' edges is :

Aodd Beven C(n − e) Dprime

Q5. Arrange the following graphs on the basis of number of edges in increasing order (for large n):
A. Kₙ (Complete Graph)
B. Cₙ (Cycle graph)
C. Wₙ (Wheel graph)
D. Kₙ,ₙ (Complete Bipartite Graph)
E. Qₙ (n-cube graph)
Choose the correct answer from the options given below:

AA, B, C, D, E BB, C, A, D, E CA, B, C, E, D DE, D, C, A, B

Q6. Which of the following graphs is/are planar?
Graph A (vertices a–f): edges ab, ac, bd, cf, de, ef, bf, cd.
Graph B (vertices a–f): edges af, ae, ad, ac, bf, bc, bd, ef, df, ce.
Graph C (vertices a–i): edges hi, hg, he, ia, if, ag, ae, ad, ab, bf, be, cf, cd, de, fg.
Choose the most appropriate answer from the options given below:

AA and C only BB only CA only DA and B only

Q7. A graph G with n ≥ 3 vertices is a Hamiltonian graph if the degree of each vertex is greater than or equal to

Athe number of vertices Bdouble the number of vertices Chalf the number of vertices Dfour times the number of vertices

Q8. Let G(V, E) be an undirected graph with l edges. Then the sum of the degrees of all vertices is equal to

A2l Bl/2 Cl² D√l

Q9. Which of the following graphs (on vertices a–f) are trees?
(A) edges: ac, bc, cd, cf, ef
(B) edges: ac, af, df, ef, be
(C) edges: ab, ac, ad, be, cf, de
(D) edges: af, be, bd, ce
Choose the correct answer from the options given below:

A(A) and (B) only B(A), (B) and (D) only C(A) and (D) only D(A), (B), (C) and (D) only

Q10. There are m points on one straight line AB and n points on another straight line AC, none of them being A. How many triangles can be formed with these points as vertices?

Amn(m + n − 2) B½ mn(m + n − 2) C½ mn(m + n − 1) Dmn(m + n − 1)

Q11. Arrange the following simple graphs by the number of spanning trees they have (increasing):
A. K₃ (complete graph on 3 nodes)
B. K₄ (complete graph on 4 nodes)
C. K₂,₂ (complete bipartite graph with 2 nodes in each part)
D. C₅ (cycle graph on 5 nodes)
Choose the correct answer from the options given below:

AA, B, C, D BA, C, B, D CA, C, D, B DD, B, C, A

Q12. Which of the following is NOT a common property of social networks?

AThe degree distribution follows a scale-free (power-law) distribution BAverage shortest path lengths are short in connected networks CMost of them are directed networks DThey follow the small-world property

Q13. Consider the following statements:
A. The number of labelled binary trees possible with n nodes is (2n)!/(n+1)!
B. The number of binary search trees possible with n (distinct) keys is (2n)!/((n+1)! n!)
C. The number of unlabelled binary trees possible with n nodes is C(2n, n)/(n+1)!
D. The number of simple, undirected, labelled graphs possible with n vertices is 2^(n(n−1)/2)
Choose the correct answer from the options given below:

AA, B and C are only correct BA, B and D are only correct CB, C and D are only correct DA, C and D are only correct

Q14. Let G be a simple undirected graph with n (n > 10) vertices and k connected components. What is the minimum possible number of edges of G?

Ak(n − 1) Bn(k − 1) Cn + k − 2 Dn − k

Q15. Consider the following graph with vertices A, B, C, D and edges:
A – B, B – C, A – D, B – D, C – D
(A, B, C lie in a row; D is below and joined to all three.)
How many spanning trees can be found?

A10 B5 C9 D8

Q16. Consider the following statements:
P: There exists no simple, undirected and connected graph with 80 vertices and 77 edges.
Q: All vertices of an Euler graph are of even degree.
R: Every simple, undirected, connected and acyclic graph with 50 vertices has at least two vertices of degree one.
S: There exists a bipartite graph with more than ten vertices which is 2-colourable.
What is the number of correct statements?

A1 B2 C3 D4

Q17. Match List I with List II.
Choose the correct answer from the options given below:

List I	List II
a. Planar graph	I. Probabilistic model
b. Bipartite graph	II. Deterministic model
c. PERT	III. 4-colourable
d. CPM	IV. 2-colourable

Aa-IV, b-III, c-I, d-II Ba-III, b-IV, c-II, d-I Ca-II, b-IV, c-I, d-III Da-III, b-IV, c-I, d-II

Q18. Match List – I with List – II.
List I: (A) LRU (B) Demand cleaning (C) Long term scheduling (D) Medium term scheduling
List II: (I) Page not referenced for the longest time is replaced (II) Page is written to secondary memory only when it has been selected for replacement (III) Decision to add a process to the pool of processes to be executed (IV) Decision to add a process, partially or fully, to main memory

A(A)-(I), (B)-(III), (C)-(IV), (D)-(II) B(A)-(II), (B)-(I), (C)-(III), (D)-(IV) C(A)-(III), (B)-(II), (C)-(I), (D)-(IV) D(A)-(IV), (B)-(II), (C)-(III), (D)-(I)

Next: Mock 9 – Graph Theory (Part 2) →