Comment on page

# 25.1 MSTs and Cut Property

Before we dive into the chapter, let's hear a couple words from Professor Hug on MSTs

Let's do a quick warmup!

Spanning Tree Definition

Spanning Tree Usefulness

MSTs vs SPTs

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.

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.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.Last modified 8mo ago