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!

Mudguard

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

Pidgin

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? – Reiss

@AlexanderFalk Where in the explanation are you having trouble? – Pidgin

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? – Hourihan

@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. – Mure

Does a MST not contain every edge in the cut? – Casteel

@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). – Paleobotany

Answer 2

I'd like to share what I understand about Cut Property to help. If there're anything to improve in my post, please comment below so I can modify my answer.

Background:

For simplification, suppose there are 2 separate MSTs (T1 and T2) formed in a graph G(V, E). There are edges not yet connected between T1 and T2.

Goal:

We want to show that when T1 and T2 are connected, a newly produced tree is also an MST - an optimal solution.

>> My Understanding of Cut Property:

Among the edges not yet connected between T1 and T2, pick the lightest edge. Adding it to connect T1 and T2 makes a new MST - an optimal solution.

Note: Connecting an edge in the same tree introduces a cycle. But a tree shouldn't contain a cycle

Sherborn

Answer 3

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.

Sinapism

Answer 4

At the intuitive level, the cut property aims to tell you that if there is indeed 2 Sets S and S', then what connects the two sets is the edge that weighs the least.

If we want to make a simple example, then say there are two edges one with weight 2 and another weight 1. Both edges connect S and S'. I can choose the edge that have edge weight 2 to connect S and S' and create a Spanning Tree. If I do that however, the resulting Spanning Tree is not Minimum because there is the edge weight of 1 that can be used to lower the cost of connecting them instead of using edge weight of 2.

When the edge with the least weight is used to connect S and S', the end result is a Minimum Spanning Tree because we kept the Minimum property in place.

Roomer