##### minimum spanning tree

Let G be an undirected connected graph with distinct edge weights. Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false?

(A) Every minimum spanning tree of G must contain emin
(B) If emax is in a minimum spanning tree, then its removal must be disconnecting G
(C) No minimum spanning tree contains emax
(D) G has a unique minimum spanning tree

Discuss

Saraansh
16 Jun 2017 05:34 pm

Every munimum spanning tree of G must contain emin

Saraansh
16 Jun 2017 05:34 pm

(A) Every minimum spanning tree of G must contain emin

Sumit Verma
16 Jun 2017 05:42 pm

pragya goyal
17 Jun 2017 09:11 am

ans: (C). It is not the case for every graph. It depends on structure of graph. Choice (B) is the reason for Ans to be (C)

Niket Gangwar
17 Jun 2017 07:31 pm

Ans:- (C) as MST will contain the maximum edge only in the condition if that particular edge is linking two different parts of the graph....so if we remove it,the graph will get disconnected...

ANUPAM MONDAL
3 Sep 2017 02:27 pm

c

ALOK GUPTA
10 Jul 2018 11:30 pm
c