关于矩阵树定理推广结论的证明问询——包含指定边或子树的生成树计数

我正在学习组合数学大纲，遇到两个被称为矩阵树定理推广的结论：
G = (V,E) 是无环完全图，U 是 V 的子集。矩阵 $Q^U(G)$ 是从拉普拉斯矩阵 $L(G)$ 中移除对应 U 中顶点的行和列得到的矩阵。

1. 设 $e=(v,w)$ 是 E 中的一条边，则包含 e 的 G 的生成树数量等于 $\det Q^{{v,w}}(G)$
2. 设 $T=(V_T,E_T)$ 是 G 的一棵子树（$V_T$ 是 V 的真子集），则包含 T 的 G 的生成树数量等于 $\det Q^{V_T}(G)$

证明留给读者作为练习，但我想不明白。通过画一些随机图我理解结论是对的，但不知道为什么成立。有人能帮我吗？谢谢！

嘿，我来帮你拆解这两个推广结论的思路，其实核心都是用「边/子树收缩」的经典技巧，把问题转化为我们熟悉的经典矩阵树定理场景～

先看结论1：包含指定边e=(v,w)的生成树计数 #

首先回忆经典矩阵树定理：对于图G，移除其拉普拉斯矩阵任意一行一列后的行列式，等于G的生成树总数。

现在我们要求必须包含边e的生成树数量，这里可以用「收缩边」的操作：把顶点v和w合并成一个新顶点u，得到新图G'。此时你会发现，G中所有包含e的生成树，和G'中的生成树是一一对应的——因为包含e的生成树在收缩e后，自然就变成了G'的生成树，反过来G'的任何一棵生成树，展开收缩的边e就能得到G中包含e的生成树。

那G'的生成树数量怎么算？用经典矩阵树定理就行。而有意思的是：原拉普拉斯矩阵L(G)移除v和w的行、列得到的矩阵$Q^{{v,w}}(G)$，它的行列式正好等于G'的生成树数量！因为G'的拉普拉斯矩阵，本质是把L(G)中v和w的行、列分别相加得到新顶点u的行和列，再删掉v、w的行和列；而根据矩阵树定理，G'的生成树数量等于其拉普拉斯矩阵移除任意一行一列（比如新顶点u的行和列）的行列式，这个值恰好就是$\det Q^{{v,w}}(G)$。所以结论1就成立了。

再看结论2：包含指定子树T的生成树计数 #

这个是结论1的推广，我们可以用多次收缩或者归纳法来理解：

• 如果你用多次收缩：因为T是子树，它的边是连通的，我们可以逐个收缩T中的每条边，直到把整个T收缩成一个单一顶点u。每收缩一条边，就对应要求生成树必须包含这条边，多次收缩后得到的新图G''的顶点数是$|V| - |V_T| + 1$。
• 此时G中包含T的生成树，和G''中的生成树又是一一对应的。同样用经典矩阵树定理，G''的生成树数量等于其拉普拉斯矩阵移除任意一行一列的行列式，而这个值正好就是$\det Q^{{V_T}(G)$——因为$Q}{V_T}(G)$是原拉普拉斯矩阵移除所有V_T顶点的行和列得到的矩阵，和收缩T后得到的G''的拉普拉斯矩阵的余子式完全一致。

你也可以用归纳法验证：当T是单条边时，就是结论1，成立；假设T有k条边时结论成立，当T有k+1条边时，新增一条边e到T中得到T'，那么包含T'的生成树数量等于「包含T且包含e」的生成树数量，结合结论1的收缩思路和归纳假设，就能推导出结论2成立。

这样是不是就清楚多啦？核心就是把必须包含的边/子树收缩成一个顶点，把问题转化为熟悉的生成树计数，再对应到题目中的行列式上。

备注：内容来源于stack exchange，提问作者Mai