GATE CS 2017 Set 1 Q26 — Graph Traversals (BFS, DFS)

Let's analyze each statement individually:

Statement I: Minimum Spanning Tree of $G$ is always unique.

This statement is TRUE.

A fundamental theorem in graph theory states that if all edge weights in a connected, undirected graph are distinct, then the graph has a unique Minimum Spanning Tree (MST).

Proof sketch: Suppose there are two different MSTs, $T_1$ and $T_2$. Let $e$ be the minimum-weight edge that belongs to one of the trees but not both (say $e \in T_1$ and $e \notin T_2$). Adding $e$ to $T_2$ creates a unique cycle. Since all edge weights are distinct, there is a unique maximum-weight edge on this cycle, which must be strictly heavier than $e$. Replacing that heavier edge with $e$ would yield a spanning tree with a strictly smaller weight than $T_2$, which contradicts the assumption that $T_2$ is an MST. Thus, the MST must be unique.

Statement II: Shortest path between any two vertices of $G$ is always unique.

This statement is FALSE.

Even if all individual edge weights are positive and distinct, the sum of weights along different paths can still be equal. We can easily construct a simple counterexample:

• Consider a graph with 3 vertices: $A$, $B$, and $C$.
• Let the edges and their weights be:
  • $w(A, B) = 3$
  • $w(B, C) = 1$
  • $w(A, C) = 4$
• All edge weights $\{1, 3, 4\}$ are positive and distinct.
• Now, consider the shortest path between $A$ and $C$:
  • Path 1: Direct edge $A \to C$ with total weight $= 4$.
  • Path 2: Path $A \to B \to C$ with total weight $= 3 + 1 = 4$.

Since both paths have the same minimum cost of $4$, the shortest path between $A$ and $C$ is not unique.

Therefore, only Statement I is necessarily true.