Proof about min spanning tree property

[ciphone]

Homework Statement

(a) If e is part of some MST of G, then it must be a lightest edge in some cutset of G.

Homework Equations

Cut property

The Attempt at a Solution

When the cutset has just one edge then yes it's true obviously. I am think I can do this by contradiction. Assuming e_i is part of some MST of G and e_i is not the lightest edge in any cutset. If this is true then, in every cutset, there exists an edge e_k such that e_k>e_i. I don't know how to go from here

The cut property says For any cut C of the graph, if the weight of an edge in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.

It doesn't say anything about the larger edges in the cut

 

[andrewkirk]

It's a bit hard to give help on this without giving the whole thing away. Still, I'll try.

Since the problem says 'for some cutset in G', it seems likely that there are some (possibly many, possibly even most) cutsets containing e in which e is not the lightest edge. So we might like to look for special cutsets (in which e does have the desired property), which is the same as looking for special partitions of the vertices. The other piece of info we have is that e is in a minimal spanning tree (MST), call that T.

So, in the interests of finding a special partition of the vertices, using the info given, can you think of a partition of the vertices that is uniquely defined as a function of only G, T and e, without requiring any additional choices (which would necessarily be arbitrary)?

 

[Mark44]

OP has been banned for having multiple accounts, so the thread is now closed.