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).

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.

classOEISspanning tree counts
Andrásfai graphA1931261, 5, 392, 130691, 116268789, 217138318913, ...
antiprism graphA193127X, X, 384, 3528, 30250, 248832, 1989806, ...
Apollonian networkA19312816, 1445, 487350000, 6820689973308563232421875, ...
barbell graphA193129X, X, 9, 256, 15625, 1679616, 282475249, ...
book graph S_(n+1) square P_nA006234X, X, 54, 189, 648, 2187, 7290, 24057, ...
cocktail party graph K_(n×2)A1931300, 4, 384, 82944, 32768000, 20736000000, ...
complete graph K_nA0002721, 1, 3, 16, 125, 1296, 16807, 262144, ...
complete bipartite graph K_(n,n)A0680871, 4, 81, 4096, 390625, 60466176, 13841287201, ...
complete tripartite graph K_(n,n,n)A1931313, 384, 419904, 1610612736, 15000000000000, ...
crossed prism graphA193132X, X, X, 384, X, 9216, X, 196608, X, 3932160, ...
crown graphA193133X, X, 6, 384, 40500, 6635520, 1575656250, ...
cube-connected cycle graphA000000X, X, 32400000, 5068660643117137920000, ...
cycle graph C_nA000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, ...
fan graphA000000X, 8, 216, 13056, 1409375, ...
fiveleaper graphA000000X, X, X, X, 0, 0, 0, 331898989520947048842445518274560, ...
folded cube graphA193134X, 1, 16, 4096, 2147483648, 14167099448608935641088, ...
gear graphA129743X, X, 50, 192, 722, 2700, 10082, 37632, 140450, 524172
grid graph P_n square P_nA0073411, 4, 192, 100352, 557568000, 32565539635200, ...
grid graph P_n square P_n square P_nA0717631, 384, 8193540096000, ...
halved cube graphA1931351, 1, 16, 82944, 126806761930752, ...
Hanoi graphA1931363, 135, 20503125, 119709242282867431640625, ...
helm graphA004146X, X, 16, 45, 121, 320, 841, 2205, 5776, 15125, ...
hypercube graph Q_nA0062371, 4, 384, 42467328, 20776019874734407680, ...
king graphA000000X, 16, 17745, 1064918960, 3271331573452800, ...
knight graphA000000X, 0, 0, 144000, 136323072000, 5398085382092881920, ...
ladder graph P_2 square P_nA0013531, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, ...
Möbius ladder M_nA020871X, X, 81, 392, 1815, 8112, 35301, 150544, 632043, ...
Mycielski graphA1931481, 1, 5, 38642, 3568248132106250, ...
odd graphA1931491, 3, 2000, 336140000000000000, ...
pan graphA000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, ...
path graph P_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
permutation star graph A1931501, 1, 6, 162000000, ...
prism graphA006235X, X, 75, 384, 1805, 8100, 35287, 150528, ...
queen graphA000000X, 16, 541205, 54711160897536, ...
rook graphA193137X, 4, 11664, 34359738368, 156250000000000000000, ...
stacked book graphA000000X, X, 56, 1, 35733190625,...
star graph S_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
sun graphA193152X, X, 54, 600, 9610, 202800, 5329646, 167968080, ...
sunlet graph C_n circledot K_1A000027X, X, 3, 4, 5, 6, 7, 8, 9, 10
tetrahedral Johnson graphA000000X, X, X, X, X, 96745881600000000, ...
triangular graphA193154X, 1, 3, 384, 2048000, 518400000000, ...
web graphA006235X, X, 75, 384, 1805, 8100, 35287, 150528, ...
wheel graph W_nA004146X, X, X, 16, 45, 121, 320, 841, 2205, ...

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).

classclosed form
antiprism graph2/5n(phi^(4n)+phi^(-4n)-2)
book graph S_(n+1) square P_n3^(n-1)(n+3)
cocktail party graph K_(n×2)4^(n-1)(n-1)^nn^(n-2)
complete graph K_nn^((n-2))
complete bipartite graph K_(n,n)n^(2n-2)
complete tripartite graph K_(n,n,n)3·8^(n-1)n^(3n-2)
crossed prism graph3n·2^(2n-3)
cycle graph C_nn
grid graph P_n square P_n(2^(n^2-1))/(n^2)product_(i,j=0; i,j not both 0)^(n-1)[2-cos((pii)/n)-cos((pij)/n)]
grid graph P_n square P_n square P_n(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)]
helm graphL_(2n)-2
hypercube graph Q_n2^(2^n-1-n)product_(k=1)^(n)k^((n; k))
ladder graph P_2 square P_n((2+sqrt(3))^n-(2-sqrt(3))^n)/(2sqrt(3))
=(sinh(ncosh^(-1)2))/(sqrt(3))
=U_(n+1)(2)
=C_(n-1)^((1))(2)
Möbius ladder M_n1/2n[2+(2+sqrt(3))^n+(2-sqrt(3))^n]
pan graphn
path graph P_n1
prism graph Y_n1/2n[(2-sqrt(3))^n+(2+sqrt(3))^n-2]
star graph S_n1
sunlet graph C_n circledot K_1n
wheel graph W_nL_(2(n-1))-2

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

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.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.Zheng

Referenced on Wolfram|Alpha

Spanning Tree

Cite this as:

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

Subject classifications