Let G be a simple, unweighted, and undirected graph. A subset of the vertices…

GATE · 2025 · DA · Data Science & AI

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

Undirected graph shown with vertices a,b,c,d across the top and e,f,g,h across the bottom. Shown edges are a-b, b-c, c-d, e-f, f-g, g-h, a-f, f-c, and c-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. A.

    (b, d)

  2. B.

    (b, g)

  3. C.

    (b, h)

  4. D.

    (e, g)

Attempted by 12 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…