The GATE Grind

GATE 2025 DA – Question 58

Programming, Data Structures and Algorithms · Graph theory and basic graph algorithms · 2 marks · Multiple select

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$?

Diagram for GATE 2025 DA question 58
  1. $(b, d)$
  2. $(b, g)$
  3. $(b, h)$
  4. $(e, 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.

More Graph theory and basic graph algorithms questions

All Graph theory and basic graph algorithms questions →