Spanning Tree
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).
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).
A count of the spanning trees of a graph can be found using the command NumberOfSpanningTrees [g] in the Wolfram Language package Combinatorica` . For a connected graph, it 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 or minimum spanning tree of graph.
The following table summarizes the numbers of spanning trees for various named classes of graphs.
Closed forms for the numbers of spanning trees for various named classes of graphs are given in the table below, where phi is the golden ratio, L_n is a Lucas number, U_n(x) is a Chebyshev polynomial of the second kind, C_n^((m))(x) is a Gegenbauer polynomial, and L_n is a Lucas number. tau(W_n) was considered by Koshy (2001) and Alikhani and Ghanbari (2024).
![画像:(2^(n^2-1))/(n^2)product_(i,j=0; i,j not both 0)^(n-1)[2-cos((pii)/n)-cos((pij)/n)]](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/SpanningTree/Inline55.svg){kind=link}
![画像:(2^(n^3-1))/(n^3)product_(i,j,k=0; i,j,k not all 0)^(n-1)[3-cos((pii)/n)-cos((pij)/n)-cos((pik)/n)]](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/SpanningTree/Inline57.svg){kind=link}
See also
Detour Matrix, Dijkstra's Algorithm, Kruskal's Algorithm, Matrix Tree Theorem, Maximum Spanning Tree, Minimum Spanning Tree, Shortest Path Problem, Taxicab Metric, TreeExplore with Wolfram|Alpha
More things to try:
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.Koshy, T. Fibonacci and Lucas Numbers With Applications. New York: Wiley-Interscience, 2001.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 A. T. and 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.Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A000272/M3072, A001353/M3499, A0041463867, A006234/M3496, A006235/M4849, A006237/M3725, A007341, A020871, A068087, A071763, A129743, A193126, A193127, A193128, A193129, A193130, A193131, A193132, A193133, A193134, A193135, A193136, A193137, A193148, A193149, A193150, A193151, A193152, A193153, A193154 in "The On-Line Encyclopedia of Integer Sequences."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.ZhengReferenced on Wolfram|Alpha
Spanning TreeCite this as:
Weisstein, Eric W. "Spanning Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SpanningTree.html