Build a minimum spanning tree while keeping it distinct from a shortest-path tree.
By the end: justify a safe light edge and explain the cost of requiring a tree.
A tree is a connected undirected graph with no cycles. Between any two vertices it has exactly one path: two distinct paths would form a cycle. A tree on n vertices has n minus one edges. Removing any edge disconnects it, while adding one new edge creates a cycle.
A spanning tree includes every vertex of the original connected graph and only selected original edges. A minimum spanning tree, or MST, minimizes the sum of those selected edge weights. It does not minimize every source-to-destination distance. A shortest-path tree minimizes routes from one chosen source instead of total construction cost.
Imagine four sites A, B, C, D with possible undirected cables A-B costing 2, A-C costing 3, B-C costing 1, B-D costing 4, and C-D costing 2. These are the complete available pairs. The costs are construction units paid once for each selected cable, irrespective of how many journeys later use it. A spanning tree must include every site and connect them using these records without a cycle. We can begin with four isolated groups and ask what each cable purchase accomplishes. An edge between different groups merges them; an edge within one group does not.
A forest is an undirected graph with no cycles. Each connected component is a tree, including a single isolated vertex. The selected edges together with all four vertices form a forest throughout these joins. This group count explains the edge total rather than merely asserting it. Initially four separate vertices give four groups. Each accepted edge between different groups reduces that count by exactly one. Reaching a single group therefore requires three such edges. More generally, starting with n vertices requires n minus one successful joins. Edges added inside an existing group create cycles instead of reducing its group count. A connected graph with exactly n minus one edges cannot afford any such redundant edge. Otherwise too few successful joins would remain to combine all of the original isolated vertices.
Choose B-C first at cost 1, then A-B at cost 2, then C-D at cost 2. The groups change from four singletons to {A}, {B,C}, {D}, then {A,B,C}, {D}, and finally {A,B,C,D}. The selected cost is 5. The unused A-C edge joins vertices already connected by A-B-C, so adding it would create a triangle. The unused B-D edge similarly has the existing alternative B-C-D. The original map contains those alternatives; the selected tree does not. Keep the available edges and the purchased subset distinct when checking what the design permits.
To see the exchange mechanism directly, take a different tree A-B, A-C, C-D costing 7. Add B-C, the cost-1 edge missing from that tree. It creates exactly the cycle A-B-C-A. Remove A-C, costing 3, from that cycle. A and C remain connected through B, and D still connects through C. The result is again a spanning tree, now costing 5. The temporary addition provides an alternative path, which makes a compensating removal possible. Removing an edge outside the cycle would instead risk disconnecting a branch while leaving the cycle intact.
This also explains why selecting the cheapest edge touching each vertex is not a general recipe. Consider the separate graph with A-B costing 1, C-D costing 1, and B-C costing 8, and no other edges. Each vertex's cheapest incident edge lies within one of the pairs. Their union buys only A-B and C-D, leaving two groups. The expensive joining edge is necessary despite being neither endpoint's cheapest choice. A spanning problem asks for global connectivity, not just local participation. Every vertex having a selected neighbor does not establish that every pair of vertices can communicate.
A minimum spanning tree exists when the finite undirected input is connected, because at least one spanning tree exists and only finitely many edge subsets can be candidates. One construction begins with any connected selection and removes cycle edges until none remain. That proves existence, not cheapness. Comparing all candidate totals would find a minimum but could involve many subsets. The cut argument gives a more useful reason why particular inexpensive edges can be selected safely. It links a local comparison of crossing costs to the global objective of minimizing the complete tree's total.
A cut partitions the vertices into two nonempty sets. Every spanning tree must cross that cut. Suppose a lightest crossing edge is absent from an MST. Adding it creates a cycle with another crossing edge. Removing that other edge preserves connectivity and cannot increase cost. Thus some MST contains the chosen lightest edge.
With tied weights, that argument proves existence of an MST containing the edge, not membership in every MST. Kruskal's algorithm considers edges by increasing weight and accepts an edge only when it joins two different current components. Edges that close a cycle are rejected. This is a safe way to extend the partial forest.
In the four-site construction graph, separate {A,B,C} from {D}. Exactly B-D of cost 4 and C-D of cost 2 cross this cut. Any spanning tree must use at least one of them, because otherwise D would have no path to the other sites. C-D is the uniquely cheapest crossing edge. If a proposed minimum tree omitted it, adding C-D would create a cycle. The old path from C to D must cross the same partition, so that cycle contains another crossing edge. Replacing that edge by C-D reduces cost, contradicting the proposed minimum.
When crossing costs tie, the last word changes. Replacing one lightest crossing edge with another can preserve cost rather than reduce it. The argument then establishes that some minimum tree contains the chosen edge. It does not require all minimum trees to contain it. For example, in a triangle with all three costs 1, either edge leaving {A} is lightest. Both can appear together in a tree, but neither is individually compulsory. An algorithm needs permission to choose one optimum consistently, not evidence that every selected edge is inevitable under the optimization objective.
There is a further qualification when several edges have already been selected. A cut respects the selected forest if none of those edges crosses it. Equivalently, each current connected group sits wholly on one side. Suppose some minimum tree contains the forest already chosen. Add a lightest crossing edge for a respecting cut. Its exchange cycle contains another crossing edge, and that removable edge cannot belong to the selected forest because the cut crosses none of it. The exchange therefore preserves all earlier commitments. This stronger statement explains how a sequence of safe choices can remain jointly compatible.
Kruskal supplies such a cut automatically. When a candidate joins two current groups, take one entire group as one side of the cut and everything else as the other. No previously selected edge leaves that group. Could a cheaper crossing edge have been missed? It would have been considered earlier. If its endpoints were separate then, it would have been accepted; if they were already connected then, later joins could not separate them. Either way it cannot now cross between current groups. Thus the candidate is a lightest remaining crossing opportunity and is safe to add.
Work through the exact record order A-B, A-C, B-C, B-D, C-D in the construction graph. Sorting first by weight gives B-C at 1, A-B at 2, C-D at 2, A-C at 3, B-D at 4. The equal weight-2 pair retains original record order, so A-B comes before C-D. The first three edges join separate groups. A-C then meets the existing A-B-C path and is rejected; B-D meets B-C-D and is rejected. A rejected edge remains an available original edge. Rejection says it is unnecessary for this selected forest, not forbidden in the underlying network.
| Candidate | Decision | Groups after decision | Selected total |
|---|---|---|---|
| B-C: 1 | Accept | {A} {B,C} {D} | 1 |
| A-B: 2 | Accept | {A,B,C} {D} | 3 |
| C-D: 2 | Accept | {A,B,C,D} | 5 |
| A-C: 3 | Reject cycle | {A,B,C,D} | 5 |
| B-D: 4 | Reject cycle | {A,B,C,D} | 5 |
Another check begins with a completed tree. For each omitted edge, find the unique tree path between its endpoints. If the omitted edge is cheaper than some edge on that path, exchange those two and lower the total. In the cost-5 tree, A-C costs 3 while its tree path uses costs 2 and 1. B-D costs 4 while its tree path uses 1 and 2. Neither offers an improvement. In fact each omitted edge is strictly dearer than every edge on its path. Here that strictness rules out a tied alternative tree, even though two selected edges share weight 2.
Spanning tree. Total cost: 5.
Route costs: 0, 2, 3, 5.
Selected edge total: 7. Unreachable vertices have no parent.
| Edge by weight | Decision |
|---|---|
| B–C: 1 | Join different components |
| A–B: 2 | Join different components |
| C–D: 2 | Join different components |
| A–C: 3 | Reject cycle |
| B–D: 4 | Reject cycle |
| Kruskal choice | Cost units |
|---|---|
| B-C | 1 |
| A-B | 2 |
| C-D | 2 |
| Total | 5 |
Start with 'Four-site network' and inspect both panels. Kruskal selects B-C, A-B, C-D for total 5. Its tree preserves the minimum route costs from A, which are 0, 2, 3, 5. The direct A-C edge costs 3, exactly the same as A-B-C, but Dijkstra first labels C through A. When B later offers an equal candidate, strict improvement keeps that direct predecessor instead. Consequently the displayed shortest-path edge set is A-B, A-C, C-D, with selected-edge total 7, despite identical optimal route costs from A.
There are therefore two different observations to separate in this preset. The minimum tree happens to preserve optimal costs from A, yet the model's particular shortest-path tree can buy a different set of edges because of the tie to C. Neither observation establishes a general equivalence between objectives. A shortest-path tree can have unnecessary construction expense compared with an MST while still fulfilling every source-route requirement. Conversely, a cheap spanning tree may impose longer routes. Compare route totals along paths as well as the sum paid for the selected edge set before interpreting the pair of diagrams.
| Quantity | Minimum spanning selection | Displayed shortest-path selection |
|---|---|---|
| Selected records | B-C, A-B, C-D | A-B, A-C, C-D |
| Purchased edge total | 1 + 2 + 2 = 5 | 2 + 3 + 2 = 7 |
| Route A to B | A-B: 2 | A-B: 2 |
| Route A to C | A-B-C: 3 | A-C: 3 |
| Route A to D | A-B-C-D: 5 | A-C-D: 5 |
Select 'Route cost differs'. The graph is a triangle A-B costing 2, A-C costing 2, B-C costing 1. Kruskal first buys B-C, then buys A-B before A-C because their weights tie and A-B has the earlier record. Its total is 3. The unique tree route from A to C is A-B-C and costs 3. The shortest-path selection buys A-B and A-C, total 4, preserving route cost 2 to each destination. The tree with the lower construction bill loses one unit on the route to C. These costs encode different sums over the same records.
Now select 'Equal-cost triangle'. Every edge costs 1, so a spanning tree costs 2 whichever edge is omitted. Kruskal keeps the first two records, A-B and A-C. Both are safe, and the last B-C edge would close a cycle. Three possible minimum trees exist, but the interface shows one deterministic selection rather than cycling through alternatives. From A, the chosen star also gives direct shortest routes. If a different valid minimum tree omitted A-C, its A-to-C route would cost 2 instead of 1. Equal minimum construction totals need not mean equal routes for every source.
In 'Disconnected pairs', the records are A-B costing 2 and C-D costing 1. Kruskal buys both for total 3 and reports a forest rather than a spanning tree. Both groups include all their own vertices; no available edge joins the groups. The right panel starts only at A, so B costs 2 while C and D retain infinity and have no predecessor. The minimum forest includes C-D, but the A-rooted shortest-path selection does not. This difference is required by reachability, not an error in either calculation or a reason to erase the unreachable vertices.
These presets also show why an edge-count check is useful but incomplete. A connected four-vertex tree must have three selected edges, yet that count alone cannot certify connectivity or optimality. On four vertices, selecting all three sides of triangle A-B-C while leaving D isolated has three edges but is not a tree spanning all four. Even after connectivity and acyclicity are checked, a cheaper exchange could remain. The model's accept/reject rows provide the algorithmic reasoning. The simultaneous route panel supplies a contrasting objective, not a second independent proof of the minimum spanning claim.
For a disconnected input there is no spanning tree over all vertices. Applying the method to each component yields a minimum spanning forest. Negative weights do not invalidate the MST problem; its constraint still requires a tree, so it cannot collect extra negative cycle edges.
Every edge of a tree is a bridge within that tree. A cheap tree may therefore be a poor design for a system required to survive one link failure. Adding redundancy changes the optimization problem. Keep the requirement to connect all sites separate from budget, latency, reliability, and equity goals.
For pure construction cost, paying for an edge around a cycle seems avoidable when all costs are positive. Remove one cycle edge and connectivity survives through the rest of that cycle, reducing total cost. Under a tree requirement, cycle edges are forbidden regardless of their prices. This distinction matters with negative costs, which might represent a subsidy in a constructed optimization example. Use vertices A, B, C and all three triangle edges, each costing negative 1. Every spanning tree costs negative 2. Buying the entire triangle costs negative 3 but violates the tree constraint, so it is not a cheaper feasible tree.
Kruskal still works with negative tree weights because its exchange proof compares edge costs, not distances accumulated along walks. A tree contains no cycle to repeat, and its objective sums each selected edge once. By contrast, Dijkstra requires nonnegative weights for its settling proof. The spanning comparison offers only nonnegative presets because it also runs Dijkstra in the other panel. The negative triangle is a paper case about the mathematical tree problem, not a request to enter unsupported values. The general graph validation range alone does not establish that every algorithm accepts every validated graph.
A useful contrast with shortest routes concerns adding a constant to all weights. Every spanning tree on the same n vertices uses exactly n minus one edges. Adding 3 to each weight therefore adds the same 3 times n minus one to every candidate tree total, preserving their order. In the four-site construction graph the minimum total changes from 5 to 14, with the same selected edges. Route candidates can have different edge counts, so the same transformation need not preserve their ordering. Multiplying all weights by a positive factor preserves both kinds of additive comparison.
If the requirement becomes surviving any single selected-cable loss, a cycle edge is no longer automatically waste. In the three-site graph A-B costing 2, A-C costing 2, B-C costing 1, the cost-3 tree fails when either selected edge is removed. Buying all three edges costs 5 and preserves connectivity after any one edge loss. The remaining two edges always connect the three sites. That is a precise structural guarantee under a single-edge-loss assumption. It says nothing about failure frequency, shared damage to two cables, or whether the site equipment itself remains available.
Small weight changes can also have different implications for total cost and selected identity. Begin with a triangle whose three edges each cost 1 and keep record order A-B, A-C, B-C. There are three minimum trees of total 2. Raise A-B to 2 while leaving the others at 1. The unique minimum now uses A-C and B-C, still totaling 2. The chosen cable changes, but the optimal bill does not. If A-B had already been purchased, replacement costs would introduce a new decision problem. The static MST objective does not include sunk costs or construction stages unless they are modeled explicitly.
| Failed edge | Remaining records if all three bought | Path through all sites | Still connected? |
|---|---|---|---|
| A-B | A-C 2; B-C 1 | A-C-B | Yes |
| A-C | A-B 2; B-C 1 | A-B-C | Yes |
| B-C | A-B 2; A-C 2 | B-A-C | Yes |
For a recommendation, report the purchased edge set, its total in stated units, and what must remain connected. Then distinguish mathematical alternatives from evidence about real sites. A missing candidate cable might be physically impossible, merely unobserved, or omitted because the survey was incomplete. Those interpretations affect whether the computed minimum is relevant. Redundant connectivity, shortest travel, and a staged installation plan need their own constraints or objectives. The tree result is useful precisely when connecting all modeled sites at minimum tree cost is the actual requirement, rather than a substitute for another requirement the calculation never represented.
All three edges of a triangle cost 1. How many minimum spanning trees exist? Is any particular edge required in all of them?
A tree needs two of the three edges.
| Selected edges | Total cost |
|---|---|
| A-B and A-C | 2 |
| A-B and B-C | 2 |
| A-C and B-C | 2 |
There are three MSTs, each omitting a different edge and costing 2. No individual edge is in every MST. A deterministic tie-breaker selects one valid tree but does not establish uniqueness.
A designer chooses a five-vertex spanning tree and claims that any single cable can fail without disconnecting sites. What refutes that claim?
How many alternate paths does a tree have?
| Design property | Tree result |
|---|---|
| Connected initially | Yes |
| Selected edges for five vertices | 4 |
| Survives every single selected-edge loss | No |
A tree has exactly one path between each pair of vertices. Every selected edge is a bridge, so deleting any cable edge splits the tree. A design with single-edge redundancy needs additional connections and a different optimization requirement.
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Cut arguments, Kruskal's algorithm, ties, negative weights, and minimum spanning forests.