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.
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
cycle
bridge
64.3k questions
77.9k answers
244k comments
80.0k users