GATE 2025 DA – Question 58
Let $G$ be a simple, unweighted, and undirected graph. A subset of the vertices and edges of $G$ are shown below.
[Figure: Eight vertices in two rows. Top row: a, b, c, d. Bottom row: e, f, g, h. The edges drawn are a-b, b-c, c-d, a-f, f-c, c-h, e-f, f-g and g-h.]
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$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $(b, d)$; (C) $(b, h)$; (D) $(e, g)$
Explanation
A shortest path stays shortest only if no edge gives a shortcut. The path $a-b-c-d$ has length 3, so $(b, d)$ would give the path $a-b-d$ of length 2, and $(b, d)$ cannot be an edge. The path $a-f-c-h$ has length 3, so $(b, h)$ would give $a-b-h$ of length 2, which is not allowed. The path $e-f-g-h$ has length 3, so $(e, g)$ would give $e-g-h$ of length 2, which is not allowed. The edge $(b, g)$ creates $a-b-g-h$, which has the same length 3, so it breaks none of the given shortest paths and may exist.