Minimum Spanning Tree: What exactly is the Cut Property?

Question

I've been spending a lot of time reading online presentations and textbooks about the cut property of a minimum spanning tree. I don't really get what it's suppose to illustrate or even why it's practical. Supposedly it helps determine what edges to add to a MST, but I fail to see how it accomplishes that. My understanding of the cut property so far is that you split a MST into two arbitrary subsets. Any help here? Thanks!

Solution 1

A cut of a connected graph is a minimal set of edges whose removal separate the graph into two components (pieces). The minimal cut property says that if one of the edges of the cut has weight smaller than any other edge in the cut then it is in the MST. To see this, assume that there is an MST not containing the edge. If we add the edge to the MST we get a cycle that crosses the cut at least twice, so we can break the cycle by removing the other edge from the MST, thereby making a new tree with smaller weight, thereby contradicting the minimality of the MST.

Solution 2

There's another property up on which this explanation is based.

"For any of the cut, if there are even number of edges crossing the cut then there must be a cycle crossing the cut"

Because MST does not contain any cycle there won't be any even number of edges crossing the cut.

Proof by contradiction: Assume that there's a MST not containing edge with min weight "e". If we add the edge "e" to the MST we get a cycle crossing the cut at least twice. We can remove other edge with more weight and break the cycle which results in an ST containing lesser weighing edge "e". This is in contradiction with the assumption.

Comments

[Alexander Falk]

8 years later on this answer and I'm still lost with this. Can you please explain this to me as I was a child?

[deinst]

@AlexanderFalk Where in the explanation are you having trouble?

[user2994783]

Sorry, I have two question: (1) Why the 'cut' would cross the newly added edge twice? (2) If the weight of the newly added edge is smaller than the weight of 'other' edge to be removed, then it would still be a MST, why there is a contradiction?

[Ankit Roy]

@user2994783: (1) One of the edges of the MST must already be in ( = "cross") the cut, because otherwise there would be no way to get from vertices on one side of the cut to vertices on the other side, and in an MST you can get from any vertex to any other vertex; after adding the new smaller edge, there are now 2 edges in ( = "crossing") the cut. (2) The contradiction is that it could not have been an MST in the first place, since we just reduced its weight.

[Foobar]

Does a MST not contain every edge in the cut?

[Neel Sandell]

@Roymunson Assume that we break the graph into two sets with our cut P and Q. Visualize two circles labeled P and Q, and between those two circles you have 4 lines for example representing our cut set. Imagine if two of those lines were included in the minimum spanning tree. Then we could go from P to Q and back to P which makes a cycle. By definition of a tree (which is acyclic), this is not allowed. This means that the edges in the cut set are mutually exclusive. This means we should choose the smallest one (which we can prove by contradiction).