edited by
2,802 views
1 votes
1 votes
Q. State whether the following statements are FALSE.

(a). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of at least one minimum spanning tree of the graph.

(b). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of each one minimum spanning tree of the graph.

which one is correct above two option?
edited by

4 Answers

6 votes
6 votes

Statements in the Question must be written like this : 

A.  if $e$ is a specific edge with  minimum edge weight in a connected weighted graph,it must be among the edges of at least one minimum spanning tree of the graph.

B.  if $e$ is a Specific edge with minimum edge weight in a connected weighted graph,it must be among the edges of each one minimum spanning tree of the graph.


Now, Coming to answer :

$A$ is Correct. Think about Kruskal's algorithm. It randomly picks the Edge with minimum weight. So, If there are multiple edges with minimum weights, then it can pick any of them, Hence there will always be some MST for each Minimum weighted edge(i.e. Edge with minimum weight).

$B$ is False. Consider a Triangle(Cycle graph with Three Vertices) with each edge having weight $1$. Of, Course, in Each MST, One edge will definitely be missing. So, It is NOT necessary that a Edge with the minimum weight will be present in Each MST.

edited by
1 votes
1 votes

option a) true 

  • if all edge weight are distinct or same then,it must be among the edges of at least one minimum spanning tree of the graph.
  • look at the example edge weight with e=1 . it is a minimum edge weight ` and it is present in MST 1,2,4. so option a is true
  • if all edge weight are distinct then ,it must be among the edges of each one minimum spanning tree of the graph.then option b is true.
  • if all edge weight are same then every MST not contain minimum edge weight .
  • look at the example edge weight with e=1 . it is a minimum edge weight. but e is not present in MST 3. so option b is wrong.
0 votes
0 votes
option b is correct
0 votes
0 votes

Few Points

  • If e is minimum and unique it will always be in MST. In fact 2nd minimum and unique will also always be in MST. (Remember we exclude minimum only when it from a cycle, 1st and 2nd minimum can never form a cycle.)
  • if e is minimum and not unique still it will be included in some MST. Same for 2nd minimum and non unique. But as its non unique 1st and/or 2nd mayn't be present in all MST. (Take example of triangle with all edge weight 5).

Now coming to the answer.

A. Correct.

B. Incorrect.

Reasons for both are already explained above,

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
Durgesh Singh asked Apr 29, 2018
918 views
Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?
0 votes
0 votes
0 answers
3
iarnav asked Apr 19, 2018
398 views
Some say answer is 2n and someplace else it's been told 2n-1-1. So, what's the corrent one?
0 votes
0 votes
1 answer
4
targate2018 asked Dec 5, 2017
317 views
Are MST and shortest path tree identical?T/F? with reasoning.