圖 的生成樹，該圖有 
個頂點，是 
條邊的子集，這些邊構成一棵樹 (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)
