GATE DA 2025 — Question 58

Programming, Data Structures and Algorithmsintroduction to graph theoryMSQ2 marksMedium

Let \(G\) be a simple, unweighted, and undirected graph. A subset of the vertices and edges of \(G\) are shown below.
Question image
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. A
    \((b, d)\)
  2. B
    \((b, g)\)
  3. C
    \((b, h)\)
  4. D
    \((e, g)\)
Practise the full 2025 paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on introduction to graph theoryTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group