GATE CSE 2025 | Set 1 | Question: 8

Question

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$ ?

• A. $d_{1}(u, v)=d_{2}(u, v)$
• B. $d_{1}(u, v) \leq d_{2}(u, v)$
• C. $d_{1}(u, v) \geq d_{2}(u, v)$
• D. $d_{1}(u, v) \neq d_{2}(u, v)$

Comments

Answer = B,,,   https://correctbrain.com/buy/

---

as we know that mst may or may not give shortest path

so shortest  path  =< mst shortest paths

 

---

 

 

An MST includes edges from the original graph; it does not add any new edges(i.e it will take edges from orginal graph using some algo like prims). So how can it give a shorter shortest path than the original graph? If it actually gives a shorter path, then we are not calculating the shortest path correctly in the original graph.

But due to achieving the minimum-cost spanning tree, it may exclude some edges which usually help to get the correct shortest path as in the original graph. So, in that case, it gives a greater value for the shortest path between two vertices in the MST than in the original graph.

Answer 1

Whenever there is only one option correct among the given options, one example is sufficient to identify the answer provided that it will give only one option is correct and remaining all other options were wrong. One such example is given below:

The shortest path between A and B in the graph is 4 whereas in the MST, it is 8. Hence, option B is the only correct.

---

Formal Proof:

T is Minimum Spanning Tree of G $\rightarrow$ all the edges of T must be part of G but not vice-versa. 

As T is MST of G, the vertices u and v of G - should be in T.

$d_1(u,v)$ - shortest distance between u and v in the given graph G

$d_2(u,v)$ - shortest distance between u and v in the T which is MST of the G

As all the edges in T are also avaiable in the G, therefore the shortest path between u and v in T, should also exist in G. 

Therefore either $d_1(u,v) = d_2(u,v)$  or $d_1(u,v) \leq d_2(u,v)$ is the correct.

So, now we need to check whether the shortest path between u and v in T - is the only shortest path between u and v in G or anyother shortest path is also available in G?

In other words, it means "while forming the MST, are we always considering the shortest path of u and v of G to include u and v in the MST" ?

If answer for that question is yes, then  $d_1(u,v) = d_2(u,v)$, otherwise $d_1(u,v) \leq d_2(u,v)$.

 

Consider Prim’s algorithm, where a Minimum Spanning Tree (MST) is constructed by adding vertices one by one.

Assume vertex u and some other vertices are already included in the MST. To add a new vertex v, Prim’s algorithm selects the minimum-weight edge that connects v to any vertex already present in the MST. This selection is based only on the edge weight.

Now, even if there exists a direct edge (u, v) that is part of the shortest path between u and v in the original graph G, Prim’s algorithm may still choose a different edge (x, v) if its weight is smaller than the weight of (u, v).

In such a case, the path between u and v in the MST will be: $ u \rightarrow \cdots \rightarrow x \rightarrow v$ and its length depends on the path from u to x plus the edge (x, v).

If the path u → x is not the shortest way to reach v in the original graph, then the MST will not contain the shortest path between u and v from G.

So, the answer for the question "while forming the MST, are we always considering the shortest path of u and v of G to include u and v in the MST" is NO.

Hence, $d_1(u,v) \leq d_2(u,v)$ where $d_1(u,v)$ - shortest distance between u and v in the given graph G and $d_2(u,v)$ - shortest distance between u and v in the T which is MST of the G.

Comments

But Sir, Taking one example and assuming that it would work for all cases is dangeorus right?

What I was thinking is like: For any two vertices in question it mentioned that it is smallest distance (assuming floyd warshall is used) then demn sure we can say that no other distance is smaller than this. So it should be B in MST's the distance might be greater or equal but it can't be less than the distance we got through some genuine algorithm

---

One example case is sufficient while choosing one out of few options in which take example case is giving only one is correct and remaining all other options are wrong. 

Sometimes, it is easy to find the correct answer instead of formal proof. 

---

Comment on your formal proof: 

Need to show why not option A but only option B is true.

---

If A was the case means shortest path between two vertices can be calculated using MST algo's like prim's or kruskal's there was no need of higher time complexity algo's like flloyd warshall right for computing shortest path between any two vertices right..

---

 shortest path between two vertices can be calculated using MST algo's like prim's or kruskal's there was no need of higher time complexity algo's like flloyd warshall right for computing shortest path between any two vertices

Even if we have merge sort, why we study Quick sort - According to your argument, there is no need of the Quicksort when we already have a better time complexity sorting technique.

---

I have added the formal proof in my answer.

Answer 2

 

Shortest Distance : 

         

d1 (u, v) = 5                                                              

 

MST :                                                                                                                     

d2 (u, v) = 6

 

-> 𝑑1 (𝑢, 𝑣) ≤ 𝑑2(𝑢, 𝑣)

Answer 3

This question can be answered using common sense :)

If the shortest distance between two vertices in the graph is d1, then that is the guaranteed shortest distance, so the shortest distance given in the tree can never be greater than it, so option C is eliminated.

If they were equal in every possible case, then why even use shortest path algorithms? :) We would get an MST which has lesser algorithmic complexity and has the shortest distances for all vertices. The existence of Dijkstra's algorithm indicates that MSTs dont have this property.

But that does not mean they are not equal in some cases, since all trees are also graphs, an MST is also a graph, in which case the graph shortest distance and MST shortest distance is same.

Leaves us only with the conclusion that MST shortest distance is greater than or equal to graph shortest distance.

Option B

 

Comments

Nice use of concepts.

Answer 4

option B  

edges 2,3,5 are selected in spanning tree .  edge weight 4 not select because it form cycle. now Shortest distance in graph G between u and v be 4 . but in minimum spaning T tree it is 5.  

---

Answer 5

We are given:

• $ G $: an undirected graph with positive edge weights.

• $ T $: a minimum spanning tree (MST) of $ G $.

• $ d_1(u, v) $: shortest path distance between $ u $ and $ v $ in the original graph $ G $.

• $ d_2(u, v) $: shortest path distance between $ u $ and $ v $ in the MST $ T $.

We are to find which statement is always true for all possible $ G $, $ T $, and $ u, v $.

 

In a tree, there is exactly one unique path between any two vertices. So in $ T $, $ d_2(u, v) $ is simply the sum of weights along that unique path.In $ G $, $ d_1(u, v) $ is the shortest path  which may use edges not in the MST, possibly yielding a shorter total weight than the path in $ T $.

But here’s the critical point:

The MST minimizes the total weight of the tree, not the shortest path distances between all pairs of vertices.So, it is possible that the unique path in $ T $ between $ u $ and $ v $ has a larger total weight than the shortest path in $ G $, because $ G $ might have a direct or indirect shortcut using non-MST edges.

Example

Consider a triangle graph with vertices $ A, B, C $:

$ AB = 1 $
$ BC = 1 $
$ AC = 1.5 $

The MST will include edges $ AB $ and $ BC $ (total weight 2), excluding $ AC $.

Now compute:

1. $ d_1(A, C) $ in $ G $: $\min( AC = 1.5, , A \to B \to C = 2 ) = 1.5$
2. $ d_2(A, C) $ in $ T $: only path is $ A \to B \to C = 2 $

So, $ d_1(A,C) = 1.5 < 2 = d_2(A,C) $Thus, $ d_1(u,v) < d_2(u,v) $ is possible.

What can we say generally?

Since $ T $ is a subgraph of $ G $, any path in $ T $ is also a path in $ G $. Therefore, the shortest path in $ G $ cannot be longer than the path in $ T $.

That is:

$$
d_1(u, v) \leq d_2(u, v)
$$

Because the path from $ u $ to $ v $ in $ T $ is one possible path in $ G $, and $ d_1(u, v) $ is the minimum over all paths in $ G $. So it must be ≤ the weight of any specific path  including the one in $ T $.

This holds for all $ G $, all MSTs $ T $, and all $ u, v $.

$$\color{lime}
\boxed{\text{B. } d_1(u, v) \leq d_2(u, v)}$$

Answer 6

So, the shortest path of a graph is less than or equal to the shortest path of the MST of a defined vertices.