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:

  1. is connected and has no cycles.
  2. Any two vertices of are joined by exactly one path.
  3. is minimally connected: it is connected, and removing any edge disconnects it.
  4. is maximally acyclic: it has no cycles, and adding any edge between existing vertices creates a cycle.
  5. is connected and has edges.
  6. 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 .