Spanning Trees and Network Skeletons

What This Concept Is

A spanning tree of a connected graph $G$ is a subgraph $T$ that:

• includes every vertex of $G$ (i.e., $V(T) = V(G)$),
• is a tree (connected, acyclic).

So a spanning tree preserves the connectivity of $G$ while stripping away every unnecessary cycle. You can think of it as a network skeleton: the smallest backbone that keeps all vertices reachable from one another.

A connected graph on $n$ vertices has exactly $n - 1$ edges in any spanning tree (by tree characterization). If $G$ has $m$ edges total, then any spanning tree throws out $m - (n-1)$ edges -- precisely the "redundant" ones from the connectivity point of view. Every discarded edge is a non-bridge of the original graph, but some original non-bridges remain in the chosen tree. Every original bridge is retained.

A connected graph typically has many spanning trees. Kirchhoff's Matrix-Tree Theorem gives an exact count: the number of spanning trees of $G$ equals any cofactor of the Laplacian matrix $L = D - A$ (where $D$ is the degree matrix and $A$ the adjacency matrix). For $K_n$, this gives $n^{n-2}$ -- Cayley's formula again.

With edge weights, a minimum spanning tree (MST) is a spanning tree whose total edge weight is minimized. Classical algorithms:

• Kruskal's algorithm: sort edges by weight; greedily add the next edge if it does not form a cycle (uses union-find). $O(m \log m)$.
• Prim's algorithm: grow a tree from a start vertex, repeatedly adding the cheapest edge leaving the current tree (uses a priority queue). $O(m \log n)$ with a binary heap, $O(m + n \log n)$ with a Fibonacci heap.
• Borůvka's algorithm: each component selects its cheapest outgoing edge using a consistent global ordering to break weight ties; process selected edges with cycle checks as components merge. $O(m \log n)$; useful for distributed settings.

The MST is not always unique, but if all edge weights are distinct, it is.

Why It Matters Here

Spanning trees show how larger graphs contain simpler core structure. They also connect directly to algorithmic ideas such as BFS/DFS trees, MSTs, multicast backbone construction, and efficient routing topologies.

This is a major example of how graph theory supports later algorithm design. Many proofs about connected graphs reduce to proofs about trees by choosing a spanning tree and working with its unique paths. The conceptual move -- "extract a skeleton, prove on the skeleton, generalize back" -- recurs throughout algorithms, networking, and distributed systems.

Concrete Examples

Example 1: existence proof. Every connected graph $G$ has a spanning tree.

Constructive proof. Start with $T = G$. While $T$ contains a cycle, pick any cycle edge $e$ and remove it from $T$. The graph $T - e$ remains connected because any path that used $e$ can be rerouted around the rest of the cycle. Continue until no cycles remain. The final $T$ is connected and acyclic -- a spanning tree. $\blacksquare$

Corollary: the cycles are exactly the redundant edges for basic connectivity.

Example 2: Kruskal on a concrete graph. Consider a graph with vertices ${A, B, C, D}$ and weighted edges:

edge	weight
$AB$	1
$BC$	2
$CD$	3
$AD$	4
$AC$	5

Sort by weight: $AB(1), BC(2), CD(3), AD(4), AC(5)$.

• Add $AB$: components ${A,B}, {C}, {D}$.
• Add $BC$: components ${A,B,C}, {D}$.
• Add $CD$: components ${A,B,C,D}$ -- done with $3 = n-1$ edges.

MST weight $= 1 + 2 + 3 = 6$. Edges $AD$ and $AC$ are rejected because they would form cycles.

Example 3: cut property. For any partition of vertices into two nonempty sets $S, \bar S$, the cheapest edge crossing the partition belongs to some MST. This is the cut property and it is the correctness engine behind both Kruskal and Prim.

Proof sketch. Suppose $T$ is an MST not containing the cheapest crossing edge $e = uv$ (with $u \in S, v \in \bar S$). Adding $e$ to $T$ creates a unique cycle; that cycle must contain another edge $e'$ crossing the partition. Since $e$ is cheapest across the cut, $w(e) \le w(e')$. Swap $e$ for $e'$: the new tree has weight $\le w(T)$, so it is also an MST and contains $e$. $\blacksquare$

Common Confusion / Misconceptions

• A spanning tree is any tree inside the graph. No -- it must include every vertex of the graph. A subtree on $k < n$ vertices is not spanning.
• The spanning tree is unique. Usually not. Most graphs have many spanning trees (exponentially many, for dense graphs). Even MSTs can be non-unique if edge weights are not all distinct.
• MST is unique if ties are broken arbitrarily. No -- ties in edge weights can produce genuinely different MSTs with the same total weight. A fixed tie-breaking rule selects a reproducible output but does not prove uniqueness for the original weighted instance.
• MST solves shortest paths. No. MST minimizes total edge weight; shortest-path trees minimize root-to-vertex distance. For most graphs these are different. Example: triangle weights AB=2, BC=2, AC=3. The MST keeps AB and BC, but its A-to-C distance 4 exceeds the original direct distance 3.
• Greedy always wrong. In most optimization settings greedy algorithms are suspect; for MST, greedy is provably optimal (Kruskal and Prim), thanks to the matroid structure of graph forests.

How To Use It

Use spanning trees when you want to:

• prove something about all connected graphs by reducing to trees (pick any spanning tree, prove on it, generalize back).
• extract a minimal connectivity certificate from a dense graph.
• reason about search or traversal structure (BFS and DFS produce spanning trees).
• build a backbone for multicast, broadcast, or reliable communication.
• count spanning trees via Kirchhoff's theorem.

Common strategy:

1. choose or construct a spanning tree $T$ (BFS tree, DFS tree, or MST depending on what you want).
2. identify the $m - (n-1)$ non-tree edges; each closes exactly one fundamental cycle through $T$.
3. prove the claim on $T$, where unique-path reasoning simplifies matters.
4. transfer the conclusion back to $G$ by considering what non-tree edges can do.
5. if weights matter, use MST; apply cut property or cycle property to reason about which edges must / cannot be in the MST.
6. for distributed or parallel settings, compare component-based merging with the communication and synchronization costs of the actual system.
7. always sanity-check on $K_3, K_4$ where spanning trees can be enumerated by hand.

Transfer to the workshop model

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

Check Yourself

1. Why does removing a cycle edge preserve connectivity? Trace an alternative path.
2. Why does every connected graph contain a spanning tree? Give the constructive argument in three sentences.
3. Why are spanning trees useful proof devices even before optimization is introduced?
4. State the cut property of MSTs and justify it informally. What does it imply for Kruskal's correctness?
5. How many spanning trees does $K_4$ have? (Hint: Cayley / Kirchhoff.)
6. Why does Prim build a connected intermediate tree at every step while Kruskal does not?

Mini Drill or Application

Take a connected graph with at least $6$ vertices (you may draw your own), and do:

1. Draw one spanning tree of it. List edges removed.
2. Explain why connectivity was preserved.
3. Produce a different spanning tree of the same graph; verify it has $n-1$ edges.
4. Assign random weights to the edges and compute the MST by hand with Kruskal. Verify by also running Prim.
5. For $K_5$ (complete graph on $5$ vertices), use Cayley's formula to predict the number of spanning trees. Check: $5^{5-2} = 125$.

Read This Only If Stuck

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

What a chosen spanning tree actually discards

Every bridge of the original connected graph lies in every spanning tree. Every discarded edge is a non-bridge of that original graph, but the reverse does not hold: a triangle has no bridges and its tree retains two edges. Moreover, edges individually removable from the original graph may not all be removable together. Re-evaluate connectivity as deletions accumulate.

An MST minimizes total weight, while a shortest-path tree preserves distances from one root. Triangle weights 2,2,3 demonstrate the difference. Tie-breaking selects a reproducible MST without proving uniqueness under the original weights. Transfer: prove the cut exchange argument and P15's route comparison; keep fast implementations and data-structure costs for Semester 2.

After your attempt use practice feedback and model contracts to check the argument.