madeeasy work book

Question

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?

Comments

if u r asking correct ans then option b if false then option a

---

No need to worry which Option is given True or False. You know the right concept and that's all that's necessary. In Work Books, You will find mistakes here and there.

---

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).

Answer 1

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.

Comments

I have a doubt regarding the statements given to us.

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.

Here, I have made 'a' bold because I think the statement is telling us about one single minimum weight edge. And other edges of different weights may or may not be different. So, considering this, statement A is false.

And same goes for B.) which will be true.

This is actually confusing.😅

Answer 2

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.
• 

Comments

• if all edge weight are same then every MST not contain minimum edge weight .

Might wanna edit it. Logically, It is incorrect statement. 

---

Deepakk.

In above graph can i say edge  e is minimum edge weight ??

---

Edge $e$ is a Specific edge with Minimum edge weight.

In the Question itself, He must have 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.

Answer 3

option b is correct

Comments

my ans is also option :(b)

but correct ans is:(a)

---

but correct ans is:(a)

See Option A is True and hence it is the Not the Correct answer since they have asked "which is False" But  If $A$ is the answer given, Then It is a Mistake in Made Easy Work Book. 

---

there are many errors in made easy books

---

there are many errors in made easy books

Yes. And There will always be. There are mistakes in Cormen as well. Just know the right concept and move on.

Answer 4

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,