Let G be any connected, weighted, undirected graph.

I. G has a unique minimum spanning tree, if no two edges of G have the same weight.

II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

Which of the above two statements is/are TRUE?This question was previously asked in

GATE CS 2019 Official Paper

- I only
- II only
- Both I and II
- Neither I nor II

Option 3 : Both I and II

Free

NIC Scientist B 2020: Full Mock Test

2694

120 Questions
120 Marks
180 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 option 1 is correct

**Theorem:**

If for every cut of a graph there is a unique light edge crossing the cut then the graph has a unique minimum spanning tree, but converse may not be true.

India’s **#1 Learning** Platform

Start Complete Exam Preparation

Daily Live MasterClasses

Practice Question Bank

Mock Tests & Quizzes

Trusted by 2,16,66,170+ Students

Start your FREE coaching now >>

Testbook Edu Solutions Pvt. Ltd.

1st & 2nd Floor, Zion Building,

Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

[email protected]
Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

Toll Free:1800 833 0800

Office Hours: 10 AM to 7 PM (all 7 days)