Correctness And Termination Of Boruvka's Algorithm

What Correctness Requires

Boruvka’s algorithm repeatedly examines the components of a current forest and chooses an outgoing edge of minimum weight for each component. Its efficiency comes from making several choices in one round. To prove correctness, we need to establish three facts: a component’s choice is safe, the choices in a round do not create a cycle, and every round that is not finished reduces the number of components.

Throughout, \(G=(V,E)\) is a finite, connected, simple, undirected graph with \(n=|V|\ge 1\), and each edge has a real weight \(w(e)\). A spanning tree is a connected, acyclic subgraph containing every vertex. A minimum spanning tree (MST) is a spanning tree of least total edge weight. At least one MST exists: a connected finite graph has a spanning tree, and there are only finitely many spanning trees over which to minimize the weight.

A forest is an acyclic graph, not necessarily connected. The algorithm’s current forest \(F\) starts with vertex set \(V\) and no edges. An edge is safe relative to \(F\) if \(F+e\) is contained in some MST. The key invariant will be that the current forest is contained in an MST.

Why a Component’s Choice Is Safe

The cut associated with a component \(C\) is the partition \((C,V\setminus C)\). Its crossing edges are exactly the edges outgoing from \(C\). We prove the safety fact directly, including the role of the current forest.

Proof. If \(e\in E(T)\), then \(T\) already contains \(F+e\). Otherwise, adding \(e\) to the tree \(T\) creates a cycle: the cycle consists of \(e\) and the unique path in \(T\) between its endpoints. That path starts in \(C\) and ends outside \(C\), so it contains an edge \(f\) crossing the cut \((C,V\setminus C)\). Because \(e\) is a minimum-weight crossing edge, \(w(e)\le w(f)\).

No edge of \(F\) crosses this cut: \(C\) is a component of \(F\), so an edge of \(F\) cannot join \(C\) to another component. In particular, \(f\notin E(F)\). Remove \(f\) from \(T+e\). Removing an edge from that cycle leaves a spanning tree \(T'=T+e-f\), and \(T'\) still contains every edge of \(F\), as well as \(e\). Its weight is \(w(T')=w(T)+w(e)-w(f)\le w(T)\). Since \(T\) is an MST, \(T'\) cannot have smaller weight than \(T\); hence \(T'\) is also an MST. Therefore \(F+e\) is contained in an MST. \(\square\)

The lemma gives safety for one component’s choice. Boruvka adds choices from several components in the same round, so we also need to show that the whole batch can be added without losing the invariant.

Choices in a Round Preserve a Forest

At the start of a round, contract each component of \(F\) to one vertex. The chosen edges then connect these contracted vertices. Regard each component as choosing its selected edge toward the other component at that edge’s endpoint. If both endpoints select the same edge, it is included only once.

Proof. Suppose the selected edges created a cycle among the components of \(F\). On that cycle, every edge must have been selected by at least one of its endpoint components. A cycle with \(k\) edges has \(k\) vertices, and each component selects just one edge. Thus every cycle edge must be selected exactly once by a component on the cycle, and no such component selects an edge outside the cycle. The selections therefore point around the cycle in one direction. At each component, its selected edge is strictly earlier in the tie-breaking order than the other cycle edge leaving that component. Going around the cycle would give a strictly decreasing sequence of edge positions that returns to its starting edge, which is impossible. So there is no cycle among the contracted components. Since \(F\) itself is acyclic, adding edges whose contracted graph is acyclic leaves a forest. \(\square\)

For the invariant, acyclicity alone is not enough: the new forest must still be contained in an MST. Process the distinct selected edges in the fixed order. Suppose the edges before \(e\) in this order have already been added while preserving containment in an MST. Let \(C\) be the component that selected \(e\) at the start of the round. None of the earlier selected edges crosses \((C,V\setminus C)\): any such edge would be an outgoing edge from \(C\) earlier than its selected edge \(e\), contradicting the choice of \(e\). Also, no edge of the starting forest \(F\) crosses this cut.

Take an MST containing \(F\) and all the earlier edges. If it does not contain \(e\), adding \(e\) creates a cycle. The cycle’s path between the endpoints of \(e\) crosses the cut, so it contains some crossing edge \(f\). The preceding paragraph shows that \(f\) is not one of the edges already required in the forest. Since \(e\) has minimum weight across the cut, \(w(e)\le w(f)\). Replacing \(f\) by \(e\) gives a spanning tree of no greater weight, hence another MST, now also containing \(e\). Repeating this argument for each selected edge proves that the entire round’s choices can be added while preserving containment in an MST.

Termination and Correctness

Proof. We maintain the invariant that the current graph \(F\) is a forest contained in some MST. Initially \(F\) has no edges, so it is a forest and is contained in every MST. If a round is performed, the forest-preservation lemma shows that the selected edges keep \(F\) acyclic. The batch-safety argument shows that the enlarged forest remains contained in an MST. Thus the invariant holds after every round.

If \(F\) has more than one component, each component has an outgoing edge. Indeed, if one component had none, no edge of \(G\) would join it to its complement, contradicting the connectedness of \(G\). Every component therefore selects an edge to a different component. Consequently at least two old components merge, and the number of components strictly decreases. It is a positive integer, so this strict decrease can occur only finitely many times. When there is one component, \(F\) is connected as well as acyclic and contains every vertex; it is a spanning tree.

By the invariant, this final tree is contained in an MST. Both are spanning trees on the same vertex set, so containment means they have exactly the same edges. The output is therefore an MST. If \(n=1\), the initial empty-edge forest is already connected on its one vertex and is the spanning tree, so the algorithm terminates immediately. \(\square\)

A Round with Several Simultaneous Merges

Common Pitfall

Do not treat arbitrary tied choices as automatically cycle-free. In the equal-weight triangle, it is possible for the three vertices to choose \(AB\), \(BC\), and \(CA\), respectively. Adding all three produces a cycle, not a forest. The correction is to fix a strict tie-breaking order before making choices and include each selected edge only once. The proof above then ensures that a round preserves acyclicity and that its additions remain contained in an MST. Without a tie rule or another explicit cycle-handling procedure, the forest invariant has not been established.

The connectedness assumption matters as well. If the input graph is disconnected, a component with no outgoing edge may never merge with the others, so there is no spanning tree of the whole graph. Running the same merging process separately within each connected component instead produces a minimum spanning forest.