1. Overview
In this tutorial, we’ll discuss the cut property in a minimum spanning tree.
Furthermore, we’ll present several examples of cut and also discuss the correctness of cut property in a minimum spanning tree.
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 in a connected graph
, partitions the vertex set
into two disjoint subsets
, and
.
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 of a connected graph
can be defined as the set of edges that have one endpoint in
and the other in
. For example the
of
A vertex is a cut vertex if there exists a connected graph
, and removing
from
disconnects that graph.
An edge is a cut edge of a connected graph
if
and
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 where
and
. Now let’s define a cut
in a
:

So here, the cut disconnects the graph
and divides it into two components
and
.
Now let’s discuss the cut vertex. According to the definition, the removal of the cut vertex will disconnect the graph. If we observe the graph , we can see there are two cut vertices:
and
. Let’s verify this. First, we’re removing the vertex
from
:

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
:

Again, when we remove from
, it disconnects the graph and creates two graphs. Hence,
is also a cut vertex in
.
Let’s talk about the cut edge. According to the definition, if we remove a cut edge, it’ll disconnect the graph and results in two or more subgraphs. In , it is easy to see that the edge
is a cut edge. If we remove
from
, it’ll break the graph
into two subgraphs:

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 on
would be
. We can see one endpoint of
belongs to
and the other endpoint is in
.
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 cut 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:

Here we’re taking a connected weighted graph . Also, we’ve defined 4 cuts in a graph
.
So according to the definition, we’ll sum the weights of edges of each cut. Let’s start with . Total edge weight in
sum of weights of
. In this way, the weight of
and
would be
.
Hence, the minimum cut is with a weight of 6 and the maximum cut in
would be
as the sum of edge weight in
is greater than all other cuts in
.
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 a weighted and connected graph. Let’s assume that all edges cost in the MST is 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.
5.2. Example
We’re taking a weighted connected graph here:

In this example, a cut divided the graph into two subgraphs
(green vertices) and
(pink vertices). The cut set for
would be
. Now 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 weather the edge
is present or not:

This is one of the minimum spanning trees of , and as we can see, the edge
is present here. So we can say the cut property works fine for the graph
.
What about other graphs? Will the cut property holds 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 tree, we’re presenting a formal proof in this section.
Let’s assume that we build 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 there exists an edge
joining two sets
,
, and has the smallest weight.
Now we’re starting this proof by assuming the edge is not a part of the MST
. It would be interesting here to see what happens if we include
to the MST
. If we include
in
, it’ll create a cycle. But 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
which has one endpoint in
and another endpoint in
. Now initially, we assumed that
has the smallest weight among all the edges which joins
and
. This implies that the edge
must be of higher weight than
.
Therefore is a spanning tree but not a minimum spanning tree. If we include the edge
and then construct the MST, the total weight of the MST
would be less than the previous one. Also,
can’t contain both
and
as it will create a cycle. Therefore our initial assumption that
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 of that graph.
Let’s simplify the proof with an example:

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

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

The total weight of the minimum spanning tree here is
. Previously we defined that
is the minimum weighted edge in the cut set. It means the weight of the edge
should be greater than the edge
. 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:

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
. Therefore if we include the edge
, then it won’t be a minimum spanning tree.
Hence, we proved that the minimum spanning tree corresponds 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.