Spanning Tree¶

Definition¶

A spanning tree of a connected undirected network contains every original vertex and a subset of its edges that forms a tree. If the network has $n$ vertices, every spanning tree has $n-1$ edges.

Interpretation¶

A spanning tree keeps all locations connected but removes enough edges to eliminate every cycle. It is a smallest set of edges that still connects everything: with $n$ vertices it always has $n-1$ edges, and different edge selections can produce different spanning trees.

Two copies of the same network with different spanning trees highlighted, one of total length 13 and one of total length 30.

Both highlighted edge sets reach all six vertices with $5$ edges and contain no cycle, so both are spanning trees of the same network. Their total lengths differ a lot: $2+1+5+2+3=13$ for the first and $4+2+10+8+6=30$ for the second. The number of edges is fixed; the total length depends on which edges are chosen.

The word spanning refers to the vertices: every vertex of the original network must belong to the tree, while many edges are left out. The tree $A-C-B$ alone is a tree but not a spanning tree. A spanning tree exists if and only if the network is connected: removing an edge that lies on a cycle never disconnects a network, so a connected network can be thinned out to a spanning tree, while a disconnected one lacks the edges to join its parts.

Comparing total lengths is the minimum spanning tree problem; the first tree in the figure, of length 13, is a minimum one.

Key Results¶

Spanning refers to including all vertices, not all edges.
Adding another original edge to a spanning tree creates a cycle.
The minimum spanning tree problem compares the total lengths of spanning trees.

Examples¶

A network with seven vertices needs six edges in each spanning tree.
The Euclidean example selects $1-7$ $7$ , $1-4$ $4$ , $4-3$ $3$ , $3-6$ $6$ , $6-2$ $2$ , and $6-5$ $5$ .

Prerequisites¶

Tree

Sources¶

OR Modelling · Week 4

Last updated: 20 October 2026 03:02