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?

This question was previously asked in

GATE CS 2017 Official Paper: Shift 1

Option 1 : I only

SEBI Grade A 2020: Full Mock Test

7394

100 Questions
100 Marks
60 Mins

**Concept:**

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

**Example:**

Graph G(V, E)

G(V, V – 1) → minimum spanning tree

If edge weights are distinct then there exist unique MST.

Hence Statement I is correct.

When edge weights are distinct and positive in that case shortest path between any two vertices of the graph is not always unique. Shortest path can be different even if the edge weights are unique.

**Example:**

Distance between A → C (3) and A → B → C (1 + 2 = 3), both paths has same distance.

Hence statement II is incorrect.