Minimum Spanning Trees: Kruskal, Prim & Cut Properties

For a connected, undirected weighted graph G = (V, E, w):

A Spanning Tree is an acyclic subgraph connecting all |V| vertices, having exactly |V| - 1 edges. An MST minimizes w(T) = sum_{e in T} w(e).

Theorem 1 (The Cut Property):

Let (S, V setminus S) be any cut of G. If edge e = (u, v) is the strictly minimum-weight edge crossing the cut (u in S, v in V setminus S), then e belongs to every MST of G.

Proof: Suppose an MST T does not contain e. Adding e to T creates a cycle C. This cycle must cross the cut at least once more via another edge e'. Since w(e) < w(e'), replacing e' with e creates a new spanning tree T' = T cup {e} setminus {e'} with w(T') < w(T), contradicting the optimality of T.

Theorem 2 (The Cycle Property):

Let C be any cycle in G. If edge e is the strictly heaviest edge on C, then e cannot belong to any MST of G.

Kruskal's Algorithm (Edge-Centric):

1. Sort all edges in non-decreasing order of weight.

2. Maintain a Disjoint Set Union (DSU) of vertices.

3. For each edge (u, v): if Find(u) != Find(v), union the sets and add (u, v) to the MST.

Union-by-rank with path compression achieves O(alpha(V)) amortized time per operation. Total time: O(E log E) = O(E log V).

Prim's Algorithm (Vertex-Centric):

1. Start with an arbitrary root vertex s. Set key[s] = 0, key[v] = inf for all v != s.

2. Extract min vertex u from priority queue.

3. For each adjacent edge (u, v): if v is in the queue and w(u, v) < key[v], update key[v] = w(u, v) and parent[v] = u (Decrease-Key).

Complexity with Binary Min-Heap: O(V log V + E log V) = O(E log V).