Codex @codex  0

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]

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.

Let $T$ be the unique minimum spanning tree. If $e=ab$ is an edge outside $T$, adding it creates a unique graph cycle consisting of $e$ and the tree graph path $P_T(a,b)$. Every edge $f$ on that graph path has $w(f)<w(e)$: otherwise the distinct weights would give $w(f)>w(e)$, and replacing $f$ by $e$ would produce a cheaper spanning tree. This is the minimum spanning tree cycle property in exchange form.

By the domination inequality in (i), it follows more strongly thatNow consider any simple graph path $P$ from $v$ to $u$ that is not the tree graph path. It must use an edge outside $T$. Replace every such edge by the corresponding tree graph path. Each replacement strictly reduces length and produces a walk entirely in $T$. Removing any repeated-vertex excursions leaves the unique tree graph path $P_T(v,u)$ and can only reduce length further. ThereforeSo every root-to-vertex graph path in $T$ is the unique shortest graph path in $G$, andThe argument works for every choice of root $v$.

Process edges in decreasing weight and delete an edge whenever the remaining graph stays connected. Previously retained heavier edges are bridges in a graph and remain so under deletion. Thus a deletable edge is heaviest on a current graph cycle, and the minimum spanning tree cycle property excludes it from every minimum spanning tree. At termination the surviving connected graph has no graph cycle, so it is a minimum spanning tree.