BTechibtechi.in
Loading Loading
Free IIT Madras BS notes, PYQs and mock tests at btechi.in

Maths I · Graphs: BFS, DFS, colouring & covers

BSMA1001 · 10 questions · 37 marks · 4 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

BSMA1001 · Mathematics for Data Science I

Graphs: BFS, DFS, colouring & covers

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
MSQ: One or more options correct. Select all to score.
NAT: Numerical response. No negative marking.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

End Term · 31 Aug 2025 (FN)End Term

Q1MSQ3 Marks·Choose all correct options
Key ↓
The following tree is the BFS tree rooted at node P of an undirected graph : Which of the following edges cannot exist in the original graph?
1. A(T, V)
2. B(U, R)
3. C(P, U)
4. D(W, P)
Q2NAT4 Marks·Write the number
Asked 4 times Key ↓
Your answer:

End Term · 13 Apr 2025 (FN)End Term

Q3MSQ4 Marks·Choose all correct options
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
Q4MSQ4 Marks·Choose all correct options
Asked 2 times Key ↓
1. AIf we perform Breadth-First Search at node 0, then one of the possible orders in which the nodes will be visited is 01423567.
2. BIf we perform Depth First Search at node 0, then one of the possible order in which the nodes will be visited is 04123576
3. CIf we perform Breadth-First Search at node 0, then one of the possible orders in which the nodes will be visited is 01423765.
4. DIf we perform Depth First Search at node 0, then one of the possible orders in which the nodes will be visited is 04132567.
Read the passage below, then answer Q5
Suppose Nitya wishes to find the minimum cost spanning tree of the graph given below. While finding the minimum cost spanning tree she finds that a few edge weights are missing (x and y) but she is sure that the weight of the minimum cost spanning tree is 15 in the graph.
Based on the above data, answer the given subquestions.
Q5NAT3 Marks·Write the number
Asked 4 times Key ↓
What is the minimum number of colors required to properly color the vertices of the given graph such that no two adjacent vertices share the same color?
Your answer:

End Term · 13 Apr 2025 (AN)End Term

Q6MSQ4 Marks·Choose all correct options
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
Q7MSQ4 Marks·Choose all correct options
Asked 2 times Key ↓
1. AIf we perform Breadth-First Search at node 0, then one of the possible orders in which the nodes will be visited is 01246573.
2. BIf we perform Depth First Search at node 7, then one of the possible order in which the nodes will be visited is 74356012
3. CIf we perform Breadth-First Search at node 0, then one of the possible orders in which the nodes will be visited is 01264537.
4. DIf we perform Depth First Search at node 0, then one of the possible orders in which the nodes will be visited is 76435012.
Read the passage below, then answer Q8
Based on the above data, answer the given subquestions.
Q8NAT3 Marks·Write the number
Asked 4 times Key ↓
What is the minimum number of colors required to properly color the vertices of the given graph such that no two adjacent vertices share the same color?
Your answer:

End Term · 22 Dec 2024 (FN)End Term

Q9MSQ3 Marks·Choose all correct options
Key ↓
1. AThe Number of edges is 8.
2. BThe Number of vertices is 5.
3. CThe Number of edges is 7.
4. DEach vertex has degree 3.
Q10NAT5 Marks·Write the number
Asked 4 times Key ↓
Your answer:

Official Key

Master Answer Key & Explanations

Official answer keys from IIT Madras BS past papers. Click any question to review.

Reveal Key

Q1C, D

Q23

Q3A, D

Q4A, D

Q54

Q6B, C

Q7B, C

Q84

Q9B, C

Q103

Questions and answer keys are reproduced from the official IIT Madras BS papers. Topics and repeated question types are BTechi’s own grouping. BTechi is not affiliated with IIT Madras.