Spanning Trees

Introduction

A spanning tree is a subgraph that connects all vertices with minimum edges (no cycles). It’s fundamental in network design and graph theory.

Definition

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

1. Includes all vertices of G
2. Is a tree (connected and acyclic)
3. Is a subgraph of G

Example 1: Basic Spanning Tree

Original Graph:

1 --- 2
|\ /| |
| X | |
|/ \| |
3 --- 4

One Possible Spanning Tree:

1 --- 2
|     |
3     4

• All 4 vertices included ✓
• 3 edges (n-1 for n=4) ✓
• No cycles ✓
• Connected ✓

Properties of Spanning Trees

Property 1: Edge Count

A spanning tree of a graph with n vertices has exactly (n-1) edges.

Example: Graph with 10 vertices → spanning tree has 9 edges

Property 2: Uniqueness

A graph can have multiple spanning trees.

Example:

Graph:      ST 1:       ST 2:
1 - 2       1 - 2       1   2
|\ /|       |           | /
| X |       |           |/
|/ \|       3   4       3 - 4
3 - 4

Property 3: Minimum Connectivity

Spanning tree has the minimum number of edges to keep graph connected.

Property 4: Adding Edge

Adding any edge to a spanning tree creates exactly one cycle.

Property 5: Removing Edge

Removing any edge from a spanning tree disconnects it.

Number of Spanning Trees

Cayley’s Formula (Complete Graph)

Complete graph Kₙ has n^(n-2) spanning trees.

Examples:

• K₃: 3^(3-2) = 3^1 = 3 spanning trees
• K₄: 4^(4-2) = 4^2 = 16 spanning trees
• K₅: 5^(5-2) = 5^3 = 125 spanning trees

Example: All Spanning Trees of K₃

K₃ (Complete triangle):

  1
 / \
2---3

Three spanning trees:

ST 1:    ST 2:    ST 3:
  1        1        1
 /          \      / \
2   3      2 3    2   3

Minimum Spanning Tree (MST)

Definition

For a weighted graph, a minimum spanning tree is a spanning tree with minimum total edge weight.

Example:

Weighted Graph:
    1
  5/ \3
  /   \
 2--2--3

MST: Use edges {1,3} and {2,3} with total weight 3+2 = 5

Finding Spanning Trees

Method 1: Depth-First Search (DFS)

Algorithm:

1. Start at any vertex
2. Perform DFS
3. Include edges used in DFS traversal
4. These edges form a spanning tree

Example:

Graph:
1 - 2 - 3
|   |   |
4 - 5 - 6

DFS from 1: Visit 1→2→3→6→5→4
Spanning Tree edges: {1,2}, {2,3}, {3,6}, {6,5}, {5,4}

Time Complexity: O(V + E)

Method 2: Breadth-First Search (BFS)

Algorithm:

1. Start at any vertex
2. Perform BFS (level-order)
3. Include edges used in BFS
4. These edges form a spanning tree

Example:

Graph:
1 - 2 - 3
|   |   |
4 - 5 - 6

BFS from 1:
Level 0: 1
Level 1: 2, 4 (neighbors of 1)
Level 2: 3, 5 (neighbors of 2, 4)
Level 3: 6 (neighbor of 3 or 5)

ST edges: {1,2}, {1,4}, {2,3}, {2,5}, {3,6}

Time Complexity: O(V + E)

Applications of Spanning Trees

1. Network Design

Problem: Connect n computers with minimum cable

Solution: Find spanning tree of network graph

Example:

• 5 offices to connect
• Spanning tree uses 4 connections (minimum)

2. Circuit Design

Problem: Connect components on circuit board

Solution: Minimum spanning tree minimizes wire length

3. Cluster Analysis

Problem: Group similar data points

Solution: Build spanning tree, remove longest edges

4. Image Segmentation

Problem: Divide image into regions

Solution: Build graph of pixels, find spanning tree

5. Network Routing

Problem: Broadcast messages efficiently

Solution: Use spanning tree to avoid loops

6. Approximation Algorithms

Problem: Traveling Salesman Problem

Solution: MST gives 2-approximation

Spanning Tree Algorithms

1. Kruskal’s Algorithm (for MST)

Approach:

• Sort edges by weight
• Add edges if they don’t create cycle
• Use Union-Find data structure

Time: O(E log E)

2. Prim’s Algorithm (for MST)

Approach:

• Start with one vertex
• Grow tree by adding minimum weight edge
• Use priority queue

Time: O(E log V) with binary heap

3. Borůvka’s Algorithm

Approach:

• For each component, add cheapest outgoing edge
• Repeat until one component

Time: O(E log V)

Example: Finding All Spanning Trees

Graph:

1 - 2
|   |
3 - 4

Edges: {1,2}, {2,4}, {4,3}, {3,1}

Possible Spanning Trees:

ST 1: {1,2}, {2,4}, {4,3}

1 - 2
    |
3 - 4

ST 2: {1,2}, {2,4}, {3,1}

1 - 2
|   |
3   4

ST 3: {1,2}, {4,3}, {3,1}

1 - 2
|
3 - 4

ST 4: {2,4}, {4,3}, {3,1}

1   2
|   |
3 - 4

Total: 4 spanning trees

Spanning Forest

Definition

For a disconnected graph, a spanning forest is a collection of spanning trees, one for each connected component.

Example:

Graph:
1 - 2    5 - 6

Spanning Forest:
Tree 1: {1,2}
Tree 2: {5,6}

Cut Property

Theorem

For any cut (S, V-S) that separates the graph, the minimum weight edge crossing the cut is in some MST.

Use: Justifies greedy algorithms like Kruskal’s and Prim’s

Cycle Property

Theorem

For any cycle in the graph, the maximum weight edge in that cycle is NOT in any MST (unless there are duplicate weights).

Use: Can eliminate expensive edges early

Matrix-Tree Theorem

Kirchhoff’s Theorem

Number of spanning trees can be computed using:

• Laplacian matrix of graph
• Determinant of cofactor

Complex but powerful for counting!

Key Points for Exams

1. Spanning tree: connects all vertices with (n-1) edges
2. No cycles in spanning tree
3. n vertices → (n-1) edges always
4. Graph can have multiple spanning trees
5. Kₙ has n^(n-2) spanning trees
6. DFS/BFS can find spanning tree
7. MST: spanning tree with minimum total weight
8. Adding edge to ST creates exactly one cycle
9. Removing edge from ST disconnects it
10. Spanning forest: for disconnected graphs

Practice Problems

1. How many edges in spanning tree of graph with 15 vertices?

2. How many spanning trees does K₄ have?

3. Draw all spanning trees of:

1 - 2
 \ /
  3

4. Can a disconnected graph have a spanning tree? Explain.

5. If graph has 10 vertices and 20 edges, how many edges are NOT in a spanning tree?

6. Use DFS to find spanning tree starting from vertex 1:

1 - 2 - 3
|   |   |
4 - 5 - 6

7. True or False: Every spanning tree of K₅ has exactly 4 edges.

8. Find minimum spanning tree for:

    1
  2/ \3
  /   \
 2--4--3

9. If we add an edge to a spanning tree, what happens?

10. Can a tree be its own spanning tree? Explain.