TOPICS
Search

Spanning Tree

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
SpanningTrees

A spanning tree of a graph on n vertices is a subset of n-1 edges that form a tree (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 degree matrix of G minus the adjacency matrix of G (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 a graph G, then

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

where edge contraction of the edge e in G is denoted G degreese (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, Taxicab Metric, Tree, Tree Number

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