The GATE Grind

GATE 2017 CS – Question 36

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

Let $G = (V, E)$ be *any* connected undirected edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements:

(I) Minimum Spanning Tree of $G$ is always unique.

(II) Shortest path between any two vertices of $G$ is always unique.

Which of the above statements is/are necessarily true?

  1. (I) only
  2. (II) only
  3. both (I) and (II)
  4. neither (I) nor (II)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) (I) only

Explanation

When all edge weights are distinct, the minimum spanning tree is unique, so (I) is true. Distinct edge weights do not stop two different paths from having the same total weight, for example 1 + 4 and 2 + 3, so the shortest path need not be unique and (II) is false.