A spanning tree of an undirected graph is a subgraph , with , that contains every vertex of and is a Tree. A spanning tree exists if and only if is a connected graph. The Minimum spanning tree is the spanning tree of least total edge weight.
Equivalent definitions
For a graph with vertices, the following are equivalent, so any of them can replace “is a Tree” above:
- is connected and has no cycles.
- Any two vertices of are joined by exactly one path.
- is minimally connected: it is connected, and removing any edge disconnects it.
- is maximally acyclic: it has no cycles, and adding any edge between existing vertices creates a cycle.
- is connected and has edges.
- has no cycles and has edges.
Consequently, for a connected graph , the following are equivalent descriptions of a spanning tree :
- a minimal connected spanning subgraph of (remove edges lying on cycles until none remain);
- a maximal acyclic subgraph of (add edges of that create no cycle until none can be added);
- a spanning subgraph with edges and no cycles.
The number of spanning trees of is given by Kirchhoff’s matrix tree theorem: it equals any cofactor of the graph Laplacian , where is the degree matrix and the adjacency matrix. For the complete graph this gives Cayley’s formula .