A spanning tree of a graph on n vertices is a subset of n - 1 edges that form a tree. For example, the spanning trees of the cycle graph C_4, diamond graph, and complete graph K_4 are illustrated above. The number of nonidentical spanning trees of a graph G is equal to any cofactor of the degree matrix of G minus the adjacency matrix of G. This result is known as the matrix tree theorem. A tree contains a unique spanning tree, a cycle graph C_n contains n spanning trees, and a complete graph K_n contains n^(n - 2) spanning trees. A count of the spanning trees τ of a graph can be found using the command NumberOfSpanningTrees[g] in the Wolfram Language package Combinatoricaˋ .

detour matrix | Dijkstra's algorithm | Kruskal's algorithm | matrix tree theorem | maximum spanning tree | minimum spanning tree | shortest path problem | taxicab metric | tree