The Nash-Williams-Tutte theorem states that a graph contains edge-disjoint spanning treesiff every partition of its vertex
set into
nonempty sets has at least edges joining different
parts (Nash-Williams 1961, Tutte 1961). For a simple
graph on vertices of minimum
vertex degree
satisfying this criterion with , Lee et al. (2026)
proved that all
spanning trees can be chosen to have graph
diameter
and
internal vertices. Both bounds hold simultaneously
with absolute constants independent of .
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. Algorithms10, 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.Lee, P.-H.; Lin, P.-T.; Tsai, M.-T.; and Wu, T.-A. "A
Low-Diameter Nash-Williams-Tutte Theorem." 3 Nov 2026. https://arxiv.org/abs/2611.05043v1.Nash-Williams,
C. St. J. A. "Edge-Disjoint Spanning Trees of Finite Graphs."
J. London Math. Soc.36, 445-450, 1961. https://doi.org/10.1112/jlms/s1-36.1.445.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.Tutte,
W. T. "On the Problem of Decomposing a Graph into Connected Factors." J. London Math. Soc.36,
221-230, 1961. https://doi.org/10.1112/jlms/s1-36.1.221.West,
D. B. Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
with at least one vertex is a spanning
subgraph that is a tree. It has 
edges, where 
is the vertex count of 
(Skiena 1990, p. 227). For example,
the spanning trees of the cycle
graph 
, diamond graph,
and complete graph 
are illustrated above.
of nonidentical spanning trees of a graph 
is equal to any cofactor
of the Laplacian matrix of 
, 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 
contains 
spanning trees, and a complete
graph 
contains 
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).
is an edge
of 
that is not a graph
loop, then
denotes deletion of the edge 
, and 
denotes its edge
contraction, retaining any resulting multiple edges
(West 2000, Alikhani and Ghanbari 2024).
is the Tutte polynomial.
edge-disjoint spanning trees iff every partition of its vertex
set into 
nonempty sets has at least 
edges joining different
parts (Nash-Williams 1961, Tutte 1961). For a simple
graph on 
vertices of minimum
vertex degree 
satisfying this criterion with 
, Lee et al. (2026)
proved that all 
spanning trees can be chosen to have graph
diameter 
and 
internal vertices. Both bounds hold simultaneously
with absolute constants independent of 
.
Connected Factors." J. London Math. Soc. 36,
221-230, 1961.