Spanning trees

Definition

A spanning tree is a subgraph of a connected, undirected graph that includes all the vertices with the minimum possible number of edges. It contains no cycles and connects all the vertices together.

5 Must Know Facts For Your Next Test

1. A spanning tree for a graph with \(n\) vertices has exactly \(n-1\) edges.
2. There can be multiple spanning trees for a single graph.
3. Removing any edge from a spanning tree will disconnect it.
4. The Minimum Spanning Tree (MST) is a type of spanning tree that minimizes the total edge weight.
5. Kruskal's and Prim's algorithms are commonly used to find Minimum Spanning Trees.

Review Questions

• What is the relationship between the number of vertices and edges in a spanning tree?
• How does removing an edge from a spanning tree affect its structure?
• What algorithms can be used to find a Minimum Spanning Tree?

Related terms

Graph: A set of vertices connected by edges, which can be directed or undirected.

Cycle:

A path in a graph that starts and ends at the same vertex without repeating any edges or vertices.

Minimum Spanning Tree (MST): A spanning tree where the sum of its edge weights is minimized.