GATE 2025 DA Q.58: solution and answer

GATE 2025 · DAQ.58 · 2 marks · MSQ

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

It is given that $a - b - c - d$ is a shortest path between $a$ and $d$ ; $e - f - g - h$ is a shortest path between $e$ and $h$ ; $a - f - c - h$ is a shortest path between $a$ and $h$ . Which of the following is/are NOT the edges of $G$ ?

GATE 2025 DA question 58: Eight vertices in two rows. — Figure from the GATE 2025 DA paper. It is part of the question.

(A)
$(b, d)$
(B)
$(b, g)$
(C)
$(b, h)$
(D)
$(e, g)$

Answer and solution

ANSWER

The edges that cannot be in $G$ are $(b, d)$ , $(b, h)$ and $(e, g)$ , so the answer is (A), (C), (D).

Official answer: A, C, DSource: Official answer key, GATE 2025 DA (IIT Roorkee)

The figure shows the edges $a - b$ , $b - c$ , $c - d$ , $e - f$ , $f - g$ , $g - h$ , $a - f$ , $c - f$ and $c - h$ . In an unweighted graph the length of a path is its number of edges, and a path is a shortest path only if no edge of $G$ gives a shorter route between its end points.
$a - b - c - d$ is a shortest path, so $d (a, d) = 3$ . If $(b, d)$ were an edge, $a - b - d$ would have length $2 < 3$ . So $(b, d)$ is NOT an edge of $G$ .
$e - f - g - h$ is a shortest path, so $d (e, h) = 3$ . If $(e, g)$ were an edge, $e - g - h$ would have length $2 < 3$ . So $(e, g)$ is NOT an edge of $G$ .
$a - f - c - h$ is a shortest path, so $d (a, h) = 3$ . If $(b, h)$ were an edge, $a - b - h$ would have length $2 < 3$ . So $(b, h)$ is NOT an edge of $G$ .
Now test $(b, g)$ . Suppose it is added to the drawn edges. The route $a - b - g - h$ has length $3$ , which equals $d (a, h) = 3$ , so $a - f - c - h$ is still shortest. Any route from $e$ to $h$ that uses $(b, g)$ must first reach $b$ , which takes at least $3$ edges from $e$ ( $e - f - a - b$ or $e - f - c - b$ ), so it is longer than $3$ . Any route from $a$ to $d$ that uses $(b, g)$ must pass through $g$ and then reach $d$ only via $c$ , so it is longer than $3$ . All three given shortest-path conditions still hold, so $(b, g)$ is allowed to be an edge. It is not forced to be absent.
Hence the pairs that are definitely NOT edges of $G$ are $(b, d)$ , $(b, h)$ and $(e, g)$ , which are options (A), (C) and (D).

KEY IDEA

In an unweighted graph a path is shortest only if no edge of the graph creates a shorter route between its end points. Each given shortest path therefore forbids every chord that would shorten it.

WATCH OUT FOR

Marking $(b, g)$ as a non-edge because it looks like a chord. It creates the route $a - b - g - h$ of length 3, which only ties $d (a, h) = 3$ and does not shorten any of the three given shortest paths, so it is allowed. Also forgetting that $d (a, h) = 3$ comes from the third path, which is what rules out $(b, h)$ .

From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2025 DA Q.58: solution and answer

Answer and solution

More Graph algorithms questions