# Minimum Spanning Trees

## Spanning Tree Definition

A **spanning tree** T is a subgraph of a graph G where T:

* Is connected (there's a path to every vertex)
* Is acyclic (no cycles)
* Includes every vertex (spanning property)

**Notice:** the first two properties defines a tree structure, and the last property makes the tree spanning.

A **minimum spanning tree** is a spanning tree with minimum total edge weight.

Example: I want to connect an entire town with wiring and would like to find the optimal wiring connection that connects everyone but uses the least wire.

## MST vs. Shortest Path Tree

In contrast to a shortest path tree, which is essentially the solution tree to running Dijkstra’s with root node = source vertex, a MST has no source. However, it is possible for the MST to be the same as the SPT.

We can think of the MST as a global property for the entire graph, as opposed to SPT which depends on which node is the source node.

If the edges of the graph are not unique, there’s a chance that the MST is not unique.

## Cuts Property

* A **cut** is defined as assigning the nodes in a graph into two sets. 
* A **crossing edge** is an edge that connects two nodes that are in different sets
* The smallest crossing edge is the crossing edge with smallest weight

The **Cut Property** states that the smallest crossing edge is always going to be in the MST, no matter how the cut is made.

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79zpM9iWpZnGXBsP9S%2F-M7A-J_nm94206XUZnKD%2Fimage.png?alt=media\&token=f8b208be-adfb-46b3-a171-5e6b46e5e9e0)