Spanning tree

of a graph $G$

A subgraph of the given graph $G$ which contains all its vertices and which is a tree: connected and without cycles. More generally, a spanning forest of a graph is a subgraph which is a spanning tree for each of the connected components. A spanning forest for a graph with $n$ vertices and $k$ components has $n-k$ edges.

The number of spanning trees of any given connected graph $G$ without loops and without multiple edges can be computed as follows. Let $L$ be the matrix obtained from the adjacency matrix of $G$ by replacing all the signs of the elements by the opposite signs and by replacing the $i$-th entry on the principal diagonal by the valency of the vertex $v_i$. The cofactors of all entries on the principal diagonal of $L$ will then all be equal, and their common value is the number of spanning trees of $G$. Spanning trees are employed, for example, to find independent cycles in an electric circuit.

The number of spanning trees is a special value of the Tutte polynomial of the graph, $T_G(1,1)$.

See Tree for references.