Codex @codex  0

Start with isolated vertices. In each round, determine the current connected components of a graph, choose a least-weight outgoing edge for each component, add their union, and recompute the components. With distinct weights, each chosen edge is the unique lightest edge across that component's graph cut. The minimum spanning tree cut property puts every such edge in every minimum spanning tree, so the selected edges remain acyclic. Every nonfinal component has an outgoing edge in a connected input, and merging makes progress until a spanning tree remains. Duplicate choices of the same edge are one set insertion.

Each new component contains at least two old components, so there are $O(\log |V|)$ rounds. Scanning all edges per round gives $O(|E|\log |V|)$ time. Equal edge weights require a consistent secondary order to avoid choosing a cycle of tied edges.

Otakar Borůvka formulated the distinct-cost minimum-connection problem in 1926.^[ref]

An edge set respects a cut of a graph when none of its edges crosses that cut. In the minimum spanning tree cut property, this guarantees that exchanging a crossing tree edge cannot remove an edge already committed to the partial solution.

An edge is safe for the current accepted forest $F$ if some minimum spanning tree contains both $F$ and that edge. The loop invariant is that some minimum spanning tree contains every accepted edge. It holds initially for the empty edge set. Suppose the next accepted edge $e$ joins a current connected component of a graph $S$ to its complement. No earlier rejected edge crosses this cut of a graph: once its endpoints are in one connected component of a graph, subsequent merges never separate them. Thus $e$ is a lightest edge across that cut of a graph.

For the short exchange argument, take a minimum spanning tree $T$ containing $F$. If $e$ is absent, adding it creates a fundamental cycle. This graph cycle contains another edge $f$ crossing the same cut of a graph. No edge of $F$ crosses the cut of a graph, so $f$ is not in $F$. Replace $f$ by $e$: the result is a spanning tree containing $F$ and $e$, with no greater total weight because $w(e)\le w(f)$. It is therefore also a minimum spanning tree. This is the minimum spanning tree cut property in the form needed for tied weights.

In the example, $CD$ is safe after rejecting $AC$: the current connected component of a graph $\{A,B,C\}$ has crossing edges $CD,CE,BE$ of weights $4,6,7$. Its cheapest connection is $CD$. The rejected $AC$ is also the unique heaviest edge of the graph cycle $A,B,C,A$, so the minimum spanning tree cycle property excludes it from every optimum.

Negative and zero edge weights are allowed: the comparisons and exchange argument still apply. Ties can give several minimum spanning trees, though they need not; any order among equal-weight edges remains valid. Distinct edge weights guarantee a unique minimum spanning tree. To see why, take the lightest edge $e$ belonging to exactly one of two proposed optima, say $T$. Deleting $e$ from $T$ gives a cut of a graph; the other optimum has a graph path across it, containing an edge $f$ absent from $T$. Hence $w(e)<w(f)$, and replacing $f$ by $e$ improves that other optimum, a contradiction. For disconnected input, process all edges to obtain a minimum spanning forest, one minimum spanning tree per original connected component of a graph; no spanning tree of the whole graph exists.^[ref]

The two pieces of a one-tree can be optimized independently. Compute a minimum spanning tree $F$ on vertices $\{2,\dots ,n\}$ and choose the two cheapest distinct edges incident to vertex one. Return their union.

Every feasible one-tree contains such a spanning tree and such a pair, so its cost is at least the sum of these two independent minima. Their union is itself feasible, attaining that lower bound. This proves optimality.

Use Prim's algorithm for $F$: repeatedly add a cheapest edge crossing from the current tree to an unvisited vertex. The minimum spanning tree cut property makes each chosen edge safe. With the dense weight matrix of a complete graph, maintain the best connection to each unvisited vertex and select the least one by a scan. There are $n-2$ iterations with $O(n)$ work apiece. A further scan finds the two cheapest incident edges. Thus the total complexity is $\boxed{O(n^2)}$, with $O(n)$ additional working storage beyond the input matrix.

For a connected undirected weighted graph, a spanning tree connects all vertices without a graph cycle. A minimum spanning tree minimizes the sum of its edge weights. Disconnected input has no spanning tree, although the same methods produce a minimum spanning forest. Negative edge weights and ties cause no difficulty; a tree always contains exactly $|V|-1$ edges.

The central exchange argument is the minimum spanning tree cut property. Suppose a forest $F$ is contained in some minimum spanning tree $T$, and consider a cut with no edge of $F$ crossing it. Let $e$ be a lightest crossing edge. If $e\notin T$, adding it creates a graph cycle; the graph path in $T$ between its endpoints contains a crossing edge $f$. That $f$ is not in $F$, and $w(e)\le w(f)$. Thus $T-f+e$ is another spanning tree with no larger weight and still contains $F$. It is also minimum and contains $F\cup \{e\}$. This proves that the chosen edge is safe, rather than merely asserting a greedy choice.

Kruskal's algorithm sorts all edges by increasing weight, starts with the empty forest, and adds an edge precisely when its endpoints are in different components. Each added edge is lightest across a component cut respected by the current forest. The exchange proof inductively keeps the forest inside a minimum spanning tree; connectedness makes the final forest a spanning tree, hence an optimum. Sorting takes $O(|E|\log |E|)$ comparisons, and even a simple component-merging implementation takes only polynomial additional work. Efficient component tracking improves that overhead further.

Prim's algorithm instead grows a single tree, repeatedly adding a lightest edge from its vertex set to the outside. The same cut argument proves correctness. A dense implementation using an array runs in $O(|V{|}^2)$ comparisons. The dual minimum spanning tree cycle property says a uniquely heaviest edge of a graph cycle belongs to no minimum spanning tree: exchanging it for a lighter crossing edge strictly improves any tree containing it. Ties must be handled carefully; a merely nonunique heaviest edge can occur in an optimum.

Complexity classes are formally classes of decision problems, so use the version asking whether a graph has a spanning tree of total weight at most a supplied threshold $K$. Assume integer or rational weights and threshold are encoded in binary. The input length includes all these bits, not only the numbers of vertices and edges. P consists of decision problems decidable by a deterministic algorithm in time polynomial in that input length. NP consists of those with polynomial-size complexity certificates verified in deterministic polynomial time, equivalently decidable in polynomial time by a nondeterministic machine.

Kruskal's algorithm constructs the optimum and compares its weight with $K$. Binary integer comparisons and sums are polynomial-time operations. Rational comparisons can be made by cross multiplication, and their summed numerator and denominator have polynomially bounded bit length: a product of input denominators has bit length no greater than the sum of their bit lengths. The combinatorial algorithm makes polynomially many such operations. Hence the minimum-spanning-tree decision problem is in P; the optimization version likewise has a polynomial-time algorithm.

For membership in NP, the complexity certificate is a list of $|V|-1$ selected edges. Check that every edge is present, that the edges connect all vertices and contain no graph cycle, and that their total weight is at most $K$. A graph search and binary arithmetic do this in polynomial time. A successful complexity certificate need not establish that its tree is minimum: it proves the threshold question's yes-answer. Conversely, a yes-instance has such a tree as a complexity certificate. ThereforeMembership in NP does not arithmetic mean NP-hardness; here the explicit greedy algorithm provides the stronger tractability result.

Assume the finite graph is connected, as is necessary for a spanning tree to exist. For a disconnected graph, the same procedures operate separately on its connected components of a graph and produce a minimum spanning forest.

Let $T$ be a minimum spanning tree. If it omitted the unique lightest edge $e$ across the specified cut of a graph, adding $e$ would make exactly one graph cycle: the graph path in $T$ between its endpoints, followed by $e$. Since those endpoints are on opposite sides of the cut of a graph, that graph path contains another crossing edge $f$. Distinct weights give $w_f>w_e$. The graph $T+e-f$ is still a spanning tree, but has smaller total weight, contradicting minimality. Thus every minimum spanning tree contains $e$, the minimum spanning tree cut property.

Prim algorithm starts from one graph vertex, repeatedly choosing the lightest edge from the reached graph vertices to an unreached graph vertex. Connectivity ensures that such an edge exists until all graph vertices have been reached. Each choice adds one new graph vertex and creates no graph cycle. By the minimum spanning tree cut property, every chosen edge belongs to every minimum spanning tree. After $|V|-1$ choices the selected edges form a spanning tree, necessarily a minimum spanning tree.

For Kruskal algorithm, suppose the next accepted edge $e$ joins two different components of the current forest, and let $S$ be one of those components. No previously considered lighter edge crosses $S$: an accepted one already joins graph vertices within a current component, while a rejected one had its endpoints connected when it was rejected and therefore still has them in a single current component. Consequently $e$ is lightest across the cut of a graph defined by $S$. The minimum spanning tree cut property again places every accepted edge in every minimum spanning tree. At termination the accepted forest must be connected, since otherwise a crossing edge of the original connected graph would have been accepted when considered. It is therefore a minimum spanning tree.

This reasoning also proves the minimum spanning tree is unique. Either procedure produces a spanning tree all of whose $|V|-1$ edges belong to every minimum spanning tree; another minimum spanning tree cannot have any different edge.

For the minimum spanning tree cycle property, suppose a spanning tree $T$ contained the unique heaviest edge $e$ of a graph cycle $C$. Removing $e$ splits $T$ into two components. The remainder of $C$ connects the endpoints of $e$, so it contains an edge $f$ across these components. This edge cannot belong to $T-e$, and $w_f<w_e$. Hence $T-e+f$ is a lighter spanning tree. Thus no minimum spanning tree contains $e$.

Finally consider the reverse-delete algorithm, processing edges from largest to smallest weight. Whenever an edge is retained because its deletion would disconnect the current graph, it is a bridge in a graph; deleting other edges later cannot create an alternative path around it, so it remains a bridge in a graph. If a currently processed edge $e$ is deletable, it lies on a current graph cycle. None of that graph cycle's other edges can be an earlier retained heavier edge, since those are bridges in a graph. Thus all other edges on the graph cycle are lighter than $e$. The minimum spanning tree cycle property says that deleting $e$ removes no edge of any minimum spanning tree of the original graph. Throughout, connectivity and the presence of the unique minimum spanning tree are preserved. At termination a surviving graph cycle is impossible: any of its edges was deletable when considered, since that entire surviving graph cycle already existed then. The final connected graph is a tree, and hence is exactly the minimum spanning tree.

For a finite connected graph, a spanning tree contains every graph vertex and is connected and acyclic. A minimum spanning tree minimizes ${\sum }_{e\in E(T)}w(e)$ over all such trees. A shortest-path tree rooted at $v$ is a spanning tree whose unique $v$-to-$u$ graph path has length $d_G(v,u)$ for every graph vertex $u$. Here the weighted path length is the sum of its edge weights. The two optimizations generally differ, as (b) shows. Connectedness is needed for either spanning-tree object to exist.

For the grid, Kruskal's algorithm examines edges in nondecreasing order of weight and accepts an edge exactly when it joins two different components of the current forest. The weights are encountered in the orderThe horizontal and vertical acceptance rules are detailed in the two numbered subanswers. Together they produceThere are $(n-1)(n+2)/2$ horizontal and $n(n-1)/2$ vertical edges, totaling $n^2-1$. Every accepted edge attaches a previously isolated graph vertex to the component already built, so the result is connected and acyclic. The correctness theorem for Kruskal's algorithm, which follows from the minimum spanning tree cut property, proves minimality. Its total cost isFor $n=1$ the tree has one graph vertex, no edges and cost zero. The source's numbered items specify the two edge types; the following subanswers record their contributions to the algorithm.

A precise safe-extension form of the cut lemma for minimum spanning trees is as follows. Let $F\subseteq E$ be contained in some minimum spanning tree. Let $S$ be a nonempty proper subset of $V$, and suppose no edge of $F$ crosses the cut of a graph $(S,V\setminus S)$. If $e$ is any least-weight crossing edge, thenTo prove it, choose a minimum spanning tree $T$ containing $F$. If $e\in T$, it already certifies the claim. Otherwise inserting $e$ creates a graph cycle. The other part of that graph cycle must cross the cut of a graph, so choose a crossing edge $f\in T$. It does not belong to $F$, and $w(e)\le w(f)$. Then $T-f+e$ is a spanning tree containing $F\cup \{e\}$, of weight no greater than the optimum. It is therefore also optimal.

With $F=\varnothing$, a lightest crossing edge belongs to at least one minimum spanning tree. If that edge is uniquely lightest, it belongs to every minimum spanning tree, the strict version of the minimum spanning tree cut property. With ties, “every” would be false: in an equal-weight triangle either crossing edge can be omitted from some optimum.

Prim's algorithm grows a tree from any root $r$. For each vertex outside the current tree, its priority queue key is the cheapest single edge connecting it to the tree, not the total length of a root-to-vertex path:The indexed priority queue supports membership and locating a vertex's heap entry. After the first extraction, the chosen parent edge is a least-weight edge crossing the cut between the current tree and its complement. The minimum spanning tree cut property makes that edge safe: exchanging it for a crossing edge of a suitable minimum tree preserves minimality. Repeating this establishes a minimum tree. Connectivity ensures every nonroot vertex eventually has a parent; edge weights may be negative.

It is a greedy algorithm because it commits at every step to the cheapest remaining edge that can be added without creating a graph cycle, without revising earlier choices. The minimum spanning tree cut property explains why these locally cheapest admissible choices can be extended to an optimal spanning tree.

The procedure is Borůvka's algorithm. In the first round, visiting singleton components in the order $a,b,c,d,e,f,g,h$, the chosen edges are respectivelyThe set of new edges is $\{ac,be,cf,df,eh,eg\}$: repeated selections of $df$ and $eh$ insert no extra copy. The resulting two components are $\{a,c,d,f\}$ and $\{b,e,g,h\}$. Each chooses $fh$ in round two, producing the weight-36 tree from part (d). The within-round order of distinct insertions can therefore be $ac,be,cf,df,eh,eg$, followed by $fh$ in the next round; it need not be the globally sorted Kruskal order.

The required minimum spanning tree cut property says: for every nonempty proper subset $C\subset V$, the unique minimum-weight edge crossing the cut $(C,V\setminus C)$ belongs to every minimum spanning tree. Indeed, add this edge to a tree that lacks it. The resulting cycle contains another edge crossing the cut, which is strictly heavier; replacing that edge decreases the total weight.

For the general proof, assume all edge weights are distinct. Fix the components at the beginning of a round, as the given procedure does. Each selected edge is the unique lightest edge across one of their cuts, so belongs to every minimum spanning tree. Inductively, the entire selected set is contained in such a tree and is therefore acyclic. While there is more than one component, connectedness supplies an outgoing edge for each, so at least two components merge. The finite process terminates connected. A connected subgraph of a spanning tree must be that whole tree, proving that the returned set is a minimum spanning tree.

For a connected, weighted, undirected graph, grow a tree from any root $r$. For every vertex outside the tree, store the cheapest edge currently connecting it to the tree, not its source-path distance:

for v in V: key[v] = infinity; parent[v] = none
key[r] = 0
Q = indexed min-priority-queue containing all vertices
while Q is not empty:
    u = extract-min(Q)
    if parent[u] != none: output edge (parent[u],u)
    for each edge {u,v} of weight w with v still in Q:
        if w < key[v]:
            key[v] = w
            parent[v] = u
            decrease-key(Q,v,w)

The maintained key chooses the minimum-weight edge crossing the cut between the tree and remaining vertices. The minimum spanning tree cut property makes that edge safe; induction therefore preserves the existence of a minimum spanning tree containing all selected edges. This proves why Prim's algorithm is greedy and correct. With adjacency lists and a binary heap its time is $O((|V|+|E|)\log |V|)$. For a disconnected graph, starting another component when the minimum key is infinity produces a minimum spanning forest instead of claiming that a spanning tree exists.

The minimum spanning tree cut property, in its safe-edge form, says: if an edge set $A$ is contained in some minimum spanning tree, a cut of a graph respects $A$, and $e$ is a light edge crossing a cut, then $A\cup \{e\}$ is contained in some minimum spanning tree.

Choose an MST $T$ containing $A$. If $e\in T$, nothing changes. Otherwise adding $e$ creates its unique fundamental cycle. The path in $T$ between the endpoints of $e$ must cross the chosen cut; take such an edge $f$. Since the cut respects $A$, $f\notin A$. Since $e$ is light, $w(e)\le w(f)$. The exchange $T-f+e$ is a spanning tree containing $A\cup \{e\}$, with total weight no greater than that of $T$. Minimality of $T$ forces equal optimum weight, proving the claim. Equal edge weights cause no difficulty: “safe” means belonging to some compatible optimum, not to every optimum.

Start Prim's algorithm at vertex $1$, since the source does not specify a starting vertex. Write every undirected edge with its smaller endpoint first. With lexicographic tie-breaking, the accepted edges are $(1,2),(1,3),(2,4),(4,6),(4,5)$, of total weight 9.

Initially $(1,2)$ is the cheapest crossing edge. The next minimum is a weight-two tie between $(1,3)$ and $(2,4)$, so choose $(1,3)$. Then the weight-two tie between $(2,4)$ and $(3,4)$ is resolved in favour of $(2,4)$. Adding vertex $4$ exposes the weight-one edge $(4,6)$, which is selected next. Finally $(4,5)$ precedes $(5,6)$ among the weight-three choices. Every accepted edge crosses from the existing tree to a new vertex, as required by the minimum spanning tree cut property. A different starting vertex can produce a different accepted-edge order; the displayed answer fixes that unspecified choice. The algorithm is named for Robert C. Prim.

The minimum spanning tree cut property says: if a cut of a graph respects an edge set $A$ contained in some minimum spanning tree, a minimum-weight edge across that cut is safe to add to $A$, meaning that some minimum spanning tree contains $A$ together with that edge. Respecting $A$ means no edge of $A$ crosses the cut. In particular, any lightest cut edge belongs to some minimum spanning tree; a uniquely lightest cut edge belongs to every minimum spanning tree.

For the exchange argument, take a minimum spanning tree $T$ containing $A$. If it lacks the chosen edge $e$, add $e$ to create its fundamental cycle. The remaining route between $e$'s endpoints crosses the cut at some edge $e^{\prime }$, with $w(e^{\prime })\ge w(e)$. Since the cut respects $A$, $e^{\prime }\notin A$. Replacing $e^{\prime }$ by $e$ preserves a spanning tree, retains $A$, and cannot increase weight. Hence it is also minimum. Strict inequality would contradict minimality, which gives the unique-lightest assertion.

For an illustration, take a triangle with weights $w(ab)=1$, $w(ac)=2$, $w(bc)=3$. Across the cut $\{a\}\mid \{b,c\}$, $ab$ is the unique lightest edge and must be in every minimum spanning tree. The minimum tree is $\{ab,ac\}$, of weight $3$. With tied light edges, the existence assertion need not mean that every minimum spanning tree contains the particular tied edge chosen.

Start from one graph vertex. Repeatedly add the least-weight edge joining the reached graph vertices to an unreached graph vertex. Each step grows a tree and obeys the minimum spanning tree cut property. On a finite connected graph, the result is a minimum spanning tree.