GATE DA 2025 | Question 58

MSQ · 2 marks

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

Eight vertices in two rows, a, b, c, d on top and e, f, g, h below. Edges join a and b, b and c, c and d, e and f, f and g, g and h, and also a and f, f and c, and c and 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\)?

  1. Option A: \((b, d)\) (correct)
  2. Option B: \((b, g)\)
  3. Option C: \((b, h)\) (correct)
  4. Option D: \((e, g)\) (correct)

Answer

(A), (C), (D)

Explanation

Each given shortest path has 3 edges, so in \(G\) the distances between \(a\) and \(d\), \(e\) and \(h\), and \(a\) and \(h\) are all exactly 3. An edge that would create a path of length 2 between one of these pairs cannot be in \(G\).

  • \((b, d)\) would give \(a - b - d\), of length 2 between \(a\) and \(d\). Not an edge.
  • \((b, h)\) would give \(a - b - h\), of length 2 between \(a\) and \(h\). Not an edge.
  • \((e, g)\) would give \(e - g - h\), of length 2 between \(e\) and \(h\). Not an edge.
  • \((b, g)\) shortens none of the three distances (for example, \(a - b - g - h\) still has length 3), so it may be an edge of \(G\).

Answer: A, C, D