• Support PF! Buy your school textbooks, materials and every day products Here!

Proof about min spanning tree property

  • Thread starter ciphone
  • Start date
  • #1
3
0

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
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,792
1,390
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)?
 
Last edited:
  • #3
33,270
4,975
OP has been banned for having multiple accounts, so the thread is now closed.
 

Related Threads on Proof about min spanning tree property

  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
4
Views
7K
Replies
1
Views
6K
  • Last Post
Replies
4
Views
4K
Replies
11
Views
882
Replies
12
Views
1K
Replies
6
Views
685
Replies
3
Views
1K
Replies
9
Views
1K
  • Last Post
Replies
3
Views
2K
Top