Difficulty: Intermediate | Prerequisites: Basic graph theory (vertices, edges, paths, connected graphs)
Spanning trees sit at the intersection of graph theory and optimisation. If you have a network of nodes (cities, computers, people) and connections between them, a spanning tree is the leanest possible sub-network that still keeps everyone reachable. This topic matters because real systems, from telecoms to epidemiology, need efficient ways to connect or trace paths through networks. You should already be comfortable with basic graph vocabulary: vertices, edges, paths, and what it means for a graph to be connected.
A spanning tree of a graph is a connected subgraph that touches every vertex and contains no cycles. Kruskal's Algorithm finds the cheapest spanning tree by sorting edges by weight and adding them one at a time, skipping any edge that would create a cycle. The total cost of a minimum spanning tree is the sum of the weights of its selected edges.
Spanning tree
A subgraph of a connected graph that includes every vertex and is itself a tree (connected, no cycles). In simple terms, it is the minimum "skeleton" of edges needed to keep all vertices linked.
Tree
A connected graph with no cycles. Think of it as a graph where there is exactly one path between any two vertices.
Minimum-cost spanning tree (MST)
A spanning tree whose total edge weight is the smallest possible among all spanning trees of a weighted graph. In simple terms, the cheapest way to connect every node.
Kruskal's Algorithm
A greedy algorithm that builds an MST by repeatedly choosing the lowest-weight edge that does not create a cycle. Think of it as picking the cheapest available cable each time, provided it does not form a loop.
Cycle (circuit)
A path that starts and ends at the same vertex without repeating any edge. In simple terms, a closed loop in the graph.
Connected graph
A graph in which there is a path between every pair of vertices. If any vertex is unreachable from another, the graph is disconnected.
Edge weight (cost)
A numerical value assigned to an edge, representing distance, cost, time, or another quantity. Kruskal's Algorithm uses these weights to decide which edges to select.
A subgraph is a spanning tree of a graph G if and only if it satisfies all three conditions:
It includes every vertex of G.
It is connected (there is a path between any two vertices).
It contains no cycles.
A graph with n vertices will have a spanning tree with exactly n - 1 edges. Any fewer and it is disconnected; any more and it contains a cycle.
Checking whether a subgraph is a spanning tree:
Missing vertex? Not a spanning tree (the subgraph must span the whole graph).
Disconnected component? Not a spanning tree (e.g. edge F-E-I disconnected from C-A-B-D-H means the subgraph is not even a tree).
Contains a cycle? Not a spanning tree (e.g. A-C-D-B-A forms a circuit, which would "crash the network" in a practical setting).
Uses every vertex, is connected, and has no cycle? It is a spanning tree.
A single graph can have many different spanning trees. To find one, start from any vertex and keep adding edges that reach a new vertex without creating a cycle, until all vertices are included.
For a graph with vertices {A, B, C, D, E} and multiple edges between them, you can produce different spanning trees by choosing different subsets of edges, provided each subset connects all five vertices with exactly four edges and no cycle.
Kruskal's Algorithm finds the spanning tree with the lowest total edge weight.
Steps:
Sort all edges by weight, from smallest to largest.
Starting from the smallest, add each edge to your tree, provided it does not form a cycle with the edges already selected.
If an edge would create a cycle, skip it (mark it with an X).
Stop when you have selected n - 1 edges (where n is the number of vertices).
The total cost is the sum of the weights of the selected edges.
Worked example (from the worksheet, Question 4):
Edges sorted by weight: 1, 1, 3, 3, 3, 4, 4, 4, 5, 6, 7, 8, 10
Selected edges (circled): 1, 1, 3, 3, 3, 4, 4, 3, 7, 6 (skipping those that would create cycles).
Total cost: 1 + 4 + 3 + 8 + 3 + 1 + 4 + 3 + 7 + 6 + 4 = 44
The key decision at each step is: "Does adding this edge create a cycle?" If yes, skip. If no, take it.
Social networking ("people you may know"):
Social networks model connections between people as a graph. Tree structures help trace paths of connection: if you follow what the platform suggests (mutual friends, shared surnames, shared regions), the recommendation engine walks a tree of relationships to find people close to you in the network but not yet connected.
Epidemiology (tracing "patient zero"):
When an outbreak occurs, a contact-tracing tree records who infected whom. Starting from the most recent patient, you trace back through contacts: each sick person links to the person who contacted them. Following this chain to its root (the person who "got it from nowhere") identifies the alleged patient zero. The tree structure ensures there is one clear path from any patient back to the source.
Students often think a subgraph that uses most vertices is "close enough" to a spanning tree. It is not. Every single vertex must be included, or it fails the definition.
A connected subgraph with all vertices is sometimes mistaken for a spanning tree even when it contains a cycle. A spanning tree must be acyclic. If you can trace a loop, it is not a tree.
Students sometimes assume Kruskal's Algorithm picks the n - 1 cheapest edges outright. It does not. It picks the cheapest edge that does not create a cycle, which may mean skipping a low-cost edge and taking a higher one later.
Confusing "spanning subgraph" with "spanning tree": a spanning subgraph includes all vertices but may have cycles or extra edges. A spanning tree is specifically a spanning subgraph that is also a tree.
⚠️ You will almost certainly be asked to verify whether a given subgraph is a spanning tree. Memorise the three conditions: all vertices, connected, no cycles.
⚠️ Kruskal's Algorithm questions typically ask you to list the edges in the order you considered them, circle or mark the ones you kept, cross out the ones you rejected (and state why: "creates a cycle"), and compute the total cost.
⚠️ Know the formula: a spanning tree of a graph with n vertices has exactly n - 1 edges.
⚠️ Application questions (social networks, patient zero) test whether you can explain the tree concept in plain English and connect it to real scenarios.
True or False: A spanning tree of a graph with 8 vertices has exactly 7 edges.
True or False: If a subgraph includes every vertex but has a cycle, it can still be a spanning tree.
Fill in the blank: Kruskal's Algorithm adds the next cheapest edge only if it does not create a ______.
True or False: A graph can have more than one valid spanning tree.
True or False: In Kruskal's Algorithm, you must sort edges from largest to smallest.
Answers: 1. True. 2. False (no cycles allowed). 3. cycle. 4. True. 5. False (smallest to largest).
Q: A connected graph has 10 vertices. How many edges does any spanning tree of this graph have?
A: 9 edges (n - 1 = 10 - 1 = 9).
Q: You are running Kruskal's Algorithm and the next cheapest edge has weight 5. It connects two vertices that are already in the same connected component. Do you add it? Why or why not?
A: No. Adding it would create a cycle, which violates the tree property. Skip it and move to the next cheapest edge.
Q: A subgraph of an 8-vertex graph includes all 8 vertices and has 7 edges, but vertex F can only be reached from vertices E and G (not from A, B, C, D, H). Is it a spanning tree?
A: Not necessarily. Having n - 1 edges is necessary but not sufficient. If the subgraph is disconnected (i.e. F-E-G form an isolated component from the rest), it is not a spanning tree. You must also verify connectivity.
Q: Explain how a tree structure can be used to trace the source of a disease outbreak.
A: Model each infected person as a vertex and each transmission event as a directed edge from infector to infected. The resulting tree has one root: the person who was infected first (with no incoming edge from another patient in the tree). Tracing from any recent patient back through parent edges leads to that root, the alleged patient zero.
Q: In Kruskal's Algorithm, what happens if two edges have the same weight?
A: Either can be chosen first. The tie-breaking order does not affect the total cost of the MST (though it may produce a different MST with the same total weight).
Spanning trees connect directly to vertex coloring and chromatic number, which also appear on this worksheet. Both topics use the same underlying graph structures. Spanning trees focus on selecting edges; vertex coloring focuses on assigning labels to vertices. Together they cover two of the most common operations in graph theory.
Kruskal's Algorithm is a classic example of a greedy algorithm, a strategy you will encounter repeatedly in algorithm design courses. The same greedy principle (make the locally optimal choice at each step) applies in Prim's Algorithm (another MST method), Dijkstra's shortest-path algorithm, and Huffman coding.
Spanning trees also underpin network design and reliability problems in operations research and computer science. If you take a networking or optimisation course later, MSTs will reappear.
Spanning tree, minimum spanning tree, MST, Kruskal's Algorithm, Prim's Algorithm, greedy algorithm, graph theory, connected graph, acyclic graph, tree, forest, cycle, circuit, edge weight, cost, network optimisation, contact tracing, patient zero, social network graph, subgraph, CS 101, discrete mathematics, graph traversal