Question

Let (u, v) be a minimum-weight edge in a connected graph G. Show that (u, v) belongs to some minimum spanning tree of G.

Answer 1

Mininum spanning tree (MST) of a given connected graph G is the path which contain all vertices of G without any cycles with the such that the sum of weights of edges chosen in the MST is minimum.

Assume e1=(u,v) is a minimum weighted edge of G.

So there cannot be any other acylic path from u to v such that the sum of edge weights in the chosen path is less than edge weight of e1.

But,it is possible to have other edges e2(u2,v2),e3(u3,v3) etc with the same egde weight as e1.Only one of them from them must be considered in the MST to avoid the cycle and reduce the sum of edge weights.

If e2 is considered in MST,e1 is considered in some other MST.But e1 must be included in the some other MST.

Hence proved.