The CAT QA section requires speed and accuracy, along with a thorough understanding of the Graph Theory. This article provides a set of MCQs on Graph Theory to help you understand the topic and improve your problem-solving skills with the help of detailed solutions by ensuring conceptual clarity, which will help you in the CAT 2025 exam preparation
Whether you're revising the basics or testing your knowledge, these MCQs will serve as a valuable practice resource.
The CAT 2025 exam is expected to follow a similar trend to the CAT 2024, with 22 questions from the QA section out of a total of 68 questions.
Also Read
CAT MCQs on Graph Theory
1. Three Englishmen and three Frenchmen each know one unique secret. Only one Englishman knows French, no Frenchman knows English. They exchange secrets via person-to-person calls so all know all secrets. What is minimum number of calls?
A
5
B
10
C
9
D
15
2. The network diagram shows cities A, B, C, D, E, F with arrows as permissible travel. How many distinct paths exist from A to F?
A
9
B
10
C
11
D
None of these
3. ABCDEFGH is a regular octagon. A and E are opposite vertices. A frog starts at A, may jump to adjacent vertices except E. When it reaches E, it stops. Let \(a_n\) = number of distinct paths of exactly n jumps ending at E. Find \(a_{2n-1}\).
A
Zero
B
Four
C
2n - 1
D
Can't be determined
4. Four cities are connected by roads as shown. In how many ways can you start at a city and come back to it without travelling the same road more than once?
A
1
B
2
C
3
D
4
5. In a six-node network, two nodes are connected to all the other nodes. Of the remaining four, each is connected to four nodes. What is the total number of links in the network?
A
13
B
15
C
7
D
26
Comments