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

Answer

Discuss

7Comments
Saraansh @saraanshmahor
16 Jun 2017 05:34 pm

Every munimum spanning tree of G must contain emin

Saraansh @saraanshmahor
16 Jun 2017 05:34 pm

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

Sumit Verma @sumitverma
16 Jun 2017 05:42 pm

False statement is asked. Please try again :) 

pragya goyal @pragya
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 @niket151194
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 @anupam
3 Sep 2017 02:27 pm

c

 

ALOK GUPTA @galok1001
10 Jul 2018 11:30 pm
c

Pages