Spanning Tree and Spanning Forest: Definitions, Construction and Worked Examples

A spanning tree, a minimum spanning tree, and a spanning forest answer different questions, yet their names make them easy to mix up. That confusion can turn a one-line edge-count question into guesswork. A connected graph on n vertices carries a spanning tree of exactly n - 1 edges, while a graph that falls into c components carries no spanning tree at all, only a spanning forest of n - c edges.

Spanning tree and spanning forest definitions

For finite, undirected graphs, a spanning subgraph of G = (V, E) retains every vertex but may retain only some edges.

If G is connected, a spanning tree is a connected, acyclic spanning subgraph. It covers every vertex and provides a path between every pair.

If a graph has c connected components, a spanning forest is the union of one spanning tree from each component. An isolated vertex is a one-vertex tree with zero edges. A disconnected graph has no single spanning tree, but it does have a spanning forest.

The immediate edge-count test is:

• A spanning tree on n vertices has n - 1 edges.

• A spanning forest on n vertices with c components has n - c edges.

Both counts come from one fact. Start with the n vertices and no edges, so there are n separate components. An edge joining two different components lowers the component count by exactly one, and an edge inside a component only closes a cycle. Falling from n components to a single one therefore costs n - 1 edges, and stopping at c components costs n - c.

For n = 9, a connected spanning tree has 9 - 1 = 8 edges. If the graph instead has c = 3 components, its spanning forest has 9 - 3 = 6 edges.

Construct a spanning tree step by step

Consider the connected graph

V = {A, B, C, D, E, F}

E = {AB, AC, BC, BD, CE, DE, DF, EF}

Process the edges in exactly that order. Keep an edge only when it joins two parts that are not already connected.

1. Keep AB.

2. Keep AC. The selected edges now connect A, B, and C.

3. Reject BC. A path already joins B to C through A, so BC would close the cycle A-B-C-A.

4. Keep BD. This introduces D without creating a cycle.

5. Keep CE. This introduces E.

6. Reject DE. The selected edges already contain the path D-B-A-C-E, so adding DE would create a cycle.

7. Keep DF. This introduces the final vertex, F.

8. Reject EF. The path E-C-A-B-D-F already joins its endpoints.

The result is T = {AB, AC, BD, CE, DF}. All six vertices appear, and every vertex is reachable from A. It has five edges, with 5 = 6 - 1. Since each kept edge joined separate parts, the construction is acyclic.

Rejected edges are not bad: another order can produce another valid tree. For this T, adding BC creates exactly the cycle A-B-C-A. Removing BD separates {D, F} from {A, B, C, E}.

Build a spanning forest when the graph is disconnected

Now take a second graph H:

V = {A, B, C, D, E, F}

E = {AB, AC, BC, DE, DF, EF}

It has two triangle components, C1 = {A, B, C} and C2 = {D, E, F}. Thus n = 6 and c = 2.

Choose F = {AB, AC, DE, DF}. Here {AB, AC} spans the first component and {DE, DF} spans the second. The forest has 4 = 6 - 2 edges. Adding an edge between the components would change the original graph, not select a spanning subgraph of H.

Three reliable construction methods

Traversal method

Run BFS or DFS and record each edge that first discovers a vertex. In a connected graph, these edges form a spanning tree. The start and neighbour order can change the result, as the BFS, DFS and shortest-path guide explains.

Edge-addition method

Start with isolated vertices. Add an edge only when it joins separate components, stopping at n - 1 edges for a connected graph. Disjoint-set union is the standard way to track those components as they merge.

Cycle-deletion method

Start with all edges. Remove cycle edges while preserving connectivity, and stop when no cycle remains. Removing a bridge instead would disconnect the graph.

Spanning tree versus minimum spanning tree

A spanning tree needs vertex coverage, connectivity, and no cycles. A minimum spanning tree, or MST, additionally needs edge weights and minimises their total. Every MST is a spanning tree, but an arbitrary tree need not be minimum.

Assign these weights to the first graph. (The 1 to 5 labels in that figure recorded the order edges were kept, not weights.)

w(AB)=2, w(AC)=3, w(BC)=1, w(BD)=4, w(CE)=5, w(DE)=2, w(DF)=6, w(EF)=1.

Our constructed tree weighs

w(T) = 2 + 3 + 4 + 5 + 6 = 20.

It is valid, but its five-edge count does not prove minimum weight. Taking the cheapest edges that never close a cycle gives {BC, EF, AB, DE, BD}, which is also a spanning tree and weighs 1 + 1 + 2 + 2 + 4 = 10. Our tree costs exactly twice that. Nothing structural separates the two: both hold five edges and reach all six vertices, and only the weight total tells them apart. Use the minimum spanning tree guide for Kruskal's and Prim's algorithms when a question asks for the cheapest weighted tree.

What spanning structures are used for

A spanning tree can be a loop-free network backbone. Its n - 1 links keep n connected locations reachable. This minimises selected links, not necessarily cable cost, distance, or latency.

It also supports broadcast or traversal without cycles. In our tree, the unique path from F to E is F-D-B-A-C-E. A forest provides this structure component by component.

Euler paths, Hamiltonian cycles, and graph colouring ask different questions about the same graph. A spanning tree does not guarantee any of those properties.

Common traps and the correct checks

Trap 1: treating n - 1 edges as sufficient. On V = {1, 2, 3, 4, 5}, {12, 23, 31, 45} has four edges. Yet the first three form a cycle and {45} is separate. Check spanning, connectivity, and acyclicity together.

Trap 2: forcing a disconnected graph into one tree. For n = 10 with component sizes 5, 4, 1, the forest has (5 - 1) + (4 - 1) + (1 - 1) = 4 + 3 + 0 = 7 edges. It matches n - c = 10 - 3 = 7.

Trap 3: assuming the first traversal tree is unique or minimum. Different neighbour orders can produce different BFS or DFS trees. Minimum total weight is a separate optimisation condition.

How exams test spanning structures

Four reusable concept checks are worth knowing:

• A connected graph on 17 vertices needs 17 - 1 = 16 tree edges.

• A graph on 17 vertices with 4 components needs 17 - 4 = 13 forest edges.

• Adding one non-tree edge to a spanning tree creates exactly one cycle.

• Removing any tree edge creates exactly two components.

Work one through. Is {AB, BC, BD, DE, EF} a spanning tree of the main graph? All five edges belong to E. From A, reach B, then C and D, then E, then F, so it covers all six vertices and is connected. Five edges holding six connected vertices together leave no room for a cycle, so it is acyclic. It is a valid spanning tree, and a different one from T. The count settled it only after coverage and connectivity were checked.

The short version

A connected graph has a spanning tree with n - 1 edges. A graph with c components has a spanning forest with n - c edges. Weights matter only when the word minimum appears.

Once the definitions feel settled, work through the previous-year questions on spanning trees and spanning forests and check every answer against coverage, connectivity and acyclicity together. GATE Guidance by Sanchit Sir carries the full graph-theory sequence, and Engineering Mathematics is the wider mathematics track around it.