Course contentsShow
← Mathematics
Lesson 2672 of 3,12153. Graph TheoryFree lesson

Spanning Trees of a Graph

Define spanning trees as subgraphs containing all vertices with minimal edges to maintain connectivity.

Spanning Trees of a Graph

You'll learn: How to extract a minimal tree structure from any connected graph that reaches every vertex.


What Is a Spanning Tree?

Imagine you have a city map with many roads connecting various neighborhoods, but you want to identify the minimum number of roads needed to ensure every neighborhood stays connected—no isolated areas, but also no unnecessary detours or loops. That's exactly what a spanning tree does for a graph.

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

  1. Contains all vertices from the original graph
  2. Forms a tree (connected and acyclic)
  3. Uses the fewest edges necessary to maintain connectivity

Since it's a tree with n vertices, it must have exactly n - 1 edges—no more, no less.

Why "Spanning" and "Minimal"?

The term "spanning" means the tree "spans" across all vertices—nobody gets left out. "Minimal" refers to the edge count: you cannot remove even one more edge without disconnecting the graph, and you cannot add any edge without creating a cycle (which would violate the tree property).

Example

Consider a complete graph K₄ with 4 vertices fully connected (6 edges total). Any spanning tree of K₄ must include all 4 vertices but use only 3 edges, arranged to avoid cycles. There are actually 16 different spanning trees of K₄—each represents a different minimal way to keep all vertices connected.

Applications

Spanning trees are fundamental in network design (minimizing cable costs), circuit design, and algorithms like finding shortest paths or organizing data hierarchically.


Key Takeaway: A spanning tree is a minimal subgraph containing all vertices and exactly n - 1 edges that maintains full connectivity without cycles.