考虑一个经典问题：一个 (n) 个点 (m) 条边的无向连通图 ( m{G})，求这个图的生成树个数。 (n leq 300) 。
先给 ( m{G}) 随便定个向（之后的 ( m{G}) 仍然为无向的），然后定义 ( m{G}) 的关联矩阵 ( m{M}) 满足：
显然 ( m{M}) 是 (n imes m) 的矩阵，而且第 (i) 行一共有 (deg(i)) 个地方有值，第 (j) 列只有两个地方有值。
再定义 ( m{G}) 的 ( m{Laplace}) 矩阵 ( m{L}) 为：
首先有 (
m{M}
m{M}^{
m{T}}=
m{L}) ， 其中 (
m{M}^{
m{T}}) 表示 (
m{M}) 的转置。
证明： 考虑 (
m{M}) 的第 (i) 行的向量 (
m{M}_i) 与 (
m{M}^{
m{T}}) 的第 (j) 列的向量 (
m{M}_j) 做点乘，分类讨论一下：
如果 (i = j) ，那么 (
m{M}_i =
m{M}_j) 。则点乘第 (k) 维的时，如果 (e_k) 不连接 (i) ，结果为 (0) ；否则为 (1) 。所以 ((
m{M}
m{M}^{
m{T}})_{i,i} = deg(i))。
如果 (i
eq j) ，那么 (
m{M}_{i,k} imes
m{M}_{j,k}) 有值时，当且仅当 (e_k) 连接了 (i,j) ，此时值为 (-1) ；否则为 (0) 。因此 ((
m{M}
m{M}^{
m{T}})_{i,j} = -f_{i,j})。
定义一个矩阵 (
m{M})_0 是 (
m{M}) 去掉任意一行后的新矩阵。
定义一个关于 (
m{M}_0) 的矩阵 (
m{M}_0[
m{S}]) 为 (
m{M}_0) 的第 (i_1 , i_2 , cdots i_{n-1}) 个列向量组成的子矩阵。其中 (i_1 , i_2 , i_{n-1} in
m{S}) ， (
m{S}) 为大小等于 (n-1) 的一个边集。
现在设原图点集 (
m{V}) 与 (
m{S}) 构成的子图为 (
m{G_0}) ，若 (
m{G_0}) 不构成生成树，即(
m{G_0}) 有环，则 (det(
m{M}_0[S]) = 0)；否则等于 (±1) 。
证明 ：假设出现环了，且假设环由 (e_1 , e_2 , cdots e_l) 这些边组成。则容易发现这 (l) 条边对应的列向量是线性相关的。此时的行列式就等于 (0) 。否则就构成生成树了。考虑怎么如果这些边构成了生成树，怎么计算这个矩阵的行列式。首先从叶子开始拓补排序，按照拓补序给行向量排个序。显然与叶子有关的边只有一条，我们把它对应的列向量排到队列里面去。这样的话每个点一定在它所有儿子的后面，当我们排序完所有儿子的边的列向量之后，现在与它相关的边又只有一条了，此时我们还是把它排到队列里去。可以发现像这样排序后第 (i) 行的第 (i+1)~(n-1) 列都是没有值的，此时就把矩阵变成了一个分布在左下的三角矩阵。由于对角线上的元素只可能是 (±1) ，又因为排序时行间交换与列间交换只会对正负造成影响，所以这个矩阵的行列式为 (±1) 。
再补充一个 ( m{Binet Cauchy}) 定理 ：
约定其中 (
m{A}) 是一个 (n imes m) 的矩阵， (
m{B}) 是一个 (m imes n) 的矩阵，(
m{A[S]}) 为从 (
m{A}) 中选出编号集合为 (
m{S}) 的行向量组成的矩阵，与之前定义一样； (
m{B[S]}) 为选出列向量，与上面有区别。
容易发现前两种情况是第三种的特殊情况，因此我们只关注第三种情况。
这里大概证一下：
由于行列式是枚举排列，考虑枚举每一列的 (k) ：
注意到当存在一个 (k_a=k_b) 时，行列式就为 (0) 了。所以我们对 ( m{A}) 的下标枚举一个不可重集 ({ i_1 , i_2 , cdots , i_n }) ，集合元素都在 ([1,m]) 之间。则现在的 ({ k_1,k_2, cdots k_n }) 对应以一个 ({ i_1 , i_2 , cdots , i_n }) 排序前的序列。注意到排序时一旦有 (i<j,k_i>k_j) ，则 第(k_i)行 会被交换一次，因此交换次数等于逆序对数，也就是 (sigma(k_1,k_2,cdots,k_n)) 。那么：
证完前面这些引理就很容易证矩阵树定理了。
类似于 (
m{M_0}) （假设去掉的是第 (i) 行），我们定义一个 (
m{L}_0) 表示去掉 (
m{L}) 的第 (i) 行第 (i) 列后的新矩阵。显然有 (
m{M_0}
m{M_0}^{
m{T}}=
m{L}_0)。则
证明 ：
然后我们又知道，当 (
m{S}) 对应的边集成环时行列式为 (0) ，否则为 (±1) 。因此 (sum_{|S|=n-1}det(
m{M_0}[
m{S}])^2) 就等于生成树个数。
至此我们将生成树计数转化为了计算行列式，就可以做到 (mathcal{O} (n^3)) 了。
拓展 ：有向图的有根生成树计数。
有根外向树 ：
由于是有向图，我们不需要先给 (
m{G}) 定向，直接用原图的方向构造关联矩阵 (
m{M}) 即可。再构造一个 入度矩阵 (
m{D}) ，如果第 (i) 条边连接 (x
ightarrow y) ，则令 (
m{D}_{y,i}=1)。再构造有向图的外向 (
m{Laplace}) 矩阵 (
m{L}) ，与无向图情况的定义相同。
可以类似地将无向图的引理对应过来：
首先有 (
m{MD^T=L}) 。然后给 (
m{M}) 和 (
m{D}) 去掉第 (
m root) 行形成 (
m{M_0,D_0}) （ (
m root) 为根），考虑 (
m{M_0[S]}) ，发现如果成环了或者有边连向 (
m root) 行列式就为 (0) ，否则为 (±1) ；同样地观察 (
m{D_0[S]}) ，发现如果不连通且未成环，行列式也为 (0) ，因为存在入度为 (0) 的点，否则行列式为 (1) 。
仿照无向图的证明过程，我们把 (
m L) 的第 (
m root) 行和第 (
m root) 列去掉形成 (
m L_0) ，仍然有 (
m L_0 = M_0D_0^T) ，那么把 (
m L_0) 的行列式用 (
m BinetCauchy) 定理展开就可以得到 (
m L_0) 的行列式等于以 (
m root) 为根的外向生成树个数。
有根内向树 ：
类似于外向的情况，只不过要给 (
m M) 乘个 (-1) 的系数，把 (
m D) 改成出度矩阵即可。其余的证明因为太相似所以略过。