#Algorithms #MST Self Doubt.

Question

Let G be a connected simple graph with non distinct edge weights. Now, e be the lightest edge in G. So, does this edge e is present in every MST of G?

My take - when all edge weights are same then lightest edge e won't be there.

Answer 1

It may or may not be there depending on the graph.   

In graph A $\rightarrow$ e is forming a cycle so it is not included in at-least one MST.  
but in graph B $\rightarrow$ e is a bridge so it is there in every MST of G

Comments

So In single sentence we can say that the lightest edge "e" doesn't present in the MST implies that edge "e" present in a cycle of graph G and every edge of the cycle has same weight.

---

Yes exactly.

---

Thanks all of you guys! :)

Answer 2

• it is false . if all edge weight are same then it may or may not include  lightest edge.
• it is true for if all edge weight are distinct.