Minimum Spanning Tree: The Cut Property

1. Overview

In this tutorial, we’ll discuss the cut property for the minimum spanning trees.

Furthermore, we’ll present several examples of cut and discuss the correctness of cut property from the minimum spanning tree perspective.

2. Definition of a Cut

In graph theory, a cut can be defined as a partition that divides a graph into two disjoint subsets.

Let’s define a cut formally. A cut C = (S_1, S_2) in a connected graph G(V, E) , partitions the vertex set into two disjoint subsets S_1 , and S_2 .

In graph theory, there are some terms related to a cut that will occur during this discussion: cut set, cut vertex, and cut edge. Before going further, let’s discuss these definitions here.

A cut set of a cut C(S_1, S_2) of a connected graph G(V, E) can be defined as the set of edges that have one endpoint in S_1 and the other in S_2 . For example the of $G(V, E) = \{(i, j) \in E | j \in S_1, j \in S_2 \}$

Furthermore, a vertex V_c is a cut vertex if a connected graph G(V, E) exists, and removing V_c from disconnects that graph.

Finally, an edge E_c is a cut edge of a connected graph G(V, E) if $E_c \in E$ and G - E_c disconnects the graph.

3. Example

In this section, we’ll see an example of a cut. We’ll also demonstrate how to find a cut set, cut vertex, and cut edge.

First, let’s take a look at a connected graph:

Here, we’ve taken G(V, E) where V=(V1, V2, V3, V4, V5, V6, V7) and E=(E1, E2, E3, E4, E5, E6, E7, E8, E9) . Now let’s define a cut C(S_1, S_2) in a :

Hence, the cut disconnects the graph and divides it into two components, S_1 and S_2 .

Moreover, let’s discuss the cut vertex. According to the definition, the removal of the cut vertex will disconnect the graph. Hence, if we observe the graph $\mathbf{G}$ , we can see there are two cut vertices: $\mathbf{V3}$ and $\mathbf{V4}$ . Let’s verify this. First, we’re removing the vertex from :

v3 remove

We can see the removal of vertex disconnects the graph and breaks it into two graphs. Hence, we verified that is a cut vertex in . Now let’s remove the vertex from :

v4 remove

Again, when we remove from , it disconnects the graph and creates two graphs. Hence, is also a cut vertex in .

Furthermore, let’s talk about the cut edge. According to the definition, if we remove a cut edge, it’ll disconnect the graph and result in two or more subgraphs. In $\mathbf{G}$ , it is easy to see that the edge $\mathbf{E4}$ is a cut edge. If we remove from , it’ll break the graph into two subgraphs:

e4 remove

Next is the cut set. A cut set of a cut is defined as a set of edges whose two endpoints are in two graphs. Here, a cut set of the cut $\mathbf{C(S_1, S_2)}$ on $\mathbf{G}$ would be $\mathbf\{E4\}$ . Thus, we can see one endpoint of belongs to S_1 , and the other endpoint is in S_2 .

4. Variants of a Cut

There are two popular variants of a cut: maximum cut and minimum cut. In this section, we’ll discuss these two variants with an example.

Both minimum and maximum cuts exist in a weighted connected graph. A minimum cut is the minimum sum of weights of the edges whose removal disconnects the graph. Similarly, a maximum cut is the maximum sum of weights of the edges whose removal disconnects the graph.

Let’s find the maximum and minimum cut:

maxmin

Here, we’re taking a connected weighted graph G_1(V_1, E_1) . Additionally, we’ve defined 4 cuts in a graph G_1 .

Furthermore, to calculate the maximum and minimum cuts, we need to calculate the sum of the weights of the edges of each cut. Let’s start with CUT 1 . Total edge weight in CUT 1 = sum of weights of E1, E3, E10 = 2 + 2 + 4 = 8 . In this way, the weight of CUT 2, CUT 3, and CUT 4 would be 10, 6, 7 .

Hence, the minimum cut is $\mathbf{CUT 3}$ with a weight of 6 and the maximum cut in $\mathbf{G_1}$ would be $\mathbf{CUT 2}$ as the sum of edge weight in $\mathbf{CUT 2}$ is greater than all other cuts in $\mathbf{G_1}$ .

5. Cut Property in Minimum Spanning Tree

5.1. Statement

Now we know that a cut splits the vertex set of a graph into two or more sets. A cut set contains a set of edges whose one endpoint is in one graph and the other endpoint is in another graph. When constructing a minimum spanning tree (MST), the original graph should be weighted and connected. Let’s assume that all edges cost in the MST are distinct.

According to the cut property, if there is an edge in the cut set which has the smallest edge weight or cost among all other edges in the cut set, the edge should be included in the minimum spanning tree. Let’s verify this cut property.

5.2. Example

We’re taking a weighted connected graph here:

A weighted connected graph example

In this example, a cut divided the graph into two subgraphs S_1 (blue vertices) and S_2 (pink vertices):

after performing the cut operation

Therefore, the cut set for would be (E2, E3, E5, E6) . Hence, according to the cut property, the minimum weighted edge from the cut set should be present in the minimum spanning tree of . Here, the minimum weighted edge from the cut set is .

Now we’ll construct a minimum spanning tree of and check whether the edge is present or not:

example2-1

This is one of the minimum spanning trees of , and as we can see, the edge is present here. Thus, we can say the cut property works fine for the graph .

What about other graphs? Will the cut property hold for all other minimum spanning trees? Let’s find out in the next section.

5.3. Proof of Cut Property

Now, to conclude that the cut property will work for all the minimum spanning trees, we’re presenting a formal proof in this section.

Let’s assume we construct a minimum spanning tree from a graph . We also defined a cut , which split the vertex set into two sets and . Furthermore, we assume that an edge E_C joins two sets and , and it has the smallest weight.

Moreover, we’re starting this proof by assuming the edge $\mathbf{E_C}$ is not a part of the MST $\mathbf{T}$ . It would be interesting here to see what happens if we include E_C to the MST . If we include E_C in , it’ll create a cycle. However, according to the definition of MST, a cycle can’t be part of MST.

Now, if we analyze the MST , there must be some edge in , let’s name it as , other than E_C , which has one endpoint in and another endpoint in . Initially, we assumed that E_C has the smallest weight among all the edges, which joins the vertices and . This implies that the edge $\mathbf{K}$ must be of higher weight than $\mathbf{E_C}$ .

Therefore, is a spanning tree but not a minimum spanning tree. If we include the edge E_C and then construct the MST, the total weight of the MST would be less than the previous one. Also, can’t contain both E_C and as it will create a cycle. Therefore, our initial assumption that E_C is not a part of the MST should be wrong.

Hence, we can conclude that the minimum weighted edge in the cut set should be part of the minimum spanning tree in that graph.

Let’s simplify the proof with an example:

cut 1

We’re taking a connected weighted graph . Now let’s define a cut of :

cut 2

The cut divided the graph into two subgraphs and . Now, there are two edges that connect and , among which E_C is the minimum weighted edge. First, we’ll construct a minimum spanning tree from without including the edge E_C :

cut 3

The total weight of the minimum spanning tree here is . Previously we defined that E_C is the minimum weighted edge in the cut set. It means the weight of the edge should be greater than the edge E_C . In such a case, the currently constructed spanning tree is not an MST, as we can build a spanning tree which can be less weighted than the current one:

cut 4

As we can see, when we include the edge in the spanning tree, the total weight of the spanning tree would become , which is higher than the weight when we construct by including the edge E_C . Therefore, it won’t be a minimum spanning tree if we include the edge $\mathbf{K}$ .

Hence, we proved that the minimum spanning tree corresponding to a connected weighted graph should include the minimum weighted edge of the cut set.

5.4. Application

Shortest path algorithms like Prim’s algorithm and Kruskal’s algorithm use the cut property to construct a minimum spanning tree.

6. Conclusion

In this tutorial, we’ve discussed cut property in a minimum spanning tree.

We presented the correctness of the cut property and showed that cut property is valid for all minimum spanning trees.

Persistence

REST

Security