The Central Idea
Start with a connected graph that may contain cycles.
A spanning tree is a subgraph that:
- contains every vertex of the original graph;
- is connected;
- contains no cycles.
Therefore,
\[ \boxed{\text{spanning tree}=\text{tree containing all vertices of }G}. \]What Does “Spanning” Mean?
The word spanning means that the subgraph reaches the full vertex set of the original graph.
If
\[ G=(V,E), \]and \(T\) is a spanning tree of \(G\), then
\[ \boxed{V(T)=V(G)}. \]The spanning tree may use fewer edges, but it does not omit any vertex.
A First Example
Consider the connected graph
\[ V=\{a,b,c,d\} \]with
\[ E= \bigl\{ \{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\} \bigr\}. \]The graph contains cycles, so it is not itself a tree.
One spanning tree is obtained using
\[ \boxed{ \{\{a,b\},\{b,c\},\{c,d\}\} }. \]Graph and Spanning Tree
A Spanning Tree Is a Subgraph
A spanning tree uses only vertices and edges already present in the original graph.
If \(T\) is a spanning tree of \(G\), then
\[ V(T)=V(G) \]and
\[ E(T)\subseteq E(G). \]No new edge may be invented.
Spanning Trees Exist Exactly for Connected Graphs
Every connected finite undirected graph has at least one spanning tree.
A disconnected graph cannot have a spanning tree because no subgraph using only its existing edges can connect vertices that lie in different components.
Therefore,
\[ \boxed{G\text{ has a spanning tree}\iff G\text{ is connected}}. \]A Tree Is Its Own Spanning Tree
If the original graph is already a tree, then it contains no redundant edges.
Its only spanning tree is the graph itself.
Removing any edge would disconnect it.
Spanning Trees Have \(n-1\) Edges
Since every spanning tree is a tree, a spanning tree on \(n\) vertices has exactly
\[ \boxed{n-1} \]edges.
Thus, if the original graph has
\[ |V|=n, \]then every spanning tree has
\[ |E(T)|=n-1. \]Example: Edge Count
Any spanning tree of a connected graph with \(12\) vertices must contain
\[ 12-1=11 \]edges.
\[ \boxed{11\text{ edges}}. \]Removing Cycle Edges
One way to construct a spanning tree is to begin with the connected graph and repeatedly remove edges from cycles.
If an edge belongs to a cycle, removing that edge does not immediately disconnect the graph because another route through the cycle still joins its endpoints.
The Cycle-Removal Method
Starting with a connected graph:
- Find a cycle.
- Remove one edge from that cycle.
- Check that the graph remains connected.
- Repeat until no cycle remains.
The final graph is connected and acyclic, so it is a spanning tree.
Why Cycle Removal Works
An edge on a cycle is redundant for connectivity.
If
\[ a,b,c,a \]forms a cycle, then removing \(\{a,b\}\) still leaves the alternate route
\[ a,c,b. \]Connectivity can therefore survive the deletion.
Building Up from Vertices
A spanning tree can also be built by adding edges instead of deleting them.
Start with all vertices and no edges. Add edges that connect previously separated parts of the graph, while refusing any edge that would create a cycle.
Continue until all vertices lie in one connected structure.
The Build-Up Method
- Keep every vertex of the original graph.
- Begin with no selected edges.
- Add an available edge that joins two currently disconnected pieces.
- Do not add an edge that creates a cycle.
- Stop when all vertices are connected.
The result has \(n-1\) edges and is a spanning tree.
Many Graphs Have Many Spanning Trees
A connected graph with cycles may admit several different spanning trees.
Different choices of cycle edges to remove can produce different tree structures while preserving the full vertex set.
A spanning tree is therefore usually not unique.
Example: Multiple Spanning Trees
Consider a triangle with vertices
\[ a,b,c. \]Its edge set is
\[ \{\{a,b\},\{b,c\},\{a,c\}\}. \]Removing any one edge produces a spanning tree.
Therefore the triangle has three spanning trees.
Bridges
A bridge is an edge whose removal increases the number of connected components of a graph.
In a connected graph, removing a bridge disconnects the graph.
Bridges are therefore essential for connectivity.
Every Bridge Must Appear in Every Spanning Tree
Suppose \(e\) is a bridge of a connected graph.
If a spanning tree omitted \(e\), the vertices separated by deleting \(e\) could not remain connected.
Therefore,
\[ \boxed{\text{every bridge belongs to every spanning tree}}. \]Cycle Edges Need Not Be Essential
An edge that lies on a cycle is not a bridge.
It may be omitted from at least some spanning trees because another path connects its endpoints through the rest of the cycle.
Spanning Trees Preserve Reachability
A spanning tree removes redundant edges but preserves the ability to reach every vertex from every other vertex.
The available routes may change, but connectivity remains.
Spanning Trees Remove Redundant Routes
In the original graph, two vertices may have several different connecting paths.
In a spanning tree, every pair of vertices has exactly one path.
The spanning tree therefore removes route redundancy while retaining connectivity.
Weighted Graphs and Spanning Trees
If the original graph is weighted, every spanning tree inherits the weights of the edges it keeps.
The total weight of a spanning tree is commonly defined as
\[ \boxed{ w(T)=\sum_{e\in E(T)}w(e) }. \]Minimum Spanning Trees
A minimum spanning tree, or MST, is a spanning tree whose total edge weight is as small as possible.
If \(\mathcal{T}\) is the set of all spanning trees of a weighted connected graph, then an MST satisfies
\[ \boxed{ w(T_{\min})=\min_{T\in\mathcal{T}}w(T) }. \]Example: Comparing Spanning Trees
Suppose one spanning tree has edge weights
\[ 3,\qquad4,\qquad8, \]giving total weight
\[ 3+4+8=15. \]Another has weights
\[ 2,\qquad4,\qquad5, \]giving
\[ 2+4+5=11. \]Among these two trees, the second has the smaller total weight.
Minimum Does Not Mean Fewest Edges
Every spanning tree on the same \(n\)-vertex graph already has exactly
\[ n-1 \]edges.
A minimum spanning tree minimizes the sum of edge weights, not the number of selected edges.
Minimum Spanning Trees Need Not Be Unique
A weighted graph may have more than one spanning tree with the same minimum total weight.
Therefore, the phrase “a minimum spanning tree” does not always identify a unique tree.
Distinct Edge Weights and Uniqueness
If every edge weight in a connected graph is distinct, then its minimum spanning tree is unique.
Repeated weights may still lead to a unique MST, but uniqueness is no longer guaranteed.
Spanning versus Shortest-Path Trees
A minimum spanning tree and a shortest-path tree solve different problems.
A minimum spanning tree minimizes the total weight of the selected network.
A shortest-path tree from a chosen source preserves shortest routes from that source to the other vertices.
The two trees need not be the same.
Network Design Interpretation
Suppose vertices represent sites that must all be connected and edge weights represent installation costs.
A spanning tree gives a network connecting every site with no cycle.
A minimum spanning tree gives such a network with the smallest total modeled installation cost.
Applications of Spanning Trees
Spanning trees appear in many settings, including:
- telecommunication design;
- electrical distribution;
- road and rail planning;
- computer-network protocols;
- clustering and data analysis;
- image processing;
- circuit design;
- approximation algorithms;
- hierarchical organization of networks.
Spanning Forests
If the original graph is disconnected, no spanning tree exists.
Instead, we may construct a spanning forest: a forest that includes every vertex and contains a spanning tree for each connected component.
Edge Count in a Spanning Forest
Suppose a graph has \(n\) vertices and \(k\) connected components.
A spanning forest contains
\[ \boxed{n-k} \]edges.
Each component contributes one fewer edge than its number of vertices.
Example: Spanning Forest Edge Count
A graph has \(10\) vertices and \(3\) connected components.
Any spanning forest contains
\[ 10-3=7 \]edges.
\[ \boxed{7}. \]Common Error: Omitting a Vertex
A tree contained inside a graph is not automatically a spanning tree.
To be spanning, it must include
\[ \boxed{\text{every vertex of the original graph}}. \]Common Error: Keeping a Cycle
A connected subgraph containing every vertex is not a spanning tree if it still contains a cycle.
A spanning tree must be both spanning and acyclic.
Common Error: Removing a Bridge
Removing a bridge disconnects the graph.
Therefore a bridge cannot simply be discarded while building a spanning tree.
Common Error: Using an Edge Not in the Original Graph
A spanning tree is a subgraph.
Its edges must satisfy
\[ E(T)\subseteq E(G). \]Inventing a shortcut edge produces a different graph rather than a spanning tree of the original one.
Common Error: Assuming Every Graph Has a Spanning Tree
Only connected graphs have spanning trees.
Disconnected graphs instead have spanning forests.
Common Error: Confusing MST with Shortest Route
A minimum spanning tree minimizes total network weight.
It does not necessarily give the shortest possible route between every pair of vertices.
A Reliable Procedure for Finding a Spanning Tree
- Confirm that the original graph is connected.
- Keep every vertex.
- Choose edges from the original graph only.
- Maintain connectivity.
- Remove or avoid edges that create cycles.
- Stop when exactly \(|V|-1\) edges remain.
- Verify that the result is connected and acyclic.
A Reliable Procedure for Checking a Proposed Spanning Tree
- Check that every original vertex is included.
- Check that every selected edge belongs to the original graph.
- Check that the selected subgraph is connected.
- Check that no cycle remains.
- For a finite \(n\)-vertex graph, confirm that the tree has \(n-1\) edges.
Example: Full Spanning-Tree Workflow
Suppose
\[ V=\{a,b,c,d,e\} \]and
\[ E= \bigl\{ \{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\},\{d,e\} \bigr\}. \]The graph is connected and contains cycles.
Select
\[ \{a,b\},\{b,c\},\{c,d\},\{d,e\}. \]These four edges connect all five vertices and form no cycle.
Since
\[ 4=5-1, \]the selected subgraph is a spanning tree.
Practice 1: Definition
What three conditions must a spanning tree satisfy relative to its original graph?
Practice 2: Edge Count
How many edges must a spanning tree of a connected graph with \(20\) vertices contain?
Practice 3: Existence
A graph has two connected components.
Can it have a spanning tree?
Practice 4: Triangle
A triangle graph has three vertices and three edges.
How many edges does each spanning tree of the triangle contain?
Practice 5: Bridge
If an edge is a bridge of a connected graph, must it appear in every spanning tree?
Practice 6: Cycle Removal
Why can one edge from a cycle often be removed without disconnecting a connected graph?
Practice 7: Total Weight
A spanning tree uses edges with weights
\[ 3,\qquad5,\qquad6,\qquad2. \]Find its total weight.
Practice 8: Minimum Spanning Tree
One spanning tree has total weight \(18\), another has total weight \(14\), and a third has total weight \(16\).
Which is minimum among these three?
Practice 9: Spanning Forest
A graph has \(14\) vertices and \(4\) connected components.
How many edges does a spanning forest contain?
Practice 10: Identify the Error
A student selects a connected subgraph containing all \(7\) vertices of a graph and \(7\) edges, then calls it a spanning tree.
Explain the problem.
Practice Answers
Practice 1
A spanning tree must:
- contain every vertex of the original graph;
- be connected;
- contain no cycle.
Practice 2
A tree on \(20\) vertices has
\[ 20-1=19 \]edges.
\[ \boxed{19}. \]Practice 3
No. A graph must be connected to have a spanning tree.
\[ \boxed{\text{No spanning tree exists.}} \]Practice 4
A spanning tree on \(3\) vertices has
\[ 3-1=2 \]edges.
\[ \boxed{2}. \]Practice 5
Yes. Removing the bridge would separate the graph into different components.
\[ \boxed{\text{Every bridge must appear in every spanning tree.}} \]Practice 6
The remaining edges of the cycle still provide an alternate path between the endpoints of the removed edge.
Therefore connectivity can remain intact.
Practice 7
Add the edge weights:
\[ 3+5+6+2=16. \] \[ \boxed{16}. \]Practice 8
The smallest listed total is
\[ \boxed{14}. \]Practice 9
A spanning forest on \(n\) vertices with \(k\) components has
\[ n-k \]edges.
\[ 14-4=10. \] \[ \boxed{10}. \]Practice 10
A spanning tree on \(7\) vertices must have exactly
\[ 7-1=6 \]edges.
A connected graph with \(7\) vertices and \(7\) edges must contain at least one cycle.
\[ \boxed{\text{The proposed subgraph is not a tree.}} \]What to Remember
- A spanning tree is a tree containing every vertex of the original graph.
- A graph has a spanning tree exactly when it is connected.
- A spanning tree of an \(n\)-vertex graph has \(n-1\) edges.
- Cycle edges can often be removed while preserving connectivity.
- Every bridge must appear in every spanning tree.
- A connected graph may have many different spanning trees.
- A minimum spanning tree minimizes the total selected edge weight.
- A minimum spanning tree is not the same as a shortest-path tree.
- A disconnected graph has a spanning forest rather than a spanning tree.
- A spanning forest with \(n\) vertices and \(k\) components has \(n-k\) edges.
Where We Go Next
Spanning trees show how to preserve full connectivity while removing cycles. Other graph problems impose a different requirement: use every edge, or visit every vertex, under tightly controlled route conditions.
The next lesson, Eulerian and Hamiltonian Problems, studies these two major families of traversal questions.