TOPICS
Search

Spanning Tree

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
SpanningTrees

A spanning tree of a finite simple graph G with at least one vertex is a spanning subgraph that is a tree. It has n-1 edges, where n is the vertex count of G (Skiena 1990, p. 227). For example, the spanning trees of the cycle graph C_4, diamond graph, and complete graph K_4 are illustrated above.

The number tau(G) of nonidentical spanning trees of a graph G is equal to any cofactor of the Laplacian matrix of G, the degree matrix minus the adjacency matrix (Skiena 1990, p. 235). 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 (Trent 1954; Skiena 1990, p. 236). The number of spanning trees of a graph is also known as its tree number or graph complexity (Harary and Palmer 1973, p. 268; Kook 2011, p. 417).

If e is an edge of G that is not a graph loop, then

tau(G)=tau(G-e)+tau(G degreese),

where G-e denotes deletion of the edge e, and G degreese denotes its edge contraction, retaining any resulting multiple edges (West 2000, Alikhani and Ghanbari 2024).

For a connected graph, the number of spanning trees is also given by

tau=T(1,1),

where T(x,y) is the Tutte polynomial.

Kruskal's algorithm can be used to find a maximum spanning tree or minimum spanning tree of a graph.

See also

Detour Matrix, Dijkstra's Algorithm, Kruskal's Algorithm, Matrix Tree Theorem, Maximum Spanning Tree, Minimum Spanning Tree, Shortest Path Problem, Spanning Forest, Spanning Subgraph, Taxicab Metric, Thin Tree, Tree, Tree Number, Tree-Weighted Planar Map, Uniform Spanning Tree

Explore with Wolfram|Alpha

References

Alikhani, S. and Ghanbari, N. "Golden Ratio in Graph Theory: A Survey." 9 Jul 2024. https://arxiv.org/abs/2407.15860.Colbourn, C. J.; Day, R. P. J.; and Nel, L. D. "Unranking and Ranking Spanning Trees of a Graph." J. Algorithms 10, 271-286, 1989.Eppstein, D. "Spanning Trees and Spanners." Ch. 9 in Handbook of Computational Geometry (Ed. J.-R. Sack and J. Urrutia). Amsterdam, Netherlands: North-Holland, pp. 425-461, 2000.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973.Kook, W. "Combinatorial Green's Function of a Graph and Applications to Networks." Adv. Appl. Math. 46, 417-423, 2011.Nikolić, S.; Trinajstić, N.; and Mihalić, A. "The Detour Matrix and the Detour Index." Ch. 6 in Topological Indices and Related Descriptors in QSAR and QSPR (Ed. J. Devillers and A. T. Balaban). Amsterdam, Netherlands: Gordon and Breach, pp. 285-286, 2000.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 224-227, 1990.Trent, H. "A Note on the Enumeration and Listing of All Possible Trees in a Connected Linear Graph." Proc. Nat. Acad. Sci. U.S.A. 40, 1004-1007, 1954.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Referenced on Wolfram|Alpha

Spanning Tree

Cite this as:

Weisstein, Eric W. "Spanning Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SpanningTree.html

Subject classifications