GATE CS 2025 (Forenoon) — Question 18

AlgorithmsMinimum Spanning Trees (Prim/Kruskal Algorithms)MCQ1 mark · −1/3 if wrongMedium

Let \( G \) be any undirected graph with positive edge weights, and \( T \) be a minimum spanning tree of \( G \). For any two vertices, \( u \) and \( v \), let \( d_1(u, v) \) and \( d_2(u, v) \) be the shortest distances between \( u \) and \( v \) in \( G \) and \( T \), respectively. Which ONE of the options is CORRECT for all possible \( G \), \( T \), \( u \) and \( v \)?
  1. A
    \( d_1(u, v) = d_2(u, v) \)
  2. B
    \( d_1(u, v) \le d_2(u, v) \)
  3. C
    \( d_1(u, v) \ge d_2(u, v) \)
  4. D
    \( d_1(u, v) \neq d_2(u, v) \)
Practise the full 2025-FN 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 Minimum Spanning Trees (Prim/Kruskal Algorithms)Timed, 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