chapter
    Graph, Route and Tournament Reasoning PYQs for GATE CS

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

    Try a question

    Answer it here to see how it works. Nothing is recorded until you sign in.

    Question 1
    2026 Slot Set2 PYQ
    Level 3: Exam Standard
    Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the line segments between them represent intercity highways.
    A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which she started.

    Which one of the following options is then true?
    (i) (ii)
    Question 2
    2026 Slot Set1 PYQ
    Level 3: Exam Standard

    Consider a knock-out women’s badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeated or remains the last undefeated player. The last undefeated player is declared the winner of the tournament. If there are 64 players in the beginning of the tournament, how many games should be played in total to declare the winner of the tournament?

    Question 3
    2025 Slot Set2 PYQ
    Level 3: Exam Standard
    The diagram below shows a river system consisting of 7 segments, marked P, Q, R, S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, and Z5. We need to connect these zones using the least number of bridges. Out of the following options, which one is correct?

    Note: The figure shown is representative.

    PQRSTUVZ1Z2Z3Z4Z5
    Free preview ends here

    Login to view the complete previous-year questions and solutions

    Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

    Login to continueSee plans
    Why MastersUp

    Personalised first. High quality throughout.

    Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

    Built around you, not around a syllabus PDF

    Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

    Revision that hits your weak spots

    We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

    Questions calibrated to the real exam

    Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

    Notes written for recall, not for volume

    Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

    One place for everything

    Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

    Honest progress

    No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

    Unlock the whole course

    Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

    View all plansStart free

    Graph, Route and Tournament Reasoning PYQs for GATE CS

    Solve 3+ Graph, Route and Tournament Reasoning previous year 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.

    1

    Graph Connectivity and Minimum Bridges

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

    2

    Knockout Tournament Elimination

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

    3

    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

    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 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 (3 Problems)

    Question 1 · Analytical Aptitude · 2026_Set2 MCQ
    Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the line segments between them represent intercity highways.
    A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which she started.

    Which one of the following options is then true?
    (i) (ii)
    1. A.

      Such a trip is possible for (i), but not for (ii).

    2. B.

      Such a trip is possible for (ii), but not for (i).

    3. C.

      Such a trip is possible for both (i) and (ii).

    4. D.

      Such a trip is possible neither for (i) nor for (ii).

    Correct Answer:

    A

    Step-by-Step Solution

    Insight: A Hamiltonian cycle requires every vertex to have a degree of exactly 2 within the cycle. Graph (ii) has three vertices of degree 2, which forces a contradiction at the central vertex. Graph (i) is a 4x4 grid, which is bipartite with equal partitions, allowing a valid cycle.

    Exam route: For (ii), identify vertices with degree 2. Their incident edges must be in the cycle. This forces the central vertex to have degree 3 in the cycle, which is impossible. Thus, (ii) has no Hamiltonian cycle. For (i), a 4x4 grid has a known Hamiltonian cycle (e.g., a snake pattern that closes). Thus, (i) is possible, (ii) is not.

    Learning route:

    1. Understand the goal: A trip visiting every city exactly once and returning to the start is a Hamiltonian cycle.
    2. Analyze Graph (ii): It has 5 vertices. The top-left, bottom, and top-right vertices each have exactly 2 connections (degree 2).
    3. Apply the Degree-Two Vertex Rule: In any Hamiltonian cycle, if a vertex has degree 2, both of its edges must be part of the cycle.
    4. Trace the forced edges in (ii): The three degree-2 vertices force 6 edges. However, these edges all converge on the central vertex, giving it a degree of 3 in the supposed cycle. A cycle can only have degree 2 for every vertex. This is a contradiction, so (ii) is impossible.
    5. Analyze Graph (i): It is a 4x4 grid graph. It is bipartite with 8 black and 8 white vertices. Since the partitions are equal, a Hamiltonian cycle is possible. We can explicitly construct one by tracing the perimeter and weaving through the center without repeating vertices.
    6. Conclusion: Possible for (i), not for (ii).
    Question 2 · Analytical Aptitude · 2026_Set1 MCQ

    Consider a knock-out women’s badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeated or remains the last undefeated player. The last undefeated player is declared the winner of the tournament. If there are 64 players in the beginning of the tournament, how many games should be played in total to declare the winner of the tournament?

    1. A.

      127

    2. B.

      64

    3. C.

      63

    4. D.

      32

    Correct Answer:

    C

    Step-by-Step Solution

    Insight: In a single-elimination tournament, every match eliminates exactly one player. To find the champion, all other players must be eliminated.

    Exam route: Total players . Number of winners = 1. Players to eliminate = . Since 1 match = 1 elimination, total matches = 63.

    Learning route:

    1. Identify the tournament type: Single-elimination (knock-out) with no ties.
    2. Identify the invariant: Every match produces exactly one loser, who is eliminated.
    3. Determine the goal: We start with 64 players and need exactly 1 winner.
    4. Calculate eliminations: To leave 1 winner, players must be eliminated.
    5. Apply the invariant: Since each match eliminates exactly one player, exactly 63 matches are required.
    6. Verify: Round 1 has 32 matches (32 eliminated, 32 remain). Round 2 has 16 matches. Round 3: 8 matches. Round 4: 4 matches. Round 5: 2 matches. Round 6: 1 match. Total = . The invariant holds perfectly.
    Question 3 · Analytical Aptitude · 2025_Set2 MCQ
    The diagram below shows a river system consisting of 7 segments, marked P, Q, R, S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, and Z5. We need to connect these zones using the least number of bridges. Out of the following options, which one is correct?

    Note: The figure shown is representative.

    PQRSTUVZ1Z2Z3Z4Z5
    1. A.

      Bridges on P, Q, and T

    2. B.

      Bridges on P, Q, S, and T

    3. C.

      Bridges on Q, R, T, and V

    4. D.

      Bridges on P, Q, S, U, and V

    Correct Answer:

    C

    Step-by-Step Solution

    Insight: The minimum number of bridges to connect zones is always , regardless of the number of river segments. We must find the option with exactly 4 bridges that connects all 5 zones.

    Exam route: Total zones . Minimum bridges = . Eliminate options with 3 or 5 bridges (Options 1 and 4). Between Options 2 and 3, Option 2 (P, Q, S, T) only connects zones on the left and middle, leaving the rightmost zone (Z4) isolated because it requires U or V. Option 3 (Q, R, T, V) includes V, which connects the rightmost zone, and forms a valid spanning tree.

    Learning route:

    1. Abstract the problem: We need to connect distinct zones with the minimum number of bridges.
    2. Apply the Minimum Connectivity Rule: The absolute minimum number of bridges required is .
    3. Filter options by count: Option 1 has 3 bridges (too few, graph will be disconnected). Option 4 has 5 bridges (not the minimum, contains a redundant cycle). We are left with Options 2 and 3.
    4. Analyze the geography (ignoring the 7 river segments distractor):
    • Option 2 uses P, Q, S, T. These segments are clustered on the left and center. The rightmost zone (Z4) is separated by segments U and V. Since neither U nor V is chosen, Z4 remains completely isolated.
    • Option 3 uses Q, R, T, V. Segment V explicitly connects the rightmost zone (Z4) to the rest of the network. Segments R, T, and Q connect the remaining zones (Z2, Z3, Z5, Z1) into a single component without forming cycles.
    1. Conclusion: Option 3 is the only valid set of 4 bridges that connects all 5 zones.

    More previous year questions (pyqs) in this unit