图 的生成树，该图有 
个顶点，是 
条边的子集，这些边构成一棵树 (Skiena 1990, p. 227)。例如，圈图 
、钻石图 和 完全图 
的生成树如上图所示。
一个图 
的非同构生成树的数量 
等于 
的度矩阵 减去 
的邻接矩阵 的任何余子式 (Skiena 1990, p. 235)。这个结果被称为矩阵树定理。一棵树 包含唯一的生成树，一个圈图 
包含 
个生成树，一个完全图 
包含 
个生成树 (Trent 1954; Skiena 1990, p. 236)。
如果 
是一张图 
的一条边，那么
 |
其中，图 
中边 
的边收缩 表示为 
(West 2000, Alikhani and Ghanbari 2024)。
可以使用以下命令找到图的生成树计数：NumberOfSpanningTrees[g]，在 Wolfram 语言 包中Combinatorica`。对于连通图，它也由下式给出：
 |
其中 
是 Tutte 多项式。
Kruskal 算法 可以用来找到图的最大 或 最小生成树。
下表总结了各种命名图类的生成树数量。
| 类别 | OEIS | 生成树计数 |
| Andrásfai 图 | A193126 | 1, 5, 392, 130691, 116268789, 217138318913, ... |
| 反棱柱图 | A193127 | X, X, 384, 3528, 30250, 248832, 1989806, ... |
| 阿波罗网络 | A193128 | 16, 1445, 487350000, 6820689973308563232421875, ... |
| 哑铃图 | A193129 | X, X, 9, 256, 15625, 1679616, 282475249, ... |
书图  | A006234 | X, X, 54, 189, 648, 2187, 7290, 24057, ... |
鸡尾酒会图  | A193130 | 0, 4, 384, 82944, 32768000, 20736000000, ... |
完全图  | A000272 | 1, 1, 3, 16, 125, 1296, 16807, 262144, ... |
完全二分图  | A068087 | 1, 4, 81, 4096, 390625, 60466176, 13841287201, ... |
完全三部图  | A193131 | 3, 384, 419904, 1610612736, 15000000000000, ... |
| 交叉棱柱图 | A193132 | X, X, X, 384, X, 9216, X, 196608, X, 3932160, ... |
| 冠图 | A193133 | X, X, 6, 384, 40500, 6635520, 1575656250, ... |
| 立方体连接环图 | A000000 | X, X, 32400000, 5068660643117137920000, ... |
圈图  | A000027 | X, X, 3, 4, 5, 6, 7, 8, 9, 10, ... |
| 扇图 | A000000 | X, 8, 216, 13056, 1409375, ... |
| 五步跳马图 | A000000 | X, X, X, X, 0, 0, 0, 331898989520947048842445518274560, ... |
| 折叠立方体图 | A193134 | X, 1, 16, 4096, 2147483648, 14167099448608935641088, ... |
| 齿轮图 | A129743 | X, X, 50, 192, 722, 2700, 10082, 37632, 140450, 524172 |
网格图  | A007341 | 1, 4, 192, 100352, 557568000, 32565539635200, ... |
网格图  | A071763 | 1, 384, 8193540096000, ... |
| 半立方体图 | A193135 | 1, 1, 16, 82944, 126806761930752, ... |
| 汉诺塔图 | A193136 | 3, 135, 20503125, 119709242282867431640625, ... |
| 舵轮图 | A004146 | X, X, 16, 45, 121, 320, 841, 2205, 5776, 15125, ... |
超立方体图  | A006237 | 1, 4, 384, 42467328, 20776019874734407680, ... |
| 国王图 | A000000 | X, 16, 17745, 1064918960, 3271331573452800, ... |
| 骑士图 | A000000 | X, 0, 0, 144000, 136323072000, 5398085382092881920, ... |
梯形图  | A001353 | 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, ... |
莫比乌斯梯形图  | A020871 | X, X, 81, 392, 1815, 8112, 35301, 150544, 632043, ... |
| Mycielski 图 | A193148 | 1, 1, 5, 38642, 3568248132106250, ... |
| 奇图 | A193149 | 1, 3, 2000, 336140000000000000, ... |
| 平底锅图 | A000027 | X, X, 3, 4, 5, 6, 7, 8, 9, 10, ... |
路径图  | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
| 排列星图 | A193150 | 1, 1, 6, 162000000, ... |
| 棱柱图 | A006235 | X, X, 75, 384, 1805, 8100, 35287, 150528, ... |
| 皇后图 | A000000 | X, 16, 541205, 54711160897536, ... |
| 车图 | A193137 | X, 4, 11664, 34359738368, 156250000000000000000, ... |
| 堆叠书图 | A000000 | X, X, 56, 1, 35733190625,... |
星图  | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
| 太阳图 | A193152 | X, X, 54, 600, 9610, 202800, 5329646, 167968080, ... |
日射图  | A000027 | X, X, 3, 4, 5, 6, 7, 8, 9, 10 |
| 四面体约翰逊图 | A000000 | X, X, X, X, X, 96745881600000000, ... |
| 三角形图 | A193154 | X, 1, 3, 384, 2048000, 518400000000, ... |
| 网络图 | A006235 | X, X, 75, 384, 1805, 8100, 35287, 150528, ... |
轮图  | A004146 | X, X, X, 16, 45, 121, 320, 841, 2205, ... |
下表给出了各种命名图类的生成树数量的闭合形式，其中 
是黄金比例，
是卢卡斯数，
是第二类切比雪夫多项式，
是格根鲍尔多项式，
是卢卡斯数。
由 Koshy (2001) 以及 Alikhani 和 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)]](/images/equations/SpanningTree/Inline55.svg)
![(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)]](/images/equations/SpanningTree/Inline57.svg)
![1/2n[2+(2+sqrt(3))^n+(2-sqrt(3))^n]](/images/equations/SpanningTree/Inline67.svg)
![1/2n[(2-sqrt(3))^n+(2+sqrt(3))^n-2]](/images/equations/SpanningTree/Inline71.svg)
