Why Prim's Algorithm Is Correct

The Correctness Question

Prim’s algorithm grows one tree from a chosen starting vertex. At each step it adds a cheapest edge from the vertices already reached to a vertex not yet reached. The choices can look local, but the key to correctness is that they preserve a global possibility: after each choice, some minimum spanning tree still contains all the edges chosen so far.

Assume throughout that \(G=(V,E)\) is a finite, connected, undirected simple graph with at least one vertex, and that each edge \(e\in E\) has a real weight \(w(e)\). Weights may be equal or negative. A spanning tree is a connected, acyclic subgraph containing every vertex. A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Since the graph is finite and connected, it has at least one spanning tree, and there are finitely many spanning trees, so an MST exists.

Prim starts with a vertex \(r\) and the empty edge set \(F\). It maintains the set \(S\) of vertices reached by the current tree. While \(S\ne V\), it chooses an edge of minimum weight among those with one endpoint in \(S\) and one in \(V\setminus S\), adds that edge to \(F\), and adds its outside endpoint to \(S\). If several crossing edges have minimum weight, any of them may be chosen.

The Cut Property That Prim Uses

For a nonempty proper subset \(S\subset V\), the edges with one endpoint in \(S\) and the other in \(V\setminus S\) are the edges crossing the cut \((S,V\setminus S)\). The graph’s connectedness guarantees that at least one edge crosses every such cut. The following form of the cut property includes the condition needed when some edges have already been selected.

Proof. Choose a minimum spanning tree \(T\) containing \(F\), which exists by the hypothesis on \(F\). If \(e\in E(T)\), then \(T\) already contains \(F\cup\{e\}\), so \(e\) is safe. Otherwise, adding \(e\) to \(T\) creates a cycle: in \(T\) there is a path between the endpoints of \(e\), and that path together with \(e\) is a cycle. The path must contain another edge \(f\) crossing the cut, because its endpoints lie on opposite sides. Since \(e\) is a minimum-weight crossing edge, \(w(e)\le w(f)\). Also, \(f\notin F\), because no edge of \(F\) crosses this cut. Removing \(f\) from the cycle leaves a spanning tree \(T'=T+e-f\) that still contains \(F\cup\{e\}\). Its weight satisfies \(w(T')=w(T)+w(e)-w(f)\le w(T)\). Because \(T\) is minimum, \(T'\) cannot have smaller weight than \(T\); hence \(T'\) is also minimum. Therefore \(e\) is safe for \(F\). \(\square\)

The lemma is an exchange argument: if a cheapest crossing edge is missing from a minimum spanning tree, it can replace another edge on a cycle without increasing the tree’s weight. Ties cause no problem. When \(w(e)=w(f)\), the exchange produces a different MST of the same weight.

Why Every Choice Prim Makes Is Safe

At any step of Prim’s algorithm, every edge already selected has both endpoints in \(S\). This holds initially, when there are no selected edges. It remains true after an iteration because the newly selected edge joins a vertex in \(S\) to the vertex that is added to \(S\); after the addition, both endpoints belong to the enlarged set. Thus no selected edge crosses the current cut.

Proof. We use induction on the number of edges selected. Before any step, \(F=\varnothing\), and every MST contains \(F\). Suppose that at the start of a step some MST contains the current set \(F\). Since \(S\ne V\), the cut \((S,V\setminus S)\) is nontrivial. Connectedness ensures that there is a crossing edge, so Prim can choose a minimum-weight crossing edge \(e\). As shown above, no edge of \(F\) crosses this cut. The cut-property lemma therefore says that \(e\) is safe for \(F\), meaning that some MST contains \(F\cup\{e\}\). This proves the induction step and the claim. \(\square\)

This argument does not require the lightest edge to be unique. The induction only needs the chosen edge to have minimum weight among the crossing edges; any tied minimum satisfies the lemma. It also does not require nonnegative weights, since the exchange argument compares weights by \(w(e)\le w(f)\), without assuming either weight is positive.

Why the Algorithm Terminates with an MST

Proof. Each iteration adds exactly one new vertex to \(S\), so after at most \(|V|-1\) iterations, \(S=V\). Before \(S=V\), connectedness ensures there is a crossing edge, so the algorithm does not get stuck early. Each added edge joins a new vertex to the current tree. It therefore preserves connectedness on the reached vertices and cannot create a cycle: a cycle using the new edge would require a previous path to its outside endpoint, but that endpoint was not yet reached. At termination, the selected edges form a connected, acyclic subgraph containing every vertex, hence a spanning tree. There are \(|V|-1\) additions, one for each vertex other than the starting vertex. By the preceding theorem, some MST contains all selected edges. The selected spanning tree and that MST both have \(|V|-1\) edges; since the selected tree is already a spanning tree contained in the MST, they are the same tree. Thus Prim’s output is an MST. If \(|V|=1\), the algorithm makes no additions and returns the one-vertex tree with weight \(0\), which is minimum. \(\square\)

Worked Traces

A Common Pitfall: Forgetting the Cut

The rule is not “choose the cheapest edge incident to any vertex already reached.” The edge must cross from \(S\) to \(V\setminus S\). For example, let \(V=\{a,b,c,d\}\), \(E=\{ab,ac,bc,bd,cd\}\), and weights \(w(ab)=1\), \(w(ac)=2\), \(w(bc)=3\), \(w(bd)=5\), \(w(cd)=4\). Starting at \(a\), Prim first selects \(ab\), so \(S=\{a,b\}\). After selecting \(ac\), the reached set would be \(\{a,b,c\}\). The edge \(bc\), of weight \(3\), is then incident to reached vertices, but it has both endpoints in \(S\). Adding it would create the cycle \(a-b-c-a\) and would not reach a new vertex. The actual crossing edges are \(bd\), of weight \(5\), and \(cd\), of weight \(4\); Prim must choose \(cd\). The cut condition is what both prevents cycles and makes the cut-property proof apply.

Prim’s central invariant is therefore precise: the selected edges form a tree on the reached vertices, and some MST contains those edges. The cut property justifies each extension of that invariant; once all vertices have been reached, the resulting tree is itself a minimum spanning tree.