A precise safe-extension form of the cut lemma for minimum spanning trees is as follows. Let be contained in some minimum spanning tree. Let be a nonempty proper subset of , and suppose no edge of crosses the cut of a graph . If is any least-weight crossing edge, thenTo prove it, choose a minimum spanning tree containing . If , it already certifies the claim. Otherwise inserting creates a graph cycle. The other part of that graph cycle must cross the cut of a graph, so choose a crossing edge . It does not belong to , and . Then is a spanning tree containing , of weight no greater than the optimum. It is therefore also optimal.
With , 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.
A spanning tree is a connected acyclic subgraph containing every vertex. A minimum spanning tree minimizes the sum of edge weights over all spanning trees. In a three-vertex triangle with every edge weight 1, deleting any of the three edges gives a different spanning tree of total weight 2. Hence there are three minimum spanning trees; minimum total weight need not mean a unique tree.
True. Every spanning tree contains precisely the vertex set by definition. Thus every minimum spanning tree has nodes, independently of the weights or which minimum tree is chosen.
A spanning tree is a connected acyclic subgraph containing every vertex of the original undirected graph. For a graph with vertices it has edges. A minimum spanning tree minimizes the sum of its edge weights over all spanning trees:Connectedness guarantees existence for a finite graph; equal weights can permit several minimizers.
Processing by increasing weight, Kruskal's algorithm accepts of weight one and of weight two, then rejects of weight three because its endpoints are already connected. It accepts , , , skips , accepts , skips , and accepts . Seven accepted edges now connect all eight vertices.
The resulting minimum spanning tree isThe remaining heavier edges are unnecessary once the tree is complete. Distinct edge weights also imply that this minimum spanning tree is unique.
The minimum spanning tree cut property, in its safe-edge form, says: if an edge set is contained in some minimum spanning tree, a cut of a graph respects , and is a light edge crossing a cut, then is contained in some minimum spanning tree.
Choose an MST containing . If , nothing changes. Otherwise adding creates its unique fundamental cycle. The path in between the endpoints of must cross the chosen cut; take such an edge . Since the cut respects , . Since is light, . The exchange is a spanning tree containing , with total weight no greater than that of . Minimality of forces equal optimum weight, proving the claim. Equal edge weights cause no difficulty: “safe” means belonging to some compatible optimum, not to every optimum.
True. Delete ; the resulting two connected components define a cut of a graph. If a crossing edge had , the exchange would be a spanning tree of smaller total weight, contradicting the minimum spanning tree assumption. Thus is a light edge crossing a cut for this fundamental cut. It need not be uniquely light.
Maintain two spanning trees whose sorted edge sequences share a prefix, initially of length zero. At the next position, select whichever next edge has smaller weight, breaking equal-weight ties arbitrarily. Keep that tree unchanged and apply spanning-tree prefix exchange from part (i) to the other tree. Both trees now have a common prefix one edge longer; one tree's sorted weight vector is unchanged and the other's cannot increase coordinatewise.
Repeat for positions. The final trees have all their edges in common, so they are one tree . Throughout, the sorted weight vector of never exceeds its original vector from , and that of never exceeds its original vector from . Consequently their common final vector satisfies at every position.
This proves the required existence without assuming either original tree was minimum. More generally, a minimum spanning tree has a coordinatewise minimum spanning-tree weight vector: after restricting the graph to edges of weight at most any threshold, a maximum forest contains at least as many edges as the corresponding portion of every other spanning tree. This threshold viewpoint explains why an optimum can simultaneously dominate every sorted coordinate, rather than merely having a smaller total weight.
To find a minimum-weight acyclic subgraph, filter to the subgraph 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 , 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 , and its restriction there must be a minimum spanning tree. Kruskal's algorithm finds exactly the resulting minimum spanning forest of . This proves optimality among all acyclic subgraphs, including disconnected ones.
Assume the graph is connected so that a minimum spanning tree exists, and let be the output of Kruskal's algorithm. With distinct weights there is a strict total edge ordering. Suppose another minimum spanning tree existed. Choose and increase only by a positive so small that the strict ordering of all edge weights remains unchanged. For a finite graph such an exists, using less than the gap to the next larger weight; if 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 , which must remain optimal for the perturbed weights. But has become more expensive by , while is unchanged. They had equal original weight, so now is cheaper, a contradiction. This proves that distinct weights imply a unique minimum spanning tree.
The converse is false. A triangle with edge weights has a unique minimum spanning tree, consisting of its two weight-one edges. Its total is , while either other spanning tree has total . 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 contained in some minimum spanning tree, a minimum-weight edge across that cut is safe to add to , meaning that some minimum spanning tree contains together with that edge. Respecting means no edge of 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 containing . If it lacks the chosen edge , add to create its fundamental cycle. The remaining route between 's endpoints crosses the cut at some edge , with . Since the cut respects , . Replacing by preserves a spanning tree, retains , 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 , , . Across the cut , is the unique lightest edge and must be in every minimum spanning tree. The minimum tree is , of weight . 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 . Five accepted edges connect all six vertices, so the remaining weight-four edges need not be scanned.
Prim's algorithm 2026-10-14
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.
Reverse-delete algorithm Created 2026-10-14 Updated 2026-11-05
The reverse-delete algorithm processes edges of a finite connected undirected weighted graph in nonincreasing weight order, deleting an edge whenever the graph stays connected.
Maintain the invariant that the surviving graph contains some minimum spanning tree. A deletable edge lies on a cycle. Previously retained heavier edges are bridges and remain bridges after further deletions, so every other edge on that cycle has weight at most . If a current optimum contains , removing it creates a cut. Another cycle edge crosses that cut; replacing by gives a surviving tree of no greater weight. Thus an optimum remains after deleting .
At termination the graph is connected and acyclic, hence is itself a minimum spanning tree. With tied weights, need not be excluded from every optimum. On a triangle with all weights one, every edge belongs to some optimum, yet deleting any one edge is safe. The minimum spanning tree cycle property excludes an edge from every optimum only when it is uniquely heaviest on a cycle.
Robert C. Prim Created 2026-10-24 Updated 2026-11-05
Robert C. Prim was a computer scientist whose Prim's algorithm constructs a minimum spanning tree. Starting from one vertex, it repeatedly adds a least-weight edge connecting the current tree to a new vertex. The goal is to minimize the total weight needed to connect every vertex, rather than to minimize each route from a chosen source.[ref]
His paper motivated the problem through communication, distribution and transportation networks, including leased communication lines. Its opening map connects Washington and the then forty-eight state capitals. That application shows how a geometric network-design question becomes a reusable optimization problem on a graph.[ref]
Shortest Connection Networks and Some Generalizations by Robert C. Prim. Page 1389 and figure 1
Shortest-path tree Created 2026-10-25 Updated 2026-10-31
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.
Spanning tree Created 2026-09-24 Updated 2026-10-14
A spanning tree of a connected graph is a subgraph that is a tree and contains every vertex of . Its edges must come from . For finite on vertices, every spanning tree has 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 be our seven-vertex tree with edge added. It has seven edges and a graph cycle. Removing gives the original spanning tree ; removing instead gives another spanning tree . Both retain all seven vertices and six edges, but their graph distances differ: , whereas . In , but , along , compared with . 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 by . [ref]
https://www.maths.tcd.ie/~dwilkins/Courses/MA2C03/MA2C03Courseware_2014to15/MA2C03_S4_Yr1415.pdf. Trinity College Dublin, section 4.16: deleting cycle edges preserves connectivity
Superincreasing sequence 2026-10-25
A positive sequence is superincreasing if each term exceeds the sum of all earlier terms. If , a geometric series proves . 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.


