Matrix Tree Theorem

The Matrix Tree Theorem solves the problem of counting the number of spanning trees in a graph.

Notation Declaration in This Article

Graphs in this article, whether undirected or directed, allow multiple edges but by default have no self-loops.

Case with self-loops

Self-loops do not affect the number of spanning trees, nor do they affect the calculation of the Laplace matrix described below. Therefore, the Matrix Tree Theorem still holds for graphs with self-loops. There is no need to remove self-loops during computation. Removing self-loops would affect the application of the Matrix Tree Theorem according to the BEST theorem for counting Eulerian circuits in directed graphs.

Undirected Graph Case

Let \(G\) be an undirected graph with \(n\) vertices. Define the degree matrix \(D(G)\) as

\[ D_{ii}(G) = \mathrm{deg}(i),\ D_{ij} = 0,\ i\neq j. \]

Let \(\#e(i,j)\) be the number of edges connecting vertex \(i\) and vertex \(j\), and define the adjacency matrix \(A\) as

\[ A_{ij}(G)=A_{ji}(G)=\#e(i,j),\ i\neq j. \]

Define the Laplace matrix (also known as the Kirchhoff matrix) \(L\) as

\[ L(G) = D(G) - A(G). \]

Denote the number of all spanning trees of graph \(G\) as \(t(G)\).

Directed Graph Case

Let \(G\) be a directed graph with \(n\) vertices. Define the out-degree matrix \(D^{out}(G)\) as

\[ D^\mathrm{out}_{ii}(G) = \mathrm{deg}^\mathrm{out}(i),\ D^\mathrm{out}_{ij} = 0,\ i\neq j. \]

Similarly, define the in-degree matrix \(D^\mathrm{in}(G)\).

Let \(\#e(i,j)\) be the number of directed edges from vertex \(i\) to vertex \(j\), and define the adjacency matrix \(A\) as

\[ A_{ij}(G)=\#e(i,j),\ i\neq j. \]

Define the out-degree Laplace matrix \(L^\mathrm{out}\) as

\[ L^\mathrm{out}(G) = D^\mathrm{out}(G) - A(G). \]

Define the in-degree Laplace matrix \(L^\mathrm{in}\) as

\[ L^\mathrm{in}(G) = D^\mathrm{in}(G) - A(G). \]

Denote the number of all arborescences rooted at \(k\) in graph \(G\) as \(t^\mathrm{root}(G,k)\). An arborescence (rooted tree) means the underlying graph is a tree, with all edges directed towards the parent (root).

Denote the number of all leaf-oriented tree arborescences rooted at \(k\) in graph \(G\) as \(t^\mathrm{leaf}(G,k)\). A leaf-oriented tree arborescence means the underlying graph is a tree, with all edges directed away from the root towards the leaves.

Theorem Statements

The Matrix Tree Theorem has several forms.

Define \([n]=\{1,2,\cdots,n\}\), and the submatrix \(A_{S,T}\) of matrix \(A\) as the submatrix obtained by selecting elements \(A_{i,j}\pod{i\in S,j\in T}\).

Theorem 1 (Matrix Tree Theorem, undirected graph, determinant form)

For an undirected graph \(G\) and any \(k\), we have

\[ t(G) = \det L(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}. \]

That is, all \((n-1)\)-th order principal minors of the Laplace matrix of an undirected graph are equal, and all equal the number of spanning trees of the graph.

Corollary 1 (Matrix Tree Theorem, undirected graph, eigenvalue form)

Let \(\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_{n-1}\ge\lambda_n=0\) be the \(n\) eigenvalues of \(L(G)\). Then,

\[ t(G) = \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}. \]

Theorem 2 (Matrix Tree Theorem, directed graph arborescence, determinant form)

For a directed graph \(G\) and any \(k\), we have

\[ t^\mathrm{root}(G,k) = \det L^\mathrm{out}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}. \]

That is, the principal minor obtained by deleting the \(k\)-th row and \(k\)-th column from the out-degree Laplace matrix of a directed graph equals the number of arborescences rooted at \(k\).

Therefore, to count all arborescences of a graph, one can simply enumerate all roots \(k\) and sum \(t^\mathrm{root}(G,k)\).

Theorem 3 (Matrix Tree Theorem, directed graph leaf-oriented tree, determinant form)

For a directed graph \(G\) and any \(k\), we have

\[ t^\mathrm{leaf}(G,k) = \det L^\mathrm{in}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}. \]

That is, the principal minor obtained by deleting the \(k\)-th row and \(k\)-th column from the in-degree Laplace matrix of a directed graph equals the number of leaf-oriented tree arborescences rooted at \(k\).

Therefore, to count all leaf-oriented tree arborescences of a graph, one can simply enumerate all roots \(k\) and sum \(t^\mathrm{leaf}(G,k)\).

Note

Arborescences are also called inward tree arborescences, but since out-degree is used to compute inward tree arborescences, to avoid confusion between \(\mathrm{in}\) and \(\mathrm{out}\), the term "root-oriented" is adopted here.

Theorem Proof

Observing that the above theorem statements are very similar, here we provide a unified proof approach, and extend the previous conclusions to weighted graphs.

The general idea of the proof is as follows:

First, all cases can be reduced to counting arborescences in directed graphs;
Use matrix language to give necessary and sufficient conditions for a selected set of edges to form an arborescence;
Connect the edge selection operation to the determinant of the Laplace matrix using the Cauchy–Binet formula;
Finally, transform the determinant form conclusion into an eigenvalue form conclusion.

Lemma: Cauchy–Binet Formula

Lemma 1 (Cauchy–Binet)

Given an \(n\times m\) matrix \(A\) and an \(m\times n\) matrix \(B\), we have

\[ \det(AB)=\sum_{S\subset[m];~|S|=n}\det A_{[n],S}\det B_{S,[n]}, \]

where the summation notation means \(S\) runs over all subsets of \([m]\) of size \(n\). If \(n>m\), then necessarily \(\det(AB)=0\).

Proof (Combinatorial Perspective)

Refer to the model in 「NOI2021」Path Intersections. First, consider the following combinatorial interpretation of the determinant. For an \(n\times n\) matrix \(C\), construct a directed acyclic graph \(G=(V,E)\). The vertex set is \(V=[2]\times[n]\subset\mathbb R^2\), i.e., two columns of points in the plane. Denote the left column as \(L=\{l_i=(1,i):i\in[n]\}\) and the right column as \(R=\{r_i=(2,i):i\in[n]\}\); the directed edge set is \(E=\{(l_i,r_j):i,j\in[n]\}\), with edge weights \(w(l_i,r_j)=C_{i,j}\). In this graph, a set of edges \(E^\sigma\subset E\) of size \(n\) is called a path family if its starting points are distinct and its ending points are also distinct. Clearly, a path family \(E^\sigma\) corresponds one-to-one to a permutation \(\sigma\) on \([n]\). Note that if we draw a path family in the plane, these edges may intersect pairwise, and the number of intersection points (counting multiplicity) equals the number of inversions in \(\sigma\). This is because edges \((l_i,r_{\sigma(i)})\) and \((l_j,r_{\sigma(j)})\) intersect if and only if \((i-j)(\sigma(i)-\sigma(j))< 0\), i.e., an inversion pair. For convenience, the parity of the number of inversions of the corresponding permutation, i.e., the parity of the number of intersections of the path family, is called the parity of the path family. Therefore, if we count these path families by weight, and subtract the number of path families with an odd number of intersections from those with an even number, we obtain the Leibniz expansion of the determinant:

\[ \det(C)=\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_{i\in[n]}C_{i,\sigma(i)}, \]

where \(S_n\) is the permutation group on \([n]\), and \(\mathrm{sgn}(\sigma)\) is the sign of permutation \(\sigma\) (equal to \(1\) when the number of inversions is even, and \(-1\) when odd).

After understanding the combinatorial meaning of the determinant, we can prove the Cauchy–Binet formula using the following combinatorial model. For an \(n\times m\) matrix \(A\) and an \(m\times n\) matrix \(B\), construct a directed acyclic graph \(G=(V,E)\). The vertex set is \(V=L\cup D\cup R\), where \(L=\{l_i=(1,i):i\in[n]\}\), \(D=\{d_i=(2,i):i\in[m]\}\), and \(R=\{r_i=(3,i):i\in[n]\}\); the directed edge set is \(E=E_L\cup E_R\), where \(E_L=\{(l_i,d_j):i\in[n],j\in[m]\}\) and \(E_R=\{(d_j,r_i):j\in[m],i\in[n]\}\), with edge weights \(w(l_i,d_j)=A_{i,j}\) and \(w(d_j,r_i)=B_{j,i}\), respectively. Again consider path families from \(L\) through \(D\) to \(R\) (paths do not share vertices), count by weight, and subtract the number of path families with an odd number of intersections from those with an even number. We will show that the left and right sides of the Cauchy–Binet formula compute this difference in two ways.

For the left side, based on the described graph \(G\), construct a new graph \(G'\) with vertex set \(V'=L\cup R\) and edge set \(E'=\{(l_i,r_j):i,j\in[n]\}\), and assign edge weight \(\sum_{k\in[m]}A_{i,k}B_{k,j}\) to edge \((l_i,r_j)\), i.e., the weighted count of simple paths from \(l_i\) to \(r_j\) in the original graph \(G\). This edge weight is exactly \((AB)_{i,j}\). This simplifies the three-layer graph to a two-layer graph. However, path families in the two-layer graph \(G'\) (counted by weight) do not correspond one-to-one with path families in the three-layer graph \(G\). Since in the two-layer graph, each path corresponds to several simple paths in the three-layer graph, when counting path families in the two-layer graph, the weights are multiplied, which is equivalent to pairwise combining their corresponding path sets in the three-layer graph. This inevitably leads to situations where intermediate stop points are shared. However, these path pairs sharing intermediate stop points do not contribute to the final answer because for \(i_1< i_2\) and \(j_1< j_2\) and any intermediate point \(d\), there exist two simple path pairs \((l_{i_1}\rightarrow d\rightarrow r_{j_1}, l_{i_2}\rightarrow d\rightarrow r_{j_2})\) and \((l_{i_1}\rightarrow d\rightarrow r_{j_2}, l_{i_2}\rightarrow d\rightarrow r_{j_1})\), but these two groups of paths have opposite parity in the number of intersections in the three-layer graph, because if we only look at the start and end points, the two groups swap endpoints. Therefore, the contributions of these path pairs sharing intermediate stop points cancel out pairwise in the simplified two-layer graph counting. For the remaining cases, given the start and end points of two paths, no matter how the intermediate points are chosen (as long as they are not the same point), the parity of the number of intersections of these two paths does not change. Hence, all path families in \(G'\) corresponding to path families in the original graph \(G\) have the same parity. Thus, \(\det(AB)\) provides one way to compute the aforementioned difference in path family counts.

For the right side, it enumerates all possible combinations of intermediate points. Given any intermediate point set \(S\subset D=[m]\) with \(|S|=n\), consider path families from \(L\) to \(S\) and from \(S\) to \(R\) separately; connecting them yields path families from \(L\) to \(R\), and the composition of the permutations corresponding to the first two path families equals the permutation corresponding to the resulting path family. Therefore, the product of the parities of the first two path families equals the parity of the resulting path family. So, the difference in counts of all path families with intermediate point set \(S\) equals the product of the difference in counts of path families from \(L\) to \(S\) and the difference in counts of path families from \(S\) to \(R\). Summing over all possible \(S\) gives the right side, which is exactly the difference in path family counts.

Proof (Algebraic Perspective)

The above combinatorial proof can be translated verbatim into an algebraic proof. Here we provide another more technical algebraic proof, using several common results. When \(m< n\), the determinant is zero because

\[ \mathrm{rank}(AB)\le \min\{\mathrm{rank}(A),\mathrm{rank}(B)\}\le m< n. \]

When \(m=n\), the Cauchy–Binet formula states that the determinant of the product of square matrices equals the product of their determinants.

When \(m>n\), note that

\[ x^{m-n}\det(xI_n+AB) = \det(xI_m+BA). \]

It is known that the coefficient of \(x^{n-k}\) in \(\det(xI_n+C)\) is the sum of all \(k\)-th order principal minors of \(C\). Therefore, comparing coefficients on both sides of the above equation, we have

\[ \det(AB) = \sum_{S\subset[m];~|S|=n}\det(BA)_{S,S} = \sum_{S\subset[m];~|S|=n}\det(B)_{S,[n]}\det(A)_{[n],S} = \sum_{S\subset[m];~|S|=n}\det(A)_{[n],S}\det(B)_{S,[n]}. \]

Here, the second equality uses the result for the case \(m=n\).

Describing Graph Structure with Incidence Matrices

For a directed graph \(G=(V,E)\) with \(n\) vertices, \(m\) edges, and each edge \(e\) assigned a weight \(w(e)\). We can define the \(m\times n\) out-degree incidence matrix

\[ M^\mathrm{out}_{ij}=\begin{cases} \sqrt{w(e_i)},&\exists u(e_i=(v_j,u)),\\ 0,&\textrm{otherwise}, \end{cases} \]

and the \(m\times n\) in-degree incidence matrix

\[ M^\mathrm{in}_{ij}=\begin{cases} \sqrt{w(e_i)},&\exists u(e_i=(u,v_j)),\\ 0,&\textrm{otherwise}. \end{cases} \]

Each row records an edge: the out-degree incidence matrix \(M^\mathrm{out}\) records the starting vertex of an edge, and the in-degree incidence matrix \(M^\mathrm{in}\) records the ending vertex.

Simple calculation shows

\[ D^\mathrm{out}(G) = (M^\mathrm{out})^T M^\mathrm{out},\ A(G) = (M^\mathrm{out})^T M^\mathrm{in},\ D^\mathrm{in}(G) = (M^\mathrm{in})^T M^\mathrm{in}. \]

Thus,

\[ L^\mathrm{out}(G) = (M^\mathrm{out})^T (M^\mathrm{out}-M^\mathrm{in}),\ L^\mathrm{in}(G) = (M^\mathrm{in}-M^\mathrm{out})^T M^\mathrm{in}. \]

The Cauchy–Binet formula indicates that the principal minors of the Laplace matrix are actually sums of substructures. Each substructure reflects properties of the corresponding subgraph.

Lemma 2

For a subgraph \((W,S)\) of \(G\), if it satisfies \(|W|=|S|\le n\), then the subgraph \(T=(V,S)\) is a root-oriented forest with roots \(V\setminus W\) if and only if the corresponding expression

\[ \det(M^\mathrm{out}_{S,W})\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W}) \]

is nonzero. Moreover, when nonzero, this expression equals \(\prod_{e\in S}w(e)\), denoted as \(w(T)\).

Proof

Assume \(w(e)=1\) without loss of generality. By the multilinearity of the determinant, each row of each determinant can factor out \(\sqrt{w(e)}\), and the product of these factors is \(w(T)\).

First analyze the conditions for each factor being zero. The first factor \(\det(M^\mathrm{out}_{S,W})\) has at most one nonzero entry per row, namely \(+1\). If any row is all zeros, the determinant is zero. So this determinant is nonzero if and only if each row has exactly one \(+1\), i.e., each vertex in \(W\) is exactly the starting point of one edge in \(S\), and no two edges share the same starting point. For \(T\) to be a root-oriented forest with roots \(V\setminus W\), a necessary condition is that every vertex except the roots has exactly one parent, which necessarily makes this factor nonzero; but the converse is not necessarily true, because cycles might still exist, so we need to examine the second factor. Note that the endpoints of edges in \(S\) may not be in \(W\).

Assuming the first factor is nonzero, then \(T\) is a root-oriented forest if and only if \(T\) has no cycles. In this case, the second factor \(\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W})\) has one \(+1\) per row, but may have one or zero \(-1\)s. For edges whose endpoint is also in \(W\), if the endpoint of \(e_i\) is the starting point of \(e_j\), then adding the row corresponding to \(e_j\) to the row of \(e_i\) can eliminate the \(-1\) in row \(e_i\). One can imagine that this row now describes the simple path \(e_i\rightarrow e_j\rightarrow \cdots\rightarrow e_k\) formed by concatenation. If a new \(-1\) appears in this row, it means the endpoint of \(e_j\) is also in \(W\), and the position of \(-1\) is the endpoint of \(e_j\). Then we can continue to find the edge starting at the endpoint of \(e_j\) and add it to this row. Such an edge always exists because the previous paragraph shows each vertex in \(W\) is exactly the starting point of one edge in \(S\). This process continues until no new \(-1\) appears in the row, equivalent to continuously adding new edges to the simple path \(e_i\rightarrow e_j\rightarrow \cdots\rightarrow e_k\). If the row ends up with only one \(+1\), then the endpoint of \(e_k\) is not in the selected vertex set \(W\), and the process terminates; if the last added edge exactly cancels the existing \(+1\), i.e., the row becomes all zeros, then the endpoint of \(e_k\) is the starting point of the initial edge \(e_i\), meaning a cycle exists. Therefore, the condition for no cycles is that this determinant can be transformed via such operations into a form where each row has exactly one \(+1\). Since the positions of these \(+1\)s are the starting points of the corresponding edges, the resulting matrix is actually \(\det(M^\mathrm{out}_{S,W})\).

In summary, if \(T\) is not a root-oriented forest, then either \(\det(M^\mathrm{out}_{S,W})=0\) or \(\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W})=0\); otherwise, both are nonzero, and their product equals \(\left(\det(M^\mathrm{out}_{S,W})\right)^2=1\).

Matrix Tree Theorem for Weighted Directed Graphs

Now we can prove the main result of this article. The previously stated matrix tree theorems are special cases of this theorem.

Theorem 4 (Matrix Tree Theorem, weighted directed graph arborescence, determinant form)

For any \(k\), we have

\[ \sum_{T\in\mathcal T^\mathrm{root}(G,k)}w(T)=\det L^\mathrm{out}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}. \]

Here, \(\mathcal T^\mathrm{root}(G,k)\) is the set of arborescences of \(G\) rooted at \(k\).

Proof

Let \(W=[n]\setminus\{k\}\) be the set of remaining vertices after removing vertex \(k\). Then, by the Cauchy–Binet formula, the right side can be written as

\[ \det L^\mathrm{out}(G)_{W,W} = \sum_{S\subset[m];~|S|=n-1}\det(M^\mathrm{out}_{S,W})\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W}). \]

Traversing all \(S\), by Lemma 2, if and only if \(T=(V,S)\) forms a root-oriented forest with roots \(V\setminus W=\{k\}\), i.e., \(T\) is an arborescence rooted at \(k\), the right side accumulates a term \(w(T)\).

When \(w(e)=1\), the weight of each tree is \(1\), so the left side is the count of all trees, i.e., \(t^\mathrm{root}(G,k)\), yielding Theorem 2. By analogy, the conclusion can be directly extended to leaf-oriented tree arborescences, yielding Theorem 3. Finally, to obtain the spanning tree count for undirected graphs, apply the following corollary.

Corollary 4 (Matrix Tree Theorem, weighted undirected graph, determinant form)

For an undirected graph \(G\) and any \(k\), we have

\[ \sum_{T\in\mathcal T(G)}w(T) = \det L(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}. \]

Here, \(\mathcal T(G)\) is the set of spanning trees of \(G\). This also shows that all \((n-1)\)-th order principal minors of \(L(G)\) are equal.

Proof

For an undirected graph \(G=(V,E)\), construct a directed graph \(G'=(V,E')\), where \(E'=\{(v_i,v_j):(v_i,v_j)\in E\}\cup\{(v_j,v_i):(v_i,v_j)\in E\}\), i.e., each undirected edge in \(G\) is split into two directed edges in opposite directions. Choose any \(k\), then arborescences of \(G'\) rooted at \(k\) correspond one-to-one with spanning trees of \(G\). From the former to the latter, simply remove edge directions and the root choice; from the latter to the former, start from the chosen root \(k\) and assign directions towards the root for each edge. Thus,

\[ \sum_{T\in\mathcal T(G)}w(T) = \sum_{T\in\mathcal T^\mathrm{root}(G',k)}w(T) = \det L^\mathrm{out}(G')_{[n]\setminus\{k\},[n]\setminus\{k\}} = \det L(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}. \]

Here we used the result \(L^\mathrm{out}(G')=L(G)\), which is easily verified directly.

Eigenvalue Form

First consider the conclusion for directed graphs.

Theorem 5

For a directed graph \(G\), define the multivariate polynomial

\[ \chi(x_1,\cdots,x_n)=\det(\mathrm{diag}(x_1,\cdots,x_n)-L^\mathrm{out}(G)). \]

Here, \(\mathrm{diag}(x_1,\cdots,x_n)\) is the diagonal matrix with diagonal elements \(x_1,\cdots,x_n\). Then,

\[ (-1)^{n-r}[x_{k_1},\cdots,x_{k_r}]\chi(x_1,\cdots,x_n) \]

equals the (weighted) count of root-oriented forests of \(G\) with roots \(\{k_1,\cdots,k_r\}\).

Proof

Mimicking the proof of Theorem 4, note that if we let \(W=[n]\setminus\{k_1,\cdots,k_r\}\), then the coefficient in the theorem is \(\det L^\mathrm{out}(G)_{W,W}\) (this can be seen directly by observing the Leibniz expansion of the determinant). By the Cauchy–Binet formula, it equals

\[ \det L^\mathrm{out}(G)_{W,W} = \sum_{S\subset[m];~|S|=n-r}\det(M^\mathrm{out}_{S,W})\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W}). \]

Traversing all \(S\), by Lemma 2, if and only if \(T=(V,S)\) forms a root-oriented forest with roots \(V\setminus W=\{k_1,\cdots,k_r\}\), the right side accumulates a term \(w(T)\).

Substituting \(x\) for all unknowns, we obtain the characteristic polynomial of the Laplace matrix

\[ P(x) = \det(xI-L^\mathrm{out}(G)) = \chi(x,\cdots,x). \]

Lemma 3

The Laplace matrix \(L^\mathrm{out}(G)\) has at least one eigenvalue equal to zero.

Proof

It suffices to show its determinant is zero. Mimicking the proofs of Theorems 4 and 5, take \(W=\varnothing\); then this determinant should equal the number of root-oriented forests with zero trees. This does not exist, so the determinant is zero.

Corollary 5

For a directed graph \(G\), the total weight of all root-oriented forests consisting of \(k\) trees equals the coefficient

\[ (-1)^{n-k}[x^k]P(x). \]

Proof

Sum over all possible choices of \(k\) roots.

Define a \(k\)-spanning forest as a spanning subgraph of a graph such that the subgraph has \(k\) connected components and no cycles.

Corollary 6

Let \(\mathcal T_k(G)\) denote the set of \(k\)-spanning forests of an undirected graph \(G\). Then,

\[ \sum_{T\in\mathcal T_k(G)}w(T)Q(T) = (-1)^{n-k}[x^k]P(x). \]

Here, \(Q(T)\) is the product of the number of vertices in each connected component of forest \(T\). In particular, when \(k=1\), \(Q(T)=n\), so

\[ n\sum_{T\in\mathcal T(G)}w(T) = \lambda_1\lambda_2\cdots\lambda_{n-1}. \]

Proof

Mimicking the proof of Corollary 4, we can directly use the result of Corollary 5. Each root-oriented forest consisting of \(k\) trees in a directed graph corresponds to a \(k\)-spanning forest in the undirected graph. However, since each \(k\)-spanning forest \(T\) has \(Q(T)\) ways to choose roots, it appears in \(Q(T)\) root-oriented forests of the directed graph.

Applications

Cayley's Formula

Corollary 7 (Cayley)

The number of labeled unrooted trees on \(n\) vertices is \(n^{n-2}\).

Proof

Equivalently, we need to show that the number of spanning trees of the complete graph on \(n\) vertices is \(n^{n-2}\). For this, write the Laplace matrix

\[ L(G) = \left(\begin{matrix} n-1 & -1 & \cdots & -1 \\ -1 & n-1 & \cdots & -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \cdots & n-1 \end{matrix}\right)_{n\times n}. \]

Compute any of its principal minors:

\[ \det(nI_{n-1}-{\bf 1}{\bf 1}^T) = n^{n-1}\det(I_{n-1}-n^{-1}{\bf 1}{\bf 1}^T) = n^{n-1}(1-n^{-1}{\bf 1}^T{\bf 1}) = n^{n-1}(1-(n-1)/n) = n^{n-2}. \]

Applying Theorem 1 yields the conclusion.

BEST Theorem

Prerequisite: Eulerian Graph

This theorem connects the number of Eulerian circuits in a directed Eulerian graph with the number of arborescences of the graph, thus solving the counting problem for Eulerian circuits in directed graphs. Note that counting Eulerian circuits in arbitrary undirected graphs is NP-complete.

When implementing this algorithm, one should first determine if the given graph is Eulerian, remove all zero-degree vertices, then construct the graph to count the number of arborescences, and obtain the Eulerian circuit count via the BEST theorem. Note that if the Eulerian circuit count requires a given starting vertex, the answer should be multiplied by the out-degree of that vertex, equivalent to enumerating the first edge of the circuit.

Before proving the BEST theorem, we need the following result.

Property (Criterion for Eulerian circuit in directed graph)

A directed graph has an Eulerian circuit if and only if its non-zero-degree vertices are strongly connected and the out-degree equals the in-degree for every vertex.

For Eulerian graphs, since out-degree equals in-degree, we can omit the superscript and denote it as \(\mathrm{deg}(v)\). The BEST theorem can be stated as follows.

Theorem 6 (BEST Theorem)

Let \(G\) be a directed Eulerian graph, and \(k\) be any vertex. Then the total number of distinct Eulerian circuits \(\mathrm{ec}(G)\) in \(G\) is

\[ \mathrm{ec}(G) = t^\mathrm{root}(G,k)\prod_{v\in V}(\deg (v) - 1)!. \]

This also shows that for any two vertices \(k, k'\) in an Eulerian graph \(G\), \(t^\mathrm{root}(G,k)=t^\mathrm{root}(G,k')\).

Proof

The general idea of the proof is to establish a correspondence between Eulerian circuits starting at \(k\) and arborescences rooted at \(k\) along with permutations of outgoing edges at each vertex. After specifying the vertices of the Eulerian circuit, the count to be proved should equal

\[ \mathrm{deg}(k)\mathrm{ec}(G) = t^\mathrm{root}(G,k)\deg(k)!\prod_{v\neq k}(\deg (v) - 1)!. \]

The combinatorial meaning of this count corresponds to the following construction. For an Eulerian circuit starting at \(k\), according to the order of appearance of each edge in the circuit, we can construct:

An arborescence rooted at \(k\), consisting of the last outgoing edge at each non-root vertex, i.e., \(t^\mathrm{root}(G,k)\),
The permutation order of all outgoing edges at the root \(k\), i.e., \(\mathrm{deg}(k)!\), and
The permutation order of all other outgoing edges (excluding the last one) at each non-root vertex \(v\neq k\), i.e., \((\mathrm{deg}(v)-1)!\).

We now show that this construction yields a bijection.

On one hand, given an Eulerian circuit, we need to show that the last outgoing edge at each non-root vertex forms an arborescence. By construction, each non-root vertex indeed has exactly one outgoing edge in the tree, so we only need to show these edges do not form a cycle. Note that if we order all vertices according to their last appearance in the Eulerian circuit, then the last outgoing edge of a non-root vertex must point to a vertex that appears strictly later in this order. If a cycle exists, then there is a vertex in the cycle that appears last in this order; since it is in the cycle, it points to a vertex that does not appear later, contradicting the above. Therefore, the last outgoing edges of non-root vertices necessarily form an arborescence.

On the other hand, given any arborescence and permutation orders of the remaining outgoing edges, we can reconstruct an Eulerian circuit such that after applying the above construction to this circuit, we obtain the given arborescence and permutation orders. For this, start from the root \(k\); whenever arriving at a vertex, choose the first outgoing edge in the given permutation order for that vertex that has not yet been traversed as the next edge in the Eulerian circuit; if all outgoing edges in the permutation have been traversed, choose the outgoing edge from the arborescence at that vertex as the next edge. Since the graph is Eulerian, the in-degree equals the out-degree at each vertex, so this process will not terminate at a non-root vertex, i.e., the resulting path is indeed a circuit. To prove the resulting path is a valid Eulerian circuit, we only need to show it traverses all edges.

If not, then some outgoing edge from some vertex \(v\) is not traversed. Consider vertex \(v\). Vertex \(v\) cannot be the root, because the process terminates at the root; if the root still has untraversed outgoing edges, this contradicts termination. So \(v\) must not be the root. According to the described process, as long as a non-root vertex \(v\) has any untraversed outgoing edges, then the outgoing edge \(e\) from \(v\) in the tree must remain untraversed. Let \(e=(v,u)\). Since some incoming edge to \(u\) is not traversed, and the out-degree of \(u\) equals its in-degree, there must be some outgoing edge from \(u\) not traversed. Then we can similarly consider vertex \(u\). This reasoning moves the considered vertex from \(v\) to \(u\), i.e., one step towards the root along the arborescence. By induction, this implies that some outgoing edge from the root \(k\) is not traversed. As already shown, this is impossible, leading to a contradiction. Thus, the path obtained in the previous paragraph is indeed a valid Eulerian circuit.

It can be verified that these mappings are injective, hence they are both bijections. The original proposition is proved.

Implementation

Write the Laplace matrix from the graph, delete one row and one column, and compute the determinant of the resulting matrix. The determinant can be computed using Gauss–Jordan elimination.

For example, the number of spanning trees of a square graph

\[ \begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{pmatrix}-\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}=\begin{pmatrix} 2 & -1 & 0 & -1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{pmatrix} \]

\[ \begin{vmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{vmatrix} = 4 \]

Can be solved using Gauss–Jordan elimination with time complexity \(O(n^3)\).

Implementation

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MOD = 100000007;
constexpr double eps = 1e-7;

struct matrix {
  static constexpr int MAXN = 20;
  int n, m;
  double mat[MAXN][MAXN];

  matrix() { memset(mat, 0, sizeof(mat)); }

  void print() {
    cout << "MATRIX " << n << " " << m << endl;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << mat[i][j] << "\t";
      }
      cout << endl;
    }
  }

  void random(int n) {
    this->n = n;
    this->m = n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) mat[i][j] = rand() % 100;
  }

  void initSquare() {
    this->n = 4;
    this->m = 4;
    memset(mat, 0, sizeof(mat));
    mat[0][1] = mat[0][3] = 1;
    mat[1][0] = mat[1][2] = 1;
    mat[2][1] = mat[2][3] = 1;
    mat[3][0] = mat[3][2] = 1;
    mat[0][0] = mat[1][1] = mat[2][2] = mat[3][3] = -2;
    this->n--;  // remove one row
    this->m--;  // remove one column
  }

  double gauss() {
    double ans = 1;
    for (int i = 0; i < n; i++) {
      int sid = -1;
      for (int j = i; j < n; j++)
        if (abs(mat[j][i]) > eps) {
          sid = j;
          break;
        }
      if (sid == -1) continue;
      if (sid != i) {
        for (int j = 0; j < n; j++) {
          swap(mat[sid][j], mat[i][j]);
          ans = -ans;
        }
      }
      for (int j = i + 1; j < n; j++) {
        double ratio = mat[j][i] / mat[i][i];
        for (int k = 0; k < n; k++) {
          mat[j][k] -= mat[i][k] * ratio;
        }
      }
    }
    for (int i = 0; i < n; i++) ans *= mat[i][i];
    return abs(ans);
  }
};

int main() {
  srand(1);
  matrix T;
  // T.random(2);
  T.initSquare();
  T.print();
  double ans = T.gauss();
  T.print();
  cout << ans << endl;
}

Example Problems

Example 1: 「HEOI2015」Little Z's Room

Solution A direct application of the Matrix Tree Theorem. Treat each empty room as a vertex, construct the graph based on the input, obtain the Laplace matrix, then delete the \(i\)-th row and \(i\)-th column of \(L\) arbitrarily, and compute the determinant of this minor. The method to compute the determinant is Gaussian elimination to upper triangular form and then multiplying the diagonal entries. Additionally, this problem requires Gaussian elimination over the integer subring \(\mathbb{Z}_k\) modulo \(k\), which can be done using the Euclidean algorithm.

Example 2: 「FJOI2007」Wheel Virus

Solution There are many solutions to this problem; using the Matrix Tree Theorem is the most direct. When the input is \(n\), it is easy to write its \((n+1)\)-th order Laplace matrix as:

\[ L_n = \begin{bmatrix} n& -1& -1& -1& \cdots& -1& -1\\ -1& 3& -1& 0& \cdots& 0& -1\\ -1& -1& 3& -1& \cdots& 0& 0\\ -1& 0& -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ -1& 0& 0& 0& \cdots& 3& -1\\ -1& -1& 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n+1} \]

Compute the determinant of its \(n\)-th order minor. The rest is high-precision calculation.

Example 2+

Strengthen the data of Example 2, requiring \(n\leq 100000\), but the answer is taken modulo 1000007. (Solving this problem requires some linear algebra knowledge.)

Solution Derive a recurrence relation and use matrix exponentiation.

Derivation process:

Note that the matrix obtained after deleting the first row and first column of \(L_n\) has a regular pattern, so we are essentially computing the determinant of the matrix

\[ M_n = \begin{bmatrix} 3& -1& 0& \cdots& 0& -1\\ -1& 3& -1& \cdots& 0& 0\\ 0& -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& 0& \cdots& 3& -1\\ -1& 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n} \]

Expand the determinant of \(M_n\) along the first column to obtain

\[ \det M_n = 3\det \begin{bmatrix} 3& -1& \cdots& 0& 0\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n-1} + \det\begin{bmatrix} -1& 0& \cdots& 0& -1\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n-1} + (-1)^n \det\begin{bmatrix} -1& 0& \cdots& 0& -1\\ 3& -1& \cdots& 0& 0\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ \end{bmatrix}_{n-1} \]

Denote the determinants of these three matrices as \(d_{n-1}, a_{n-1}, b_{n-1}\).
Note that \(d_n\) is a tridiagonal determinant; using a similar expansion method, we find \(d_n\) satisfies the recurrence \(d_n=3d_{n-1}-d_{n-2}\). Similarly, expanding gives \(a_{n-1}=-d_{n-2}-1\), and \((-1)^n b_{n-1}=-d_{n-2}-1\).
Substituting these recurrences into the above equation yields:

\[ \det M_n = 3d_{n-1}-2d_{n-2}-2 \]

\[ d_n = 3d_{n-1}-d_{n-2} \]

Thus we conjecture \(\det M_n\) also satisfies a non-homogeneous second-order linear recurrence. Using the method of undetermined coefficients, the final recurrence is

\[ \det M_n = 3\det M_{n-1} - \det M_{n-2} + 2 \]

Rewriting as \((\det M_n+2) = 3(\det M_{n-1}+2) - (\det M_{n-2} + 2)\), matrix exponentiation can be used to compute the answer.

Example 3: 「BZOJ3659」WHICH DREAMED IT

Solution This problem is a direct application of the BEST theorem. However, note that the problem states "two ways of completing the task are considered different if and only if the order of using keys is different." For each Eulerian circuit, room 1 can start along any outgoing edge, so the answer must be multiplied by the out-degree of room 1.

Example 4: 「United Provincial Selection 2020 A」Homework Problem

Solution First, Möbius inversion is needed to transform the problem into computing the sum of edge weights over all spanning trees, which is omitted as it is not closely related to this article.

Write each term of the determinant as \(w_ix+1\). The final answer is the coefficient of the linear term of the determinant, because the answer is actually the sum of edge weights of a spanning tree after fixing an edge \(\times\) the number of spanning trees after fixing that edge. Then the edge multiplied by the linear coefficient is the fixed edge. At this point, terms of degree higher than one can be ignored, complexity \(O(n^3)\).

「Beijing Provincial Selection Training 2019」Spanning Tree Counting is a more generalized case: compute the sum of the \(k\)-th powers of spanning tree weights. Construct determinant terms similarly; see the Luogu solution for details.

Example 5: AGC051D C4

Solution Counting Eulerian circuits in undirected graphs is an NPC problem, but the graph in this problem is relatively simple. Once the number of edges from \(S\) to \(T\) directed from \(S\) to \(T\) among the \(S-T\) edges is determined, the orientation of the other three edges can be determined. Then directly apply the BEST theorem to get an \(O(a+b+c+d)\) solution.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用