Graph, Route and Tournament Reasoning Practice Questions for GATE CS

Solve 48+ Graph, Route and Tournament Reasoning practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Graph, Route and Tournament Reasoning

Chapter Roadmap

Graph, Route and Tournament Reasoning

This chapter transitions you from linear logical reasoning to network and spatial reasoning. You will learn to abstract real-world scenarios into mathematical graphs, allowing you to solve complex connectivity and routing problems with simple, universal rules.

Graph Connectivity and Minimum Bridges

Focus: Modeling land zones and rivers as vertices and edges.
Master: Using the $V - 1$ rule to find the absolute minimum bridges needed to connect all regions.

Knockout Tournament Elimination

Focus: Binary tree structures in sports or competition brackets.
Master: Calculating total matches or eliminated players instantly without simulating the bracket.

Hamiltonian Routes and Round Trips

Focus: Pathfinding through interconnected nodes.
Master: Identifying valid paths that visit every city exactly once and return to the start, while avoiding dead ends.

Graph Connectivity and Minimum Bridges

Connecting isolated regions with maximum efficiency and zero waste.

Logic › Graph, Route and Tournament Reasoning

What you will master here:

Abstracting real-world geography (zones and rivers) into graph theory components (vertices and edges).
Applying the fundamental $V - 1$ connectivity rule for minimum spanning trees.
Identifying and ignoring visual distractors, such as the total number of river segments.
Executing a rapid, two-step verification process for network connectivity questions.

Graph, Route and Tournament Reasoning: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Analytical Aptitude MCQ

A river system splits the land into several distinct zones. If the minimum number of bridges required to connect all these zones is 8, how many distinct zones are there?

A.
7
B.
8
C.
9
D.
10

Correct Answer:

Step-by-Step Solution

Key idea: This is a reverse-engineering minimum connectivity problem.

Step 1: Recall the minimum connectivity rule: $Minimum Bridges = V - 1$ .

Step 2: We are given $Minimum Bridges = 8$ .

Step 3: Substitute into the formula: $8 = V - 1$ .

Step 4: Solve for $V$ : $V = 8 + 1 = 9$ .

Answer: 9

Question 2 · Analytical Aptitude MCQ

Assertion (A): In a Hamiltonian cycle, if a vertex has exactly two incident edges, both edges must be part of the cycle.

Reason (R): A Hamiltonian cycle focuses on traversing every edge exactly once, making all edges of a degree-2 vertex mandatory.

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing the distinction between Hamiltonian and Eulerian concepts.

Step 1: Evaluate Assertion (A). In a Hamiltonian cycle, every vertex must be visited exactly once. If a vertex has degree 2, both edges must be used to enter and exit the vertex. Thus, A is true.

Step 2: Evaluate Reason (R). R states that Hamiltonian cycles focus on traversing every edge exactly once. This is false; that is the definition of an Eulerian circuit. Hamiltonian cycles focus on visiting every vertex exactly once.

Step 3: Since A is true and R is false, the correct option is C.

Answer: A is true but R is false.

Question 3 · Analytical Aptitude MCQ

A graph with 6 vertices has three vertices of degree 2. The mandatory edges for these three vertices form a closed loop of 3 vertices, excluding the other 3 vertices. Which of the following is true?

A.
A Hamiltonian path is impossible, but a cycle is possible.
B.
A Hamiltonian cycle is impossible because the mandatory edges form a premature loop.
C.
A Hamiltonian cycle is possible if the loop is traversed twice.
D.
A Hamiltonian cycle is guaranteed if the remaining 3 vertices are fully connected.

Correct Answer:

Step-by-Step Solution

Key idea: This is a boundary case problem testing the degree-2 vertex rule and premature loops.

Step 1: Identify the degree-2 vertices. Their incident edges are mandatory for any Hamiltonian cycle.

Step 2: The problem states these mandatory edges form a closed loop of 3 vertices.

Step 3: A Hamiltonian cycle must visit all 6 vertices exactly once. A loop of 3 vertices is a premature cycle that does not include the other 3 vertices.

Step 4: Therefore, a Hamiltonian cycle is impossible.

Answer: A Hamiltonian cycle is impossible because the mandatory edges form a premature loop.

Question 4 · Analytical Aptitude MCQ

According to the Connectivity Rapid Execution Protocol, which of the following statements correctly describes the final verification step before confirming the minimum number of bridges?

A.
Verify that the number of river segments is less than the number of zones.
B.
Ensure no zone is described as fundamentally unbridgeable.
C.
Calculate the total area of all land zones to check for proportionality.
D.
Confirm that the number of bridges is exactly equal to the number of zones.

Correct Answer:

Step-by-Step Solution

Key idea: The Connectivity Rapid Execution Protocol has a specific final step to ensure the formula's validity.

Step 1: Recall the 4 steps of the protocol: Isolate Zones, Discard Noise, Apply Core Rule ( $V - 1$ ), Verify Constraints.

Step 2: The final step is to verify constraints, specifically checking if any zone is fundamentally unbridgeable.

Step 3: Match this with the options. Option B correctly states this verification step.

Answer: Ensure no zone is described as fundamentally unbridgeable.

Question 5 · Analytical Aptitude MCQ

A single-elimination knockout tournament begins with 64 players. There are no ties. What is the minimum number of matches that must be played to declare the winner?

A.
62
B.
63
C.
64
D.
127

Correct Answer:

Step-by-Step Solution

Key idea: This is a single-elimination tournament problem. The core invariant is that each match eliminates exactly one player.

Step 1: Identify the total number of starting players, $N = 64$ .

Step 2: To find exactly 1 winner, $64 - 1 = 63$ players must be eliminated.

Step 3: Since each match eliminates exactly 1 player, the total number of matches is exactly 63.

Answer: 63

Question 6 · Analytical Aptitude MCQ

Match the graph property in List I with its implication for a Hamiltonian cycle in List II.

List I:

P. Graph contains a cut vertex

Q. Graph is a simple cycle of 5 vertices

R. Graph has a vertex of degree 2

List II:

Both incident edges are mandatory
Hamiltonian cycle is impossible
Hamiltonian cycle is guaranteed

A.
P-2, Q-3, R-1
B.
P-1, Q-2, R-3
C.
P-2, Q-1, R-3
D.
P-3, Q-1, R-2

Correct Answer:

Step-by-Step Solution

Key idea: This is a matching question testing the core rules for Hamiltonian cycles.

Step 1: Evaluate P. A cut vertex disconnects the graph if removed, making a single continuous loop impossible. Thus, P matches 2.

Step 2: Evaluate Q. A simple cycle of 5 vertices visits all vertices exactly once and returns to the start. Thus, Q matches 3.

Step 3: Evaluate R. A vertex of degree 2 must use both its edges in any Hamiltonian cycle. Thus, R matches 1.

Step 4: The correct matching is P-2, Q-3, R-1.

Answer: P-2, Q-3, R-1

Question 7 · Analytical Aptitude MCQ

A geographical map displays 4 distinct land zones. A single winding river separates them, creating 6 visible segments of water in the diagram. What is the absolute minimum number of bridges needed to connect all 4 zones into a single network?

A.
6
B.
5
C.
4
D.
3

Correct Answer:

Step-by-Step Solution

Key idea: This is a minimum connectivity problem. The number of river segments is a visual distractor.

Step 1: Identify the number of distinct land zones (vertices), $V = 4$ .

Step 2: Ignore the 6 river segments, as they do not affect the minimum number of bridges.

Step 3: Apply the minimum connectivity rule: $Minimum Bridges = V - 1$ .

Step 4: Calculate $4 - 1 = 3$ .

Answer: 3

Question 8 · Analytical Aptitude MCQ

A map shows $V$ distinct land zones. According to the fundamental rule of graph connectivity, which of the following pairs of $(V, Minimum Bridges)$ is mathematically impossible for a fully connected network?

A.
(5, 4)
B.
(10, 9)
C.
(8, 8)
D.
(12, 11)

Correct Answer:

Step-by-Step Solution

Key idea: This is a boundary case question testing the validity of the connectivity formula.

Step 1: Recall the fundamental rule: $Minimum Bridges = V - 1$ .

Step 2: Check Option A: $V = 5 ⟹ 5 - 1 = 4$ . Possible.

Step 3: Check Option B: $V = 10 ⟹ 10 - 1 = 9$ . Possible.

Step 4: Check Option C: $V = 8 ⟹ 8 - 1 = 7$ . The option says 8 bridges. This is impossible.

Step 5: Check Option D: $V = 12 ⟹ 12 - 1 = 11$ . Possible.

Answer: (8, 8)

Question 9 · Analytical Aptitude MCQ

In a single-elimination tournament with 50 players, some players receive a bye in the first round. Which of the following statements correctly describes the total number of matches played?

A.
It is less than 49 because byes reduce the total matches.
B.
It is exactly 49, as byes do not affect the total number of eliminations.
C.
It is 50, because every player must play at least one match.
D.
It cannot be determined without knowing the exact bracket structure.

Correct Answer:

Step-by-Step Solution

Key idea: This is a non-power-of-two tournament problem. The elimination invariant holds regardless of byes.

Step 1: Identify the total number of starting players, $N = 50$ .

Step 2: To find 1 winner, $50 - 1 = 49$ players must be eliminated.

Step 3: Byes simply advance players without playing a match, but they do not change the total number of eliminations required.

Step 4: Total matches = 49.

Answer: It is exactly 49, as byes do not affect the total number of eliminations.

Question 10 · Analytical Aptitude MCQ

A bipartite graph has two disjoint sets of vertices, Set A and Set B. If a Hamiltonian cycle exists in this graph and Set A contains 7 vertices, how many vertices must Set B contain?

A.
6
B.
7
C.
8
D.
14

Correct Answer:

Step-by-Step Solution

Key idea: This is a bipartite graph constraint problem for Hamiltonian cycles.

Step 1: Recall the rule for bipartite graphs: edges only connect vertices from different sets.

Step 2: For a Hamiltonian cycle to exist, the cycle must alternate between Set A and Set B.

Step 3: To form a closed loop, the number of vertices in Set A must exactly equal the number of vertices in Set B ( $∣ A ∣ = ∣ B ∣$ ).

Step 4: Since Set A has 7 vertices, Set B must also have 7 vertices.

Answer: 7

Try a question

Login to view the complete practice questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Graph, Route and Tournament Reasoning Practice Questions for GATE CS

Chapter Roadmap: Graph, Route and Tournament Reasoning

Chapter Roadmap

Graph Connectivity and Minimum Bridges

Knockout Tournament Elimination

Hamiltonian Routes and Round Trips

Graph Connectivity and Minimum Bridges

Graph Connectivity and Minimum Bridges

What you will master here:

Graph, Route and Tournament Reasoning: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit