Let \(G\) be any undirected graph with positive edge weights, and \(𝑇\) be a…

GATE · 2025 · CS · Set 1 · Computer Science & IT

Let GG be any undirected graph with positive edge weights, and 𝑇𝑇 be a minimum spanning tree of GG. For any two vertices, 𝑢𝑢 and 𝑣𝑣, let 𝑑1(𝑢,𝑣)𝑑_1(𝑢, 𝑣) and 𝑑2(𝑢,𝑣)𝑑_2(𝑢, 𝑣) be the shortest distances between uu and 𝑣𝑣 in GG and 𝑇, respectively. Which ONE of the options is CORRECT for all possible 𝐺,𝑇,𝑢𝐺, 𝑇, 𝑢 and 𝑣𝑣?

  1. A.

    d1(u,v)=d2(u,v)d_1(u, v) = d_2(u, v)

  2. B.

    d1(u,v)≤d2(u,v)d_1(u, v) \leq d_2(u, v)

  3. C.

    d1(u,v)≥d2(u,v)d_1(u, v) \geq d_2(u, v)

  4. D.

    d1(u,v)≠d2(u,v)d_1(u, v) \neq d_2(u, v)

Attempted by 194 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…