> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-2025/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-2025/25.-minimum-spanning-trees/25.1-msts-and-cut-property.md). # 25.1 MSTs and Cut Property Before we dive into the chapter, let's hear a couple words from Professor Hug on MSTs {% embed url="" %} Let's do a quick warmup! {% endembed %} {% embed url="" %} Spanning Tree Definition {% endembed %} {% embed url="" %} Spanning Tree Usefulness {% endembed %} {% embed url="" %} MSTs vs SPTs {% endembed %} ## Minimum Spanning Trees \ A minimum spanning tree (MST) is the lightest set of edges in a graph possible such that all the vertices are connected. Because it is a tree, it must be connected and acyclic. And it is called "spanning" since all vertices are included. In this chapter, we will look at two algorithms that will help us find a MST from a graph. Before we do that, let's introduce ourselves to the Cut Property, which is a tool that is useful for finding MSTs. ### Cut Property \ We can define a **cut** as an assignment of a graph’s nodes to two non-empty sets (i.e. we assign every node to either set number one or set number two). We can define a **crossing edge** as an edge which connects a node from one set to a node from the other set. With these two definitions, we can understand the **Cut Property**; given any cut, the minimum weight crossing edge is in the MST. ![](https://joshhug.gitbooks.io/hug61b/content/assets/Screen%20Shot%202019-04-14%20at%208.57.22%20PM.png) The proof for the cut property is as follows: Suppose (for the sake of contradiction) that the minimum crossing edge *e* were not in the MST. Since it is not a part of the MST, if we add that edge, a cycle will be created. Because there is a cycle, this implies that some other edge f must also be a crossing edge (for a cycle, if *e* crosses from one set to another, there must be another edge that crosses back over to the first set). Thus, we can remove *f* and keep *e*, and this will give us a lower weight spanning tree. But this is a contradiction because we supposedly started with a MST, but now we have a collection of edges which is a spanning tree but that weighs less, thus the original MST was not actually minimal. As a result, the cut property must hold.