A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree [Spanning tree] whose sum of edge weights is as small as possible.

[…]

(“Minimum Spanning Tree” 2022)

Cycle property

For any cycle \(C\) in the graph, if the weight of an edge \(e\) of \(C\) is larger than any of the individual weights of all other edges of \(C\), then this edge cannot belong to an [minimum spanning tree].

(“Minimum Spanning Tree” 2022)

Cut property

For any cut [Cut (Graph theory)] \(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 [minimum spanning tree] of the graph.

(“Minimum Spanning Tree” 2022)

Minimum-cost edge

If the minimum cost edge e of a graph is unique, then this edge is included in any MST.

(“Minimum Spanning Tree” 2022)

Bibliography

References

“Minimum Spanning Tree.” 2022. In Wikipedia. https://en.wikipedia.org/w/index.php?title=Minimum_spanning_tree&oldid=1128869717.