Justify greedy selection by exchange

Try

A weighted connected graph models possible links between sites. A spanning tree connects every site without a redundant cycle; a minimum spanning tree minimizes total weight. Choosing cheap edges without creating a cycle is Kruskal’s algorithm. Its success is not explained by the word greedy: many locally cheapest or locally best procedures fail. An exchange property is the reason this particular selection rule is valid.

Predict

Predict the role of a cut. A cut divides the vertices into two nonempty sets. Every spanning tree must cross it. If the current chosen forest has no edge crossing that cut, adding a lightest crossing edge can be justified by exchanging it into an optimal tree. If the cut already splits a chosen edge, that exchange might delete required work, so the condition that the cut respects the forest matters.

Experiment

Run Kruskal on a four-cycle with edge weights 1, 2, 3, 4 and a diagonal of weight 5.

Candidate weight	Decision	Reason
1	Accept	Joins components
2	Accept	Joins components
3	Accept	Completes a tree
4	Reject	Would close the cycle
5	Reject	Already connected

The total is six. Give a cut certificate for each accepted edge at the moment it is chosen, rather than only checking the final sum.

Understand

Maintain the invariant that some minimum spanning tree contains the current forest F. Let e be a lightest edge crossing a cut respected by F. If a compatible optimal tree T already contains e, nothing changes. Otherwise adding e creates one cycle. That cycle contains another edge f crossing the same cut; f is not in F and has weight at least that of e. Replacing f by e yields a spanning tree containing F and e, with no larger weight, so it is also optimal. Kruskal chooses such a cut by taking one current component. The invariant starts with the empty forest and proves optimality when a spanning tree is reached.

Why distinct weights force one optimum

Assume a finite connected undirected graph, with distinct real edge weights. There are finitely many spanning trees and at least one, so a minimum exists. Suppose two different minimum trees T and U exist. Their symmetric difference consists of edges in exactly one of the two trees. Choose its lightest edge e and rename the trees if needed so that e belongs to T but not U.

Remove e from T. A tree loses connectivity into exactly two components when one edge is removed; let these components define a cut. The unique path in U between the endpoints of e must cross this cut. Choose a crossing edge f on that path. It cannot belong to T: the only T-edge crossing the cut was e, which is absent from U. Thus f also belongs to the symmetric difference. By the lightest choice and distinct weights, f is strictly heavier than e.

Adding e to U creates one cycle, formed by e and that unique path. Removing f from this cycle reconnects all vertices without a cycle, yielding a spanning tree with weight weight(U)+weight(e)−weight(f), strictly less than weight(U). This contradicts minimality. The proof uses two different trees deliberately: the cut comes from T, while the cycle and improving replacement come from U.

Before reading the answer, locate the failed step if weights may tie. Does a tied pair necessarily create multiple optima?

Check the strict inequality and the converse

With ties, the replacement may have equal weight rather than smaller weight, so there is no contradiction. A triangle with all weights 1 has three optimal trees, each of total weight 2. But a triangle with weights 1,1,2 has just one optimal tree: use both weight-1 edges, for total 2; either alternative totals 3. Thus distinct weights are sufficient for uniqueness, not necessary. In a one-vertex connected graph the empty tree is already unique. A disconnected graph has no spanning tree over all its vertices; the forest version is a separate statement.

Apply

A matroid is a finite ground set with independent subsets satisfying heredity and exchange: if I, J are independent and size (I)< size (J), some element of J outside I extends I independently. Forests form the graphic matroid. If every edge of J lay within an I-component, the forest edge bound inside each component would force size (J)≤size (I); hence a crossing edge exists and can be added. The general matroid greedy theorem uses repeated exchanges between a greedy basis and an optimal basis, preserving earlier choices. The full cut-exchange proof above establishes the graphic case used here. The preserved-prefix extension lesson and weighted greedy proof now supply the finite arbitrary-matroid argument, including signed objectives and a non-graphic example. This is the structural reason local weight decisions can be globally repaired.

Continue

For disconnected graphs the same algorithm finds a minimum spanning forest, not a nonexistent spanning tree. With tied weights several optimal trees may exist; deterministic tie-breaking selects one but does not prove uniqueness. Implementations commonly use a disjoint-set structure to test whether endpoints already lie in one component. Its data-structure complexity is separate from the mathematical exchange proof. To diagnose a failed greedy method elsewhere, test heredity and the exchange axiom rather than assuming every collection of feasible partial solutions behaves like forests.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with distinguish edge traversal from vertex cycles.