# 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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://cs61b-2.gitbook.io/cs61b-textbook/25.-minimum-spanning-trees/25.1-msts-and-cut-property.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.