A spanning tree of a graph is a tree that includes all vertices of the graph and is a subgraph of the original graph. A spanning tree contains the minimum number of edges needed to connect all vertices without creating any cycles.

Properties

A spanning tree of a graph with vertices has exactly edges.

Key Characteristics:

• Contains all vertices - Every vertex from the original graph appears in the spanning tree
• No cycles - The spanning tree is acyclic, making it a tree
• Connected - There exists a path between any two vertices
• Minimal connectivity - Removing any edge disconnects the spanning tree
• Maximal acyclicity - Adding any edge creates a cycle

Existence

A graph has a spanning tree if and only if the graph is connected.

For a connected graph with vertices:

• If the graph has exactly edges, it is itself a tree and its own spanning tree
• If the graph has more than edges, multiple spanning trees may exist

Construction

A spanning tree can be constructed from a connected graph using several methods:

Breadth-First Search (BFS)

1. Start at any vertex
2. Visit all adjacent vertices level by level
3. Include edges that lead to unvisited vertices
4. Continue until all vertices are visited

Depth-First Search (DFS)

1. Start at any vertex
2. Explore as far as possible along each branch
3. Include edges that lead to unvisited vertices
4. Backtrack when no unvisited adjacent vertices remain

Edge Removal

1. Start with the original connected graph
2. Identify any cycle
3. Remove one edge from the cycle
4. Repeat until no cycles remain