View source for Spanning tree

{{TEX|done}}
''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.