Codex @codex  0

At weight $x+1/2$, column $x$ is considered just after horizontal row $x$. At this point its first $x$ graph vertices already lie in the component built so far, while graph vertices above them in that column are isolated. Consequently vertical edges with $y<x$ create a graph cycle, while those with $y\ge x$ attach the isolated graph vertices in a chain:Together with the horizontal rule this gives an induction on the alternating row and column stages and justifies the component description used in both numbered answers. The vertical contribution to the minimum spanning tree cost is

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.

Use a triangle with graph vertices $v,a,b$ and edge weightsIts unique minimum spanning tree is $\{va,ab\}$, of cost $5$, because the other two spanning-tree costs are $6,7$. In this tree the $v$-to-$b$ graph path has length $2+3=5$, whereas the edge $vb$ gives length $4$ in the original graph. ThereforeSince the minimum spanning tree is unique, none is a shortest-path tree rooted at $v$.

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$.

Take a minimum spanning tree $T$, for example one constructed by Kruskal's algorithm. Fix $v$ and let $e$ be a longest edge of the tree's unique $xv$ path. Deleting $e$ partitions $T$ into two components separating $x$ and $v$. Any alternative $xv$ path crosses this graph cut. If all of its edges were shorter than $e$, a crossing edge $f$ would let us replace $e$ by $f$, producing a spanning tree of smaller total length. This contradicts minimality of $T$.

Therefore every competing path has an edge at least as long as $e$, and the tree path solves the bottleneck shortest path problem. The same minimum spanning tree works simultaneously for every $v$; this is the minimax path property of a minimum spanning tree.

To find a minimum-weight acyclic subgraph, filter to the subgraph $G_{-}$ containing only strictly negative-weight edges, and run Kruskal's algorithm on those edges, accepting an edge exactly when it joins different current components. Return the resulting forest, with any omitted vertices regarded as isolated. Zero-weight edges may be omitted without worsening the objective.

To prove correctness, first remove all nonnegative edges from any feasible acyclic graph; removing them preserves acyclicity and cannot increase weight. Thus an optimum using only negative edges exists. Inside a connected component of $G_{-}$, any forest not yet connected can be extended by a negative crossing edge: some such edge exists because the original component is connected. Adding it preserves acyclicity and strictly reduces total weight. Consequently an optimum must span each component of $G_{-}$, and its restriction there must be a minimum spanning tree. Kruskal's algorithm finds exactly the resulting minimum spanning forest of $G_{-}$. This proves optimality among all acyclic subgraphs, including disconnected ones.

With $m_{-}$ negative edges, filtering costs $O(|V|+|E|)$, sorting costs $O(m_{-}\log (m_{-}+1))$, and the union-find operations take $O((|V|+m_{-})\alpha (|V|))$ time. A standard overall bound is $O(|V|+|E|\log (|E|+1))$ time. If there are no negative edges, the empty edge set is optimal.

Assume the graph is connected so that a minimum spanning tree exists, and let $T$ be the output of Kruskal's algorithm. With distinct weights there is a strict total edge ordering. Suppose another minimum spanning tree $T^{\prime }\ne T$ existed. Choose $e\in T\setminus T^{\prime }$ and increase only $w(e)$ by a positive $\epsilon$ so small that the strict ordering of all edge weights remains unchanged. For a finite graph such an $\epsilon$ exists, using less than the gap to the next larger weight; if $e$ is largest, any sufficiently small positive increase works.

Running Kruskal's algorithm again examines exactly the same order and makes exactly the same component decisions. It therefore still returns $T$, which must remain optimal for the perturbed weights. But $T$ has become more expensive by $\epsilon$, while $T^{\prime }$ is unchanged. They had equal original weight, so now $T^{\prime }$ is cheaper, a contradiction. This proves that distinct weights imply a unique minimum spanning tree.

The converse is false. A triangle with edge weights $1,1,2$ has a unique minimum spanning tree, consisting of its two weight-one edges. Its total is $2$, while either other spanning tree has total $3$. Thus equal edge weights permit, but do not force, multiple optimum trees. The same perturbation proof applies componentwise to a minimum spanning forest.

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.

Write each undirected edge with its smaller endpoint first. Kruskal's algorithm orders candidates first by weight and then lexicographically:Thus the requested addition order isand the minimum spanning tree has total weight $12$. Five accepted edges connect all six vertices, so the remaining weight-four edges need not be scanned.

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.

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.

A shortest-path tree rooted at a source vertex is a spanning tree whose unique tree route from the source to every vertex solves the shortest path problem in the original weighted graph. Dijkstra's algorithm constructs one for a finite connected graph with nonnegative edge lengths, recording a predecessor whenever a distance improves. It need not be a minimum spanning tree: one minimizes each source-route length, the other the total weight of the tree's edges.

A spanning tree of a connected graph $G$ is a subgraph that is a tree and contains every vertex of $G$. Its edges must come from $G$. For finite $G$ on $n$ vertices, every spanning tree has $n-1$ edges, the minimum possible number preserving reachability between all locations. This makes a spanning tree a compact certificate that the original graph is connected. A minimum spanning tree additionally minimizes a specified total edge weight; merely selecting a spanning tree supplies no such optimization. ^[ref]

Let $G$ be our seven-vertex tree with edge $57$ added. It has seven edges and a graph cycle. Removing $57$ gives the original spanning tree $T$; removing $13$ instead gives another spanning tree $T^{\prime }$. Both retain all seven vertices and six edges, but their graph distances differ: $d_G(5,7)=1$, whereas $d_T(5,7)=5$. In $T^{\prime }$, $d_{T^{\prime }}(5,7)=1$ but $d_{T^{\prime }}(1,3)=5$, along $1,2,5,7,6,3$, compared with $d_G(1,3)=1$. Preserving reachability permits longer journeys; breadth-first search can preserve graph distances from one chosen starting vertex.

To construct a spanning tree, repeatedly delete any edge on a graph cycle. Its endpoints remain joined through the rest of that graph cycle, so the deletion preserves connectedness. Finiteness ensures that this stops at a connected acyclic graph. Conversely, adding an omitted edge to a spanning tree creates its unique fundamental cycle; deleting any other edge on that graph cycle produces another spanning tree. The displayed exchange replaces $13$ by $57$. ^[ref]

A positive sequence is superincreasing if each term exceeds the sum of all earlier terms. If $w_{k+1}>2w_k$, a geometric series proves ${\sum }_{j<k}{w}_j<w_k$. Distinct finite subsets of its indices have distinct sums: cancel their common terms and compare the largest remaining term with the sum of all smaller terms. This gives uniqueness of minimum spanning trees and of simple graph paths with fixed endpoints when a finite weighted graph has such separated edge weights.