Split the vertices into two sides. Among the edges with one end on each side, the lightest is in some minimum spanning tree, and if it is strictly lightest it is in every one. That single lemma justifies every edge either algorithm in this module takes. The lab does not quote it: it enumerates every spanning tree of the graph you typed and reads the verdict off the list.
Core ideas
The hard idea is the exchange argument. The two lemmas are two readings of it, and the gap between some and every is where ties live.
Choose any set S of vertices, not empty and not everything. The edges with exactly one end in S are the crossing edges, and the cut property is a statement about the lightest of them. Nothing requires S to be connected, or to be half the graph, or to have anything to do with an algorithm — which is exactly why one lemma covers two algorithms that choose their cuts in completely different ways.
Take a minimum spanning tree that does not contain the lightest crossing edge e. Adding e to it makes exactly one cycle, and that cycle must cross the cut a second time, at some other crossing edge g. Remove g. The result is a spanning tree again, and its weight changed by the weight of e minus the weight of g, which is at most 0. So it is also minimum, and it contains e.
If e is strictly lighter than every other crossing edge then the exchange strictly reduces the weight, which is impossible for a minimum tree, so every minimum tree already contained e. With a tie the exchange is weight-neutral and only produces one tree containing e. The lab measures the difference: on the opening graph, whose weights are all distinct, the lightest crossing edge is in the one minimum tree there is. On a triangle with all three weights equal there are 3 spanning trees, all 3 minimum, and the lightest crossing edge is in 2 of them.
The material
Cuts and crossing edges, the exchange argument, the cycle property as the same picture read backwards, and what the lab enumerates.
A cut of a graph is a partition of its vertices into a non-empty proper subset S and the rest. An edge crosses the cut if exactly one of its ends lies in S. A spanning tree is a subset of the edges that connects every vertex and contains no cycle; on a connected graph with V vertices it has exactly V - 1 edges. A minimum spanning tree is one of least total weight; there may be several.
Let S be one side of a cut of a connected weighted graph, and let e be a crossing edge of least weight. Then some minimum spanning tree contains e. If e is the unique crossing edge of least weight, then every minimum spanning tree contains it.
Let T be a minimum spanning tree with e not in it, and write e as joining x in S to y outside it. T connects x to y, so adding e creates exactly one cycle, consisting of e and the tree path from y back to x.
That tree path starts outside S and ends inside it, so it contains at least one crossing edge; call one of them g. Then T with e added and g removed is connected — removing an edge of a cycle cannot disconnect anything — and has V - 1 edges, so it is a spanning tree.
Its weight is w(T) + w(e) - w(g), and w(e) ≤ w(g) because e is a lightest crossing edge. So the new tree weighs at most w(T), and since T was minimum it weighs exactly w(T) and is minimum too. That gives the first claim. For the second, if e is strictly lightest then w(e) < w(g) and the new tree would weigh strictly less than T, which is impossible — so no minimum tree can have omitted e.
□
The lab is built to make that proof checkable rather than believable. Give it a graph of at most seven vertices and it enumerates every spanning tree, totals each one, and reports how many are minimum and how many of them contain the lightest crossing edge. The verdict comes off the list.
The lab opens on 1-2 4, 1-3 3, 2-3 2, 2-4 5, 3-4 7, 4-5 1, 5-6 6 with S = {1, 2, 3}. Two edges cross: 2-4 at weight 5 and 3-4 at weight 7, so the lightest crossing edge is 2-4. The enumeration finds 8 spanning trees in total, exactly 1 of them minimum, at weight 17; that tree is 1-3, 2-3, 2-4, 4-5, 5-6, and it contains 2-4. Kruskal's method on the same graph also returns 17.
That graph has distinct weights, so the minimum tree is unique and the distinction between some and every collapses. Sweeping every one of the 62 proper cuts of those six vertices, the lightest crossing edge is in a minimum tree every time, and where it is strictly lightest it is in all of them.
Type a triangle with all three weights equal — 1-2 1, 2-3 1, 3-1 1 — and take S = {1}. Two edges cross, tied at weight 1. There are 3 spanning trees, all 3 minimum at weight 2, and each edge is in exactly 2 of them. So the lightest crossing edge is in SOME minimum tree and not in every one, and the panel reports the some-verdict as yes and the every-verdict as no, with the tie count beside it. That is the whole content of the second sentence of the theorem.
If an edge is the unique heaviest edge on some cycle of the graph, then no minimum spanning tree contains it.
The argument is the exchange run backwards: a minimum tree containing that edge, with the edge removed, splits into two pieces, and the rest of the cycle must rejoin them with some strictly lighter edge, giving a lighter tree. The lab prints the per-edge count that settles this. On 1-2 1, 2-3 2, 3-4 3, 4-1 9, 2-4 4 there are 8 spanning trees, 1 of them minimum at weight 6, and two edges appear in none of the minimum trees: 4-1 at weight 9 and 2-4 at weight 4. The second is the interesting one — it is not the heaviest edge in the graph, it is the heaviest on the cycle 2, 3, 4.
It does not say that taking the lightest edge at each vertex builds a tree. On 1-2 1, 2-3 5, 3-4 1, 4-5 6, 5-6 1 that rule selects three edges on six vertices and leaves three separate pieces — the lab reports all three figures. Every one of those three edges is in the minimum tree, which is the cut property doing its job; they are simply not enough of it, because the lemma is about one cut at a time and says nothing about what a family of cuts collectively covers.
And it does not say the lightest edge overall is in every minimum tree, although that happens to be true whenever it is uniquely lightest: take S to be one of its endpoints alone and it is the unique lightest crossing edge of that cut. What makes this worth stating is that the same trick does not extend — the second-lightest edge has no such argument, because the cut that isolates its endpoint may be crossed by the lightest edge as well.
The measured figure and the proved claim, one more time. The panel's numbers — 8 spanning trees, 1 minimum, weight 17, verdict yes — are about the graph on screen and the cut you chose. The theorem is about every graph and every cut, and the enumeration cannot reach it: seven vertices is where the lab stops, and it declines above that rather than running slowly. The exchange argument is what covers the rest.
Interactive
Pick a set; the lightest edge leaving it is in a minimum tree, and the page lists them all to show it
Method
Name the cut first. Every safe edge on this course is safe because of some cut.
The lemma licenses an edge only relative to a cut. “This edge is light, so it is safe” is not an argument; “this edge is the lightest crossing the cut between what I have built and what I have not” is. Both algorithms in this module are a rule for choosing S, and nothing more.
If it is, you are entitled to say every minimum tree contains it, which is the stronger and more useful claim. If it is not, you may only say some minimum tree does — and two implementations may then legitimately return different trees of the same weight.
The two lemmas are complementary: one puts an edge in, one keeps an edge out. When a candidate edge closes a cycle with edges you already have and it is the heaviest on that cycle, it is in no minimum tree at all, which is exactly why one of the two algorithms can discard an edge for ever on first sight.
Below eight vertices the lab lists every spanning tree, so “in every minimum tree” is a fact about a list. Above that it declines. Any claim you carry past the cap is carried by the proof, and it is worth being able to say which of the two you are relying on.
The graph is 1-2 4, 1-3 3, 2-3 2, 2-4 5, 3-4 7, 4-5 1, 5-6 6 and the chosen side is S = {1, 2, 3}. Six vertices, so a spanning tree has five edges.
The edge 3-4, at weight 7, is in four of the eight spanning trees and in none of the minimum ones. That is the cycle property: it is the heaviest edge on the cycle 2, 3, 4 formed with 2-3 and 2-4. The two lemmas are visible in the same list, one putting 2-4 in and the other keeping 3-4 out.
Notice that the verdict does not depend on which cut was chosen. Sweeping all 62 proper subsets of these six vertices, the lightest crossing edge is in a minimum tree every time. The cut is the reader's choice; the conclusion is not.
For a faded rehearsal, change the weight of 3-4 from 7 to 5 and predict what happens to the verdict before running it. The supplied first move is this: the two crossing edges now tie at 5, so the panel's tie count rises to 2 and the strict half of the theorem no longer applies. Say what the number of minimum trees becomes, and whether 2-4 is still in every one of them.
You should be able to state both lemmas, reproduce the exchange argument, identify the crossing edges of a cut you chose, read the verdict off the enumeration, and explain why lightest-at-each-vertex is not a spanning tree even though every edge it picks is safe.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.