minimum weight in the cut of a MST

Let G be an undirected graph with distinct edge weights. Let T be the M开发者_如何学PythonST in G. Let (u, v) be any edge in T. Show that there is a cut (S; V-S) such that (u; v) is the minimum weight edge in this cut.

I'll give it a shoot, let's consider a cut such that e = (u, v) is the only of its edges belonging to T. Suppose there's another edge e' in the cut with w(e') < w(e), then we could form another ST including e' and dropping e, which would have smaller weight, absurd.

we start with |V| cuts. We merge two cuts in every loop. Finally we end up with 1 cut. The MST is a subset of the edges in this cut. Thus for every merge, we have chosen (one of)the light edge (u,v) for that cut. Finally, we have |V|-1 edges. Conversely, for every edge in the tree, there's a cut which was "bridged". So, if an edge (u,v) is in MST, there's a cut (S,V-S) corresponding to which it was the light edge.