Spanning Trees

Discrete Math · Axiom Academy

Understanding trees as connected acyclic graphs and how every connected graph contains a spanning tree. Connected: There exists a path between every pair of vertices Acyclic: No path leads back to itself (no loops) Let's visualize the difference between a tree and graphs that aren't trees: One of the most important properties of trees is that they have exactly n-1 edges when they have n vertices . This isn't a coincidence—it's a fundamental property we can prove! Start with 1 vertex (n=1): 0 edges ✓ To add a new vertex while staying connected and acyclic, we must add exactly 1 edge Each new vertex adds exactly 1 edge Therefore: n vertices → n-1 edges A spanning tree of a connected graph G is a subgraph that: Is a tree (connected and acyclic) Contains a subset of edges from G Every connected graph contains at least one spanning tree. To find one, we can remove edges that create cycles while keeping the graph connected. Here's a simple algorithm to find a spanning tree from any connected graph: Start with the original connected graph G While the graph contains a cycle: Find any cycle in the graph Remove one edge from that cycle What remains is a spanning tree! Watch this process in action as we transform a graph with cycles into a spanning tree: Note: A graph may have multiple spanning trees if there are multiple ways to remove edges. Each valid removal sequence produces a valid spanning tree.

This is the written version of the interactive lesson above. See the full Discrete Math course.