GATE CS 2025 Set 1 Q8 — Minimum Spanning Trees

To find the correct relationship between $d_1(u, v)$ and $d_2(u, v)$, let us analyze the properties of the graph $G$ and its minimum spanning tree $T$:

1. Subgraph Relationship: By definition, a spanning tree $T$ is a subgraph of $G$ ($T \subseteq G$). This means every edge present in $T$ is also present in $G$, and any path between two vertices in $T$ is also a valid path in $G$.
2. Shortest Path Definition:
   • $d_2(u, v)$ is the length of the unique path between $u$ and $v$ in $T$.
   • $d_1(u, v)$ is the length of the shortest path between $u$ and $v$ in $G$, which is computed by taking the minimum weight over all possible paths between $u$ and $v$ in $G$.

Since the path in $T$ is just one of the many possible paths available in $G$, the shortest path in $G$ can never be longer than the path in $T$. Therefore, we must have:

Counterexample for other options:

Consider a triangle graph $G$ with vertices $A, B, C$ and edge weights:

• $w(A, B) = 1$
• $w(B, C) = 1$
• $w(A, C) = 1.5$

The minimum spanning tree $T$ consists of the edges $(A, B)$ and $(B, C)$ with a total weight of $2$.

• For $u = A$ and $v = C$:
  • In $G$, the shortest path is the direct edge $AC$, so $d_1(A, C) = 1.5$.
  • In $T$, the unique path is $A \to B \to C$, so $d_2(A, C) = 1 + 1 = 2$.
  • Here, $d_1(A, C) < d_2(A, C)$, which disproves options A and C.
• For $u = A$ and $v = B$:
  • In $G$, $d_1(A, B) = 1$.
  • In $T$, $d_2(A, B) = 1$.
  • Here, $d_1(A, B) = d_2(A, B)$, which disproves option D.

Thus, only option B is correct for all possible graphs and vertices.