Spanning trees and minimum spanning trees
Every site must be linked to every other, and every possible link has a price. Which links should be built so that everything is connected at the least total cost?
Where you are 10 in Introductory graph theory
When you reach for it
A set of sites must all be joined: huts by groomed trails, buildings by cable, tanks by pipe. Each possible link has a weight, in miles or dollars, as in Weighted and directed graphs, and you want the cheapest set of links in which every site can reach every other. With positive weights the cheapest such set has no cycle, since deleting one edge of a cycle keeps everything connected and lowers the total. So it is a tree that reaches every vertex: a minimum spanning tree.
Trying every tree is hopeless: by Cayley’s formula (Trees, Result 11) the complete graph on 15 sites has 15^{13} \approx 1.9 \times 10^{15} spanning trees. Kruskal’s and Prim’s methods look at each edge about once. This is the cheapest network; the cheapest route is Finding a shortest path.
The procedure
Two days. Day 1: spanning trees and Kruskal’s method (Examples 1 to 3). Day 2: why it is right, Prim’s method, uniqueness and ties (Examples 4 to 6).
Day 1: spanning trees and Kruskal’s method
Graphs are finite and simple, with the trees, components and results of Trees and the weights of Weighted and directed graphs. Let G = (V, E) have n vertices.
- A spanning tree of G is a set T \subseteq E of edges such that the graph (V, T), which has every vertex of G, is a tree. By Result 3 of Trees, \lvert T \rvert = n - 1.
- For a set H of edges, w(H) is the sum of w(e) over e \in H. A minimum spanning tree is a spanning tree T with w(T) \le w(T') for every spanning tree T' of G.
- For an edge e \notin T and an edge f \in T, T + e - f is T with e added and f removed.
Theorem 1 (spanning trees exist). A graph has a spanning tree exactly when it is connected.
Proof. A spanning tree joins every two vertices by a path, so a graph that contains one is connected. Conversely, let G be connected. Removing cycle edges: while there is a cycle, delete one of its edges. This keeps the graph connected (the fact in the proof of Result 7 of Trees) and ends with no cycle. Growing a tree: start with one vertex and no edges. While the tree misses a vertex y, take x in the tree; a path from x to y starts inside the tree and ends outside, so one of its edges uv has u inside and v outside. Adding v and uv keeps the tree connected and makes no cycle, since v then has degree 1 and every vertex of a cycle has degree at least 2. Each round adds a vertex, so the tree ends with all of V. \square
Different choices give different spanning trees. Those of K_n are the labeled trees on its vertices, n^{n-2} of them. Kirchhoff’s matrix-tree theorem counts any graph’s spanning trees with a determinant; here small graphs are counted by listing (Example 1).
Kruskal’s method. List the edges by weight, lightest first, with ties in any order. Keep a set F of edges, empty at the start. Go down the list and keep each edge unless it closes a cycle with the edges already kept; stop when \lvert F \rvert = n - 1. Whether an edge closes a cycle is read off the pieces (components) of F:
Lemma (closing a cycle). Let F be a forest and uv \notin F an edge. Then F + uv has a cycle exactly when u and v lie in the same component of F.
Proof. If they do, that component is a tree with a path from u to v, of length at least 2 since uv \notin F, and the path with uv is a cycle. If F + uv has a cycle, it uses uv, since F has none, and the rest of it is a path from v to u in F. \square
So a kept edge merges two components into one, and a skipped edge has both ends in one component. Components only ever merge.
Theorem 2 (Kruskal’s method gives a spanning tree). For a connected graph, Kruskal’s method keeps n - 1 edges, and they form a spanning tree.
Proof. The kept set F never has a cycle. Suppose the list ran out with \lvert F \rvert < n - 1. Then (V, F) is a forest with c \ge 2 components (Result 4 of Trees). Let C be one; as G is connected, some edge uv has u \in C and v \notin C. At the end u and v lie in different components, so they did when uv was examined, and uv was kept by the lemma; then u and v lie in one component, a contradiction. So F reaches n - 1 edges with no cycle, and is a spanning tree by Result 7 of Trees. \square
That this tree is a cheapest one is Theorem 4, on Day 2.
Day 2: why the cheapest crossing edge is safe
Let S be a set of vertices with S \ne \varnothing and S \ne V. An edge crosses S when exactly one of its ends lies in S.
Theorem 3 (the cut property). Let G be a connected weighted graph and F a set of edges that lies inside some minimum spanning tree. Let S be a set of vertices, neither empty nor all of V, such that no edge of F crosses S, and let e be an edge of least weight among the edges crossing S. Then F + e lies inside some minimum spanning tree. In particular (F = \varnothing), a cheapest edge across any split of the vertices lies in some minimum spanning tree.
Proof. Let T be a minimum spanning tree with F \subseteq T. If e \in T we are done. Otherwise write e = uv with u \in S, v \notin S. By Result 6 of Trees, T + e has exactly one cycle: e with the path P from u to v in T. The path starts in S and ends outside it, so some edge f of P crosses S, and f \ne e. Deleting f, an edge on a cycle, keeps T + e connected, and T' = T + e - f has n - 1 edges, so it is a spanning tree (Result 7). As e is a cheapest edge crossing S, w(e) \le w(f) and
So T' is a minimum spanning tree too. It contains e, and it contains F, because the one edge removed, f, crosses S and no edge of F does. \square
The swap of f for e is the exchange argument.
Theorem 4 (Kruskal’s method is correct). Kruskal’s method returns a minimum spanning tree.
Proof. By induction on the number of kept edges, F always lies inside some minimum spanning tree. At the start F = \varnothing, and a minimum spanning tree exists, since G has at least one spanning tree (Theorem 1) and finitely many. Suppose F lies inside one, and the method keeps e = uv next. Let S be the vertex set of the component of F containing u. Then v \notin S by the lemma, so e crosses S, and no edge of F crosses S, which is a whole component. An edge crossing S listed before e was skipped (it is not in F), so its ends were in one component then and still are, which a crossing edge’s ends are not. So every edge crossing S weighs at least w(e), and Theorem 3 puts F + e inside a minimum spanning tree. At the end F is a spanning tree inside a minimum spanning tree T^*, and both have n - 1 edges, so F = T^*. \square
Prim’s method. Choose a start vertex r; the tree is r alone. Each round, add a cheapest edge with exactly one end in the tree, together with that new end, until the tree has every vertex.
Theorem 5 (Prim’s method is correct). For a connected graph and any start r, Prim’s method returns a minimum spanning tree.
Proof. By the growing proof of Theorem 1, a crossing edge exists until the tree spans, and the tree stays a tree. By induction the chosen edges F lie inside a minimum spanning tree: with S the tree’s vertex set, no edge of F crosses S, and the added edge is a cheapest one crossing S, so Theorem 3 applies. The end is as in Theorem 4. \square
Unlike Finding a shortest path, Prim’s method ranks an outside vertex by one edge, not a whole route.
Theorem 6 (distinct weights give one tree). If the edges of a connected graph have pairwise different weights, it has exactly one minimum spanning tree.
Proof. By contradiction. Suppose T_1 \ne T_2 are both minimum. Both have n - 1 edges, so some edges lie in exactly one of them; let e be the lightest such edge, say e \in T_1, e \notin T_2. The graph T_2 + e has one cycle C, and C has an edge f \notin T_1, or C would be a cycle in T_1. So f \in T_2, f \notin T_1, f \ne e, and by the choice of e and distinct weights w(f) > w(e). Then T_2 + e - f is a spanning tree, as in Theorem 3, of weight w(T_2) + w(e) - w(f) < w(T_2), a contradiction. \square
With ties there can be several minimum spanning trees (Example 5). Greed works here because of the cut property; for a cheapest Hamiltonian cycle (Hamiltonian paths and cycles) nothing like it holds, and greed can lose (Example 6).
Worked examples
Day 1: listing the spanning trees of a small graph
The house graph of Figure 1 has vertices a, b, c, d, e and edges ab, bc, cd, da, ae, be. Count its spanning trees.
With 5 vertices a spanning tree has 4 edges, and 4 edges on 5 vertices form a tree exactly when they hold no cycle (Result 7 of Trees). So a spanning tree is what is left after leaving out 2 of the 6 edges: \binom{6}{2} = 15 pairs to test. The cycles are the triangle (a, b, e, a), the square (a, b, c, d, a) and (a, e, b, c, d, a), which has 5 edges and cannot fit in 4. The kept edges hold no cycle exactly when the pair left out takes an edge from the triangle and an edge from the square.
The edge ab lies in both, so ab with any other edge works: 5 pairs. Without ab, take one of ae, be and one of bc, cd, da: 2 \cdot 3 = 6 pairs. The house has 5 + 6 = 11 spanning trees. Check: the other 4 pairs fail, \{ae, be\} keeping the square and \{bc, cd\}, \{bc, da\}, \{cd, da\} keeping the triangle, and 11 + 4 = 15.
Day 1: Kruskal’s method on a trail map
Taavetti’s crew grooms ski trails between seven warming huts A to G (Figure 2, in miles), just enough for every hut to be reached from every other. Which trails, for the fewest miles?
A cheapest connecting set has no cycle, so the answer is a minimum spanning tree with 7 - 1 = 6 trails. Take the trails lightest first; the last column lists the pieces of the kept trails with more than one hut.
| Trail | Miles | Kept? | Pieces afterward |
|---|---|---|---|
| EF | 2 | yes | \{E, F\} |
| CD | 3 | yes | \{C, D\}, \{E, F\} |
| AC | 4 | yes | \{A, C, D\}, \{E, F\} |
| DE | 5 | yes | \{A, C, D, E, F\} |
| BC | 6 | yes | \{A, \ldots, F\} |
| AB | 7 | no | the same |
| CE | 8 | no | the same |
| BD | 9 | no | the same |
| FG | 10 | yes | all seven |
A skipped trail has both ends in one piece: AB would close (A, B, C, A), CE would close (C, D, E, C), BD would close (B, C, D, B). After six trails the method stops; DF and EG are never examined. Groom EF, CD, AC, DE, BC, FG: 2 + 3 + 4 + 5 + 6 + 10 = 30 miles of the 77 on the map. Theorem 4 will show none is shorter.
Day 1: checking the method against a full list
Oyelade lays fiber-optic cable between five farm buildings placed as in the house graph. Costs, in hundreds of dollars, are ab 4, bc 7, cd 6, da 3, ae 2, be 5 (Figure 3). Find the cheapest network by Kruskal’s method and confirm it against all 11 spanning trees of Example 1.
Lightest first: ae (2) is kept, da (3) is kept, and ab (4) is kept, joining \{a, d, e\} to b. Then be (5) is skipped, since b and e are in one piece and it would close (a, b, e, a). Last, cd (6) is kept, as c was alone. Four edges: the tree \{ae, da, ab, cd\} costs 2 + 3 + 4 + 6 = 15, that is \$1{,}500.
All six cables cost 27, and a spanning tree costs 27 minus the pair left out, so the cheapest tree leaves out the costliest allowed pair. The 11 allowed pairs of Example 1 cost 11, 10, 7, 6, 9 (with ab) and 12, 11, 8, 9, 8, 5 (without). The largest, 12, is only \{be, bc\}, leaving Kruskal’s tree at 27 - 12 = 15: the only cheapest network. The pair \{bc, cd\} costs 13 but is not allowed, as it keeps the triangle and cuts c off.
Day 2: Prim’s method on the trail map
Run Prim’s method on Figure 2 from hut A.
SolutionEach round adds the lightest trail crossing the set of huts already in the tree, safe by Theorem 5; the last column is the runner-up.
| Round | Added | Next lightest crossing |
|---|---|---|
| 1 | AC 4 | AB 7 |
| 2 | CD 3 | BC 6 |
| 3 | DE 5 | BC 6 |
| 4 | EF 2 | BC 6 |
| 5 | BC 6 | AB 7 |
| 6 | FG 10 | EG 12 |
A trail drops out once both ends are inside: CE when E joins. These are the trails of Example 2 in another order, 30 miles. The eleven weights are all different, so by Theorem 6 this is the only minimum spanning tree, and Prim’s method from any hut finds it.
Day 2: ties and several minimum trees
A ranch joins five water tanks p, q, r, s, t by pipe (Figure 4), costs in hundreds of dollars: pq 2, qr 2, pr 2, st 3, rs 4, rt 4, qs 6. Find every minimum spanning tree.
A spanning tree has 4 edges and holds at most two of pq, qr, pr, since all three form a cycle. The other edges cost 3, 4, 4, 6. Two triangle edges and two others cost at least 2 + 2 + 3 + 4 = 11; one triangle edge and three others at least 2 + 3 + 4 + 4 = 13; no triangle edge leaves p unreached. So a tree costing 11 is minimum, and it must hold two triangle edges, st, and one of rs, rt, since 3 and a 4 are the only two of 3, 4, 4, 6 adding to 7. Each such set is a spanning tree: the two triangle edges join p, q, r, the edge st joins s, t, and the 4 joins the groups. There are 3 \cdot 2 = 6 minimum spanning trees, each \$1{,}100.
Kruskal’s method finds one, depending on the tie order: listing pq, qr, pr and rs before rt gives the tree of Figure 4. The proof of Theorem 6 breaks exactly at w(f) > w(e).
Day 2: greed fails for the cheapest tour
Taavetti checks four huts W, X, Y, Z on snowshoes, starting and ending at W and visiting each hut once. The trails are WX 1, XY 2, YZ 3, ZW 10, WY 4, XZ 4 miles (Figure 5). If he always walks to the nearest hut not yet visited, is his loop the shortest?
From W the nearest hut is X (1, against 4 and 10); from X it is Y (2, against 4); then Z, the only one left, and back along ZW. The loop (W, X, Y, Z, W) is 1 + 2 + 3 + 10 = 16 miles. The graph is K_4, with \displaystyle \frac{(4-1)!}{2} = 3 Hamiltonian cycles (Hamiltonian paths and cycles, Result 2): (W, X, Y, Z, W) is 16, (W, X, Z, Y, W) is 1 + 4 + 3 + 4 = 12, and (W, Y, X, Z, W) is 4 + 2 + 4 + 10 = 20. No: the shortest loop is 12. Taking trails lightest first, skipping any that would give a hut three trails or close a loop early, keeps WX, XY, YZ and is forced onto ZW: 16 again. Swapping one edge of such a loop for another never gives such a loop again, so there is no exchange argument to lean on.
Boundaries
- Connected graphs. A disconnected graph has no spanning tree (Theorem 1).
- Undirected edges. For directed graphs the cheapest arcs reaching every vertex from a root is a different problem, not treated here.
- Any real weights. Theorems 2 to 6 only compare weights, so zero and negative weights are allowed, and a maximum spanning tree is a minimum one for -w. But “the cheapest connected network is a tree” needs positive weights: with a negative weight an extra link lowers the cost.
- Ties. Equal weights can give several minimum spanning trees, all of one weight.
- A network, not a route. A tree path need not be a cheapest route (Exercise 21).
Where this goes next
The exchange behind the cut property defines the structures called matroids, where taking the best safe element first is always right. The cheapest Hamiltonian cycle has no known fast method, and minimum spanning trees give it lower bounds (Exercise 20).
Exercises
Day 1: counting spanning trees
- How many spanning trees does the cycle C_7 have? How many does K_5 have?
- Two triangles share exactly one vertex, giving 5 vertices and 6 edges. How many spanning trees does this graph have?
- The graph on a, b, c, d has edges ab, bc, cd, da, ac. How many spanning trees does it have?
Day 1: Kruskal’s method
- Six pumping stations P, Q, R, S, T, U may be joined by pipes of these lengths in miles: PQ 8, PR 5, QR 4, QS 7, RS 9, RT 11, ST 3, SU 2, TU 10. Find a minimum spanning tree by Kruskal’s method, and its length.
- A rockslide closes trail EF in Figure 2. Find the minimum spanning tree of what is left and how many more miles it needs.
- In Figure 3 the cable bc drops to 3. Find the cheapest network and its cost.
Day 1: reasoning
- Prove that a connected graph has exactly one spanning tree exactly when it is a tree.
- A connected graph has n vertices and n edges. Prove that it has exactly one cycle and that its number of spanning trees is the length of that cycle.
- Prove that if Kruskal’s method skips an edge uv, then u and v are joined by a path of kept edges, each weighing at most w(uv).
Day 2: Prim’s method, ties and greed
- Run Prim’s method on the pipes of Exercise 4 from U, giving the pipes in the order added.
- Run Prim’s method on Figure 2 from hut G, giving the trails in the order added.
- The square abcd has sides ab, bc, cd, da of weight 1 and both diagonals ac, bd of weight 2. How many minimum spanning trees does it have, and what do they weigh?
- Find a maximum spanning tree of the pipes of Exercise 4 and its length, and say why Kruskal’s method run heaviest first finds one.
- In K_4 on a, b, c, d the weights are ab 1, bc 2, cd 5, da 6, ac 4, bd 3. Find the tour from a that always moves to the nearest unvisited vertex, and the cheapest Hamiltonian cycle.
Day 2: reasoning
- Prove that adding the same number c to every weight does not change which spanning trees are minimum.
- Prove that if e is lighter than every other edge of G, then every minimum spanning tree contains e.
- Prove the cycle property: if an edge e is heavier than every other edge of some cycle, then no minimum spanning tree contains e.
- In Figure 2 the trail BD is rerouted, and its length becomes x > 0, every other trail unchanged. Prove that some minimum spanning tree uses BD exactly when x \le 6.
- Let the weights be pairwise different. Prove that for every vertex v the lightest edge at v lies in the minimum spanning tree.
- Let every weight be positive and n \ge 3. Prove that every Hamiltonian cycle weighs more than a minimum spanning tree.
- Refute with a counterexample: “the path between two vertices in a minimum spanning tree is always a cheapest route between them.”
Answers
- 7: a spanning tree keeps 6 of the 7 edges, and leaving out any one leaves a path. K_5 has 5^{3} = 125 by Cayley’s formula.
- 9. A tree keeps 4 edges, so 2 are left out. Each triangle must lose an edge or keep a cycle, so each loses exactly one, and the triangles are the only cycles: 3 \cdot 3 = 9.
- 8. Leave out 2 of the 5 edges, \binom{5}{2} = 10 pairs. The kept 3 edges fail only when they are a triangle: \{ab, bc, ac\} (leaving out cd, da) or \{ac, cd, da\} (leaving out ab, bc). So 10 - 2 = 8.
- Kept in order: SU 2, ST 3, QR 4, PR 5, QS 7, which joins \{P, Q, R\} to \{S, T, U\}. Five edges, so stop: 2 + 3 + 4 + 5 + 7 = 21 miles.
- Kept: CD 3, AC 4, DE 5, BC 6; skipped AB, CE, BD; kept FG 10 and DF 11, which joins \{F, G\} to the rest. Total 3 + 4 + 5 + 6 + 10 + 11 = 39 miles, 9 more.
- ae 2, then bc 3 and da 3 in either order, then ab 4 joining \{a, d, e\} to \{b, c\}: the tree \{ae, bc, da, ab\} costs 2 + 3 + 3 + 4 = 12, that is \$1{,}200.
- A tree’s only spanning tree is itself, with all n - 1 edges. Otherwise take a spanning tree T and e \notin T; the cycle of T + e has an edge f \in T, and T + e - f \ne T.
- A spanning tree T leaves out one edge e, and T + e = G has exactly one cycle C (Result 6). Leaving out an edge gives a tree exactly when the rest stays connected (Result 7): true on C, false for an edge uv on no cycle, as a path from u to v avoiding uv would close a cycle.
- At the skip, u and v were in one component of the kept edges (lemma), joined by a path of kept edges, each listed earlier and so weighing at most w(uv).
- SU 2, ST 3, QS 7, QR 4, PR 5: the tree of Exercise 4, 21 miles.
- FG 10, EF 2, DE 5, CD 3, AC 4, BC 6, the tree of Example 2.
- 4 trees of weight 3. Every spanning tree has 3 edges of weight at least 1, so weight 3 means three sides, and any three of the four sides form a path.
- RT 11, TU 10, RS 9, PQ 8, QS 7, total 45 miles. A maximum tree for w is a minimum tree for -w, whose list runs heaviest first (Boundaries).
- Nearest neighbor: (a, b, c, d, a), 1 + 2 + 5 + 6 = 14. The cycles weigh 14, (a, b, d, c, a) 1 + 3 + 5 + 4 = 13 and (a, c, b, d, a) 4 + 2 + 3 + 6 = 15: the cheapest is 13.
- Every spanning tree has n - 1 edges, so its weight rises by exactly (n - 1)c. Every tree moves by the same amount, so the trees of least weight are the same.
- If a minimum spanning tree T lacked e, then T + e has a cycle, which has an edge f \ne e in T with w(f) > w(e). Then T + e - f is a spanning tree lighter than T, a contradiction.
- If a minimum spanning tree T held e = uv, then T - e has two components, at u and at v (Result 6). The rest of the cycle runs from u to v, so one of its edges f joins them, and T - e + f is a spanning tree lighter by w(e) - w(f) > 0.
- If x > 6, BD is the heaviest edge of the cycle (B, C, D, B), so no minimum tree uses it (Exercise 17). If x \le 6, list BD before BC: the other trails at B weigh 6 and 7, so B is alone when BD is examined, and Kruskal’s method keeps it (Theorem 4).
- Take S = \{v\}. The edges crossing S are the edges at v, so by Theorem 3 the lightest lies in some minimum spanning tree, which by Theorem 6 is the only one.
- Removing an edge e leaves a spanning path, a spanning tree, so the cycle weighs more than a spanning tree by w(e) > 0.
- A triangle x, y, z with xy 2, yz 2, xz 3. The only minimum spanning tree is \{xy, yz\}, weight 4 (the others weigh 5). Its path from x to z weighs 4, but the edge xz weighs 3.