Search code examples
algorithmgraphminimum-spanning-tree

minimum weight in the cut of a MST


Let G be an undirected graph with distinct edge weights. Let T be the MST 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.


Solution

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