# Minimum Spanning Trees

Special thanks to Arin for writing this page!

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.

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.

- 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.Last modified 3yr ago