Minimum Spanning Tree

Last updated Nov 8, 2022 Edit Source

A minimum-weight spanning tree in a weighted graph

Spanning tree: connected, acyclic subgraph containing all the vertices of a graph

Minimum Spanning Tree Property Let T be a spanning tree of G, where $G=(V,E,W)$ is a connected weighted graph

For every edge (u,v) of G that is not in T

• if (u,v) is added to T, it creates a cycle such that (u,v) is a maximum-weight edge on that cycle
• then T has the MST Property

Tree is an MST if it has the MST property: Tree with MST property is an MST:

For any cut C of the graph, if the weight of an edge e in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.

Proof: Assume that there is an MST T that does not contain e. Adding e to T will produce a cycle, that crosses the cut once at e and crosses back at another edge e’ . Deleting e’ we get a spanning tree $T∖{e’}∪{e}$ of strictly smaller weight than T. This contradicts the assumption that T was a MST.

By a similar argument, if more than one edge is of minimum weight across a cut, then each such edge is contained in some minimum spanning tree.

Misinterpretation of the cut property:

Answer is No. For any node u in $M_2$ there can be some other path P that connects u to v in $M_2$ which passes through the cut multiple times (enters $M_1$). This path can have edge weights smaller than the path $P’$ that connects u to v through $M_2$