Minimum Spanning Trees: Kruskal and Prim

Given a weighted, connected, undirected graph — a network of assets connected by correlation strength, or a set of locations connected by connectivity cost — the minimum spanning tree (MST) problem asks for the cheapest possible subset of edges that keeps every vertex connected, with no cycles. This is the connectivity twin of the shortest-path problem: instead of minimizing a single path's cost, minimize a whole connected subgraph's total edge weight. This note proves the two structural facts (the cut property and cycle property) that make greedy MST algorithms provably correct, then derives Kruskal's and Prim's algorithms as two different greedy strategies built on the same guarantee.