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 τ(G) 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.

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