Skip to content
GATEiit

GATE DA 2025 Q58: Shortest paths: which edges cannot be in G?

Question

Let GG be a simple, unweighted, and undirected graph. A subset of the vertices and edges of GG are shown below.

Graph with vertices a, b, c, d in the top row and e, f, g, h in the bottom row. Edges: a–b, b–c, c–d, a–f, e–f, f–c, f–g, g–h, c–h.
Tap the figure to enlarge

It is given that a−b−c−da - b - c - d is a shortest path between aa and dd; e−f−g−he - f - g - h is a shortest path between ee and hh; a−f−c−ha - f - c - h is a shortest path between aa and hh. Which of the following is/are NOT the edges of GG?

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: A, C, D (official GATE 2025 final answer key)

Concept used: A given shortest path rules out any edge that would create a shorter route.

First step: Each given shortest path has length 3. Test each candidate edge: does adding it give a path of length 2 between the same endpoints? For example, (b,d)(b, d) would give a−b−da - b - d.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 DA question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Programming, Data Structures and Algorithms PYQs

PracticePractise Programming, Data Structures and Algorithms questions →Full paperAll GATE DA 2025 questions →