Skip to content

Matrix Tree Theorem

The matrix tree theorem counts the spanning trees of a graph.

Notation

Graphs on this page, directed or undirected, may have multiple edges but have no self-loops unless stated otherwise.

Graphs with self-loops

Self-loops do not change the number of spanning trees: just leave them out when you compute the Laplacian matrix. When you count Eulerian circuits with the BEST theorem, however, the degrees must include the self-loops.

Undirected graphs

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

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

Let \(\#e(i,j)\) be the number of edges joining vertices \(i\) and \(j\), and define the adjacency matrix \(A\) by

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

Define the Laplacian matrix \(L\) (also called the Kirchhoff matrix) by

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

Write \(t(G)\) for the number of spanning trees of \(G\).

Directed graphs

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

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

The in-degree matrix \(D^\mathrm{in}(G)\) is defined in the same way.

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

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

Define the out-degree Laplacian matrix \(L^\mathrm{out}\) by

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

Define the in-degree Laplacian matrix \(L^\mathrm{in}\) by

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

Write \(t^\mathrm{root}(G,k)\) for the number of root-oriented arborescences of \(G\) rooted at \(k\). A root-oriented arborescence is a graph whose underlying graph is a tree and in which every edge points to the parent.

Write \(t^\mathrm{leaf}(G,k)\) for the number of leaf-oriented arborescences of \(G\) rooted at \(k\). A leaf-oriented arborescence is a graph whose underlying graph is a tree and in which every edge points to the child.

Statement of the theorem

The matrix tree theorem comes in several forms.

Let \([n]=\{1,2,\cdots,n\}\). For a matrix \(A\), the submatrix \(A_{S,T}\) consists of the entries \(A_{i,j}\pod{i\in S,j\in T}\).

Theorem 1 (matrix tree theorem, undirected graphs, determinant form)

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

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

In other words, all principal minors of order \(n-1\) of the Laplacian of an undirected graph are equal, and their common value is the number of spanning trees of the graph.

Corollary 1 (matrix tree theorem, undirected graphs, 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, root-oriented trees in directed graphs, determinant form)

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

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

In other words, the principal minor obtained by deleting row \(k\) and column \(k\) from the out-degree Laplacian of a directed graph is the number of root-oriented arborescences rooted at \(k\).

So to count all root-oriented arborescences of a graph, enumerate every root \(k\) and sum \(t^\mathrm{root}(G,k)\).

Theorem 3 (matrix tree theorem, leaf-oriented trees in directed graphs, determinant form)

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

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

In other words, the principal minor obtained by deleting row \(k\) and column \(k\) from the in-degree Laplacian of a directed graph is the number of leaf-oriented arborescences rooted at \(k\).

So to count all leaf-oriented arborescences of a graph, enumerate every root \(k\) and sum \(t^\mathrm{leaf}(G,k)\).

Remark

A root-oriented arborescence is also called an in-arborescence. But counting in-arborescences uses out-degrees, so to keep \(\mathrm{in}\) and \(\mathrm{out}\) from being confused, this page says "root-oriented" instead.

Proof of the theorem

The theorems above look very much alike. This section gives a single proof that covers all of them, and extends the results to weighted graphs.

The proof goes roughly as follows:

  • first, every case reduces to counting root-oriented arborescences in a directed graph;
  • in matrix language, we give a necessary and sufficient condition for a chosen set of edges to form a root-oriented arborescence;
  • the Cauchy–Binet formula connects the choice of edges to the determinant of the Laplacian;
  • finally, we turn the determinant form into the eigenvalue form.

Lemma: the Cauchy–Binet formula

Lemma 1 (Cauchy–Binet)

Let \(A\) be an \(n\times m\) matrix and \(B\) an \(m\times n\) matrix. Then

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

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

Proof (combinatorial)

Following the model of [NOI2021] Path Intersections, we start with a combinatorial interpretation of the determinant. For an \(n\times n\) matrix \(C\), build a directed acyclic graph \(G=(V,E)\). Its vertex set is \(V=[2]\times[n]\subset\mathbb R^2\), that is, two columns of points in the plane. Call the left column \(L=\{l_i=(1,i):i\in[n]\}\) and the right column \(R=\{r_i=(2,i):i\in[n]\}\). The set of directed edges is \(E=\{(l_i,r_j):i,j\in[n]\}\), with edge weights \(w(l_i,r_j)=C_{i,j}\). A subset \(E^\sigma\subset E\) of \(n\) edges is called a path system if its edges have pairwise distinct start vertices and pairwise distinct end vertices. Clearly, path systems \(E^\sigma\) are in one-to-one correspondence with permutations \(\sigma\) of \([n]\). If you draw a path system in the plane, some pairs of its edges may cross, and the number of these intersection points (counted with multiplicity) equals the number of inversions of \(\sigma\). This is because the edges \((l_i,r_{\sigma(i)})\) and \((l_j,r_{\sigma(j)})\) cross if and only if \((i-j)(\sigma(i)-\sigma(j))< 0\), that is, if and only if they form an inversion. For convenience, define the parity of a path system as the parity of the number of inversions of its permutation, which is the parity of its number of intersection points. So if we count path systems by weight, and subtract the count of those with an odd number of intersection points from the count of those with an even number, we get 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 group of permutations of \([n]\) and \(\mathrm{sgn}(\sigma)\) is the sign of the permutation \(\sigma\) (it is \(1\) when the number of inversions is even and \(-1\) when it is odd).

With this interpretation of the determinant in hand, we can prove the Cauchy–Binet formula using the combinatorial model below. For an \(n\times m\) matrix \(A\) and an \(m\times n\) matrix \(B\), build a directed acyclic graph \(G=(V,E)\). Its 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]\}\). Its set of directed edges 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. As before, consider path systems from \(L\) through \(D\) to \(R\) (no two paths share a vertex), count them by weight, and subtract the count of those with an odd number of intersection points from the count of those with an even number. We now show that the two sides of the Cauchy–Binet formula compute this quantity in two ways.

For the left-hand side, build from \(G\) a new graph \(G'\) with vertex set \(V'=L\cup R\) and edge set \(E'=\{(l_i,r_j):i,j\in[n]\}\), and give the edge \((l_i,r_j)\) the weight \(\sum_{k\in[m]}A_{i,k}B_{k,j}\), 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}\). In effect, the three-layer graph has been collapsed into a two-layer graph. However, path systems of the two-layer graph \(G'\) (counted by weight) are not in one-to-one correspondence with path systems of the three-layer graph \(G\). Each path of the two-layer graph stands for several simple paths of the three-layer graph, and counting path systems in the two-layer graph multiplies the weights. This amounts to combining the corresponding sets of paths of the three-layer graph in every possible way, which inevitably produces paths that share a middle point. But pairs of paths that share a middle point contribute nothing to the final answer. For \(i_1< i_2\), \(j_1< j_2\) and any middle point \(d\), there are two pairs of simple paths, \((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})\), and their numbers of intersection points in the three-layer graph have opposite parities: looking only at start and end vertices, the two pairs have their end vertices swapped. So in the count on the collapsed two-layer graph, the contributions of paths that share a middle point cancel in pairs. In the remaining cases, once the start and end vertices of two paths are given, the parity of their number of intersection points does not depend on the choice of middle points (as long as the two are different). Hence all path systems of the original graph \(G\) that correspond to one path system of \(G'\) have the same parity. Therefore \(\det(AB)\) is one way to compute the difference of path system counts described above.

The right-hand side enumerates all possible combinations of middle points. Given a set of middle points \(S\subset D=[m]\) with \(|S|=n\), take a path system from \(L\) to \(S\) and a path system from \(S\) to \(R\). Joining them gives a path system from \(L\) to \(R\) whose permutation is the composition of the permutations of the two parts, so its parity is the product of their parities. So the difference of counts over all path systems with middle point set \(S\) is exactly the product of the difference of counts for path systems from \(L\) to \(S\) and the difference of counts for path systems from \(S\) to \(R\). Summing over all possible \(S\) gives the right-hand side, which is therefore the same difference of path system counts.

Proof (algebraic)

The combinatorial proof above can be translated word for word into an algebraic one. Here we give a different algebraic proof instead, one that leans more on tricks but uses a few standard facts. 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 says that the determinant of a product of square matrices is the product of their determinants.

When \(m>n\), note that

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

Recall also that the coefficient of \(x^{n-k}\) in \(\det(xI_n+C)\) is the sum of all principal minors of order \(k\) of \(C\). Comparing coefficients on both sides of the identity above gives

\[ \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]}. \]

The second equality uses the case \(m=n\).

Describing a graph by incidence matrices

Let \(G=(V,E)\) be a directed graph with \(n\) vertices and \(m\) edges, in which each edge \(e\) has a weight \(w(e)\). 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 of these matrices records one edge: the out-degree incidence matrix \(M^\mathrm{out}\) records its tail, and the in-degree incidence matrix \(M^\mathrm{in}\) records its head.

A short computation shows that

\[ 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}. \]

Hence

\[ 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}. \]

By the Cauchy–Binet formula above, a principal minor of the Laplacian is a sum over substructures, each of which reflects a property of the corresponding subgraph.

Lemma 2

Let \(W\subseteq V\) be a subset of the vertices and \(S\subseteq E\) a subset of the edges with \(|W|=|S|\le n\). If the subgraph \(T=(V,S)\) is a root-oriented forest whose roots are \(V\setminus W\), then the expression

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

equals \(\prod_{e\in S}w(e)\), which we denote by \(w(T)\). Otherwise it equals zero.

Proof

We may assume \(w(e)=1\): by multilinearity of the determinant, a factor \(\sqrt{w(e)}\) can be pulled out of each row of each determinant, and the product of these factors is \(w(T)\).

First we find out when each of the two factors is zero. Each row of the first factor \(\det(M^\mathrm{out}_{S,W})\) has at most one nonzero entry, a \(+1\). If some row is all zeros, or two rows have their \(+1\) in the same column, the determinant is zero. So this determinant is nonzero if and only if every row and every column contains exactly one \(+1\), that is, the tail of every edge of \(S\) lies in \(W\), and every vertex of \(W\) is the tail of exactly one edge of \(S\). For \(T\) to be a root-oriented forest with roots \(V\setminus W\), it is necessary that every vertex other than the roots has exactly one parent, and this makes the first factor nonzero. The converse may fail, because nothing rules out a cycle, so we must also look at the second factor. Note that the heads of the edges of \(S\) need not lie in \(W\).

Suppose the first factor is nonzero. Then the subgraph \(T\) is a root-oriented forest if and only if it has no cycle. Each row of the second factor \(\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W})\) contains one \(+1\), and one \(-1\) or none. Take an edge \(e_i\) whose head also lies in \(W\). If its head is the tail of \(e_j\), adding the row of \(e_j\) to the row of \(e_i\) cancels the \(-1\) in row \(e_i\). Think of the row as now describing the simple path formed by \(e_i\) followed by \(e_j\). If a new \(-1\) appears in the row, the head of \(e_j\) also lies in \(W\), and the \(-1\) sits at that head. We can then find the edge whose tail is the head of \(e_j\) and add its row as well. Such an edge always exists, since by the previous paragraph every vertex of \(W\) is the tail of exactly one edge of \(S\). Continue until the row no longer contains a \(-1\). This keeps appending new edges to the simple path \(e_i\rightarrow e_j\rightarrow \cdots\rightarrow e_k\). If at that point the row is left with a single \(+1\), the head of \(e_k\) is not among the chosen vertices \(W\), and the process stops. If the last edge added happens to cancel the existing \(+1\), so that the row is all zeros, the head of the new edge \(e_k\) is the tail of the first edge \(e_i\), and we have found a cycle. If the process never stops, the path has entered a cycle, and the rows of the edges on that cycle likewise become zero. So there is no cycle if and only if these operations transform the determinant into one in which every row contains exactly one \(+1\). Each of these \(+1\) entries sits at the tail of the edge of its row, so the resulting matrix is in fact \(M^\mathrm{out}_{S,W}\), and the two determinants are equal.

To sum up, 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 is \(\left(\det(M^\mathrm{out}_{S,W})\right)^2=1\).

The matrix tree theorem for weighted directed graphs

We can now prove the main result of this article. All the forms of the matrix tree theorem stated earlier are special cases of it.

Theorem 4 (matrix tree theorem, root-oriented trees in weighted directed graphs, determinant form)

For any \(k\),

\[ \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 root-oriented arborescences of \(G\) rooted at \(k\).

Proof

Let \(W=[n]\setminus\{k\}\) be the set of all vertices other than \(k\). By the Cauchy–Binet formula, the right-hand 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}). \]

Go through all \(S\). By Lemma 2, the right-hand side gains a term \(w(T)\) if and only if \(T=(V,S)\) is a root-oriented forest with roots \(V\setminus W=\{k\}\), that is, if and only if \(T\) is a root-oriented arborescence rooted at \(k\).

When \(w(e)=1\), every tree has weight \(1\), so the left-hand side is the number of trees, \(t^\mathrm{root}(G,k)\). This gives Theorem 2. The same argument carries over directly to leaf-oriented arborescences, which gives Theorem 3. Finally, the count of spanning trees of an undirected graph follows from the corollary below.

Corollary 2 (matrix tree theorem, weighted undirected graphs, determinant form)

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

\[ \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 principal minors of order \((n-1)\) of \(L(G)\) are equal.

Proof

From an undirected graph \(G=(V,E)\), build the directed graph \(G'=(V,E')\) with \(E'=\{(v_i,v_j):(v_i,v_j)\in E\}\cup\{(v_j,v_i):(v_i,v_j)\in E\}\), that is, split every undirected edge of \(G\) into two directed edges with opposite directions. Fix any \(k\). Then the root-oriented arborescences of \(G'\) rooted at \(k\) are in one-to-one correspondence with the spanning trees of \(G\). To go from the former to the latter, forget the orientation of the edges and the choice of root. To go back, start from the chosen root \(k\) and orient the edges one by one towards the root. So

\[ \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\}}. \]

This uses \(L^\mathrm{out}(G')=L(G)\), which is easy to verify directly.

Eigenvalue form

Again we start with 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 entries \(x_1,\cdots,x_n\). Then

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

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

Proof

We follow the proof of Theorem 4. Let \(W=[n]\setminus\{k_1,\cdots,k_r\}\). Then the expression in the theorem is \(\det L^\mathrm{out}(G)_{W,W}\) (to see this, look at 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}). \]

Go through all \(S\). By Lemma 2, the right-hand side gains a term \(w(T)\) if and only if \(T=(V,S)\) is a root-oriented forest with roots \(V\setminus W=\{k_1,\cdots,k_r\}\).

Substituting \(x\) for every indeterminate gives the characteristic polynomial of the Laplacian:

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

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

Proof

It suffices to show that its determinant is zero. As in the proofs of Theorems 4 and 5, take \(W=[n]\) (the set of roots is empty). Then the determinant should equal the number of root-oriented forests with zero trees. There are none, so the determinant is zero.

Corollary 3

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

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

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

A \(k\)-spanning forest of a graph is a spanning subgraph that has \(k\) connected components and no cycle.

Corollary 4

Let \(\mathcal T_k(G)\) be the set of \(k\)-spanning forests of an undirected graph \(G\), and let \(P(x)=\det(xI-L(G))\) be the characteristic polynomial of its Laplacian. 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 numbers of vertices of the connected components of the forest \(T\). In particular, when \(k=1\) we have \(Q(T)=n\), so

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

As in the proof of Corollary 2, we can apply Corollary 3 directly. Every root-oriented forest of the directed graph that consists of \(k\) trees corresponds to a \(k\)-spanning forest of the undirected graph. But a \(k\)-spanning forest \(T\) has \(Q(T)\) ways to choose its roots, so it arises from \(Q(T)\) root-oriented forests of the directed graph.

Applications

Cayley's formula

Corollary 5 (Cayley)

There are \(n^{n-2}\) labeled unrooted trees of size \(n\).

Proof

Equivalently, we show that the complete graph on \(n\) vertices has \(n^{n-2}\) spanning trees. Write down its Laplacian

\[ 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}. \]

Any of its principal minors evaluates to

\[ \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}. \]

The claim follows from Theorem 1.

The BEST theorem

Prerequisite reading: Eulerian graphs

This theorem relates the number of Eulerian circuits of a directed Eulerian graph to the number of its root-oriented arborescences, and so solves the problem of counting Eulerian circuits in a directed graph. Note that counting Eulerian circuits in an arbitrary undirected graph is #P-complete.

To implement the algorithm, first check that the given graph is Eulerian and remove all vertices of degree zero. Then build the graph, count its root-oriented arborescences, and obtain the number of Eulerian circuits from the BEST theorem. If the circuits to be counted must start at a given vertex, multiply the answer by the out-degree of that vertex, which amounts to enumerating the first edge of the circuit.

The proof of the BEST theorem needs the following fact.

Property (when a directed graph has an Eulerian circuit)

A directed graph has an Eulerian circuit if and only if its vertices of nonzero degree are strongly connected and every vertex has equal in-degree and out-degree.

In an Eulerian graph the out-degree and the in-degree are equal, so we drop the superscript and write \(\mathrm{deg}(v)\). The BEST theorem reads as follows.

Theorem 6 (BEST theorem)

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

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

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

Proof

The idea is to set up a correspondence between Eulerian circuits that start at \(k\) on one side, and root-oriented arborescences rooted at \(k\) together with orderings of the outgoing edges at each vertex on the other. Once the circuit is required to start at \(k\), the count to be proved is

\[ \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 comes from the following construction. From an Eulerian circuit that starts at \(k\), the order in which its edges appear determines

  • a root-oriented arborescence rooted at \(k\), formed by the last outgoing edge at every non-root vertex, which accounts for \(t^\mathrm{root}(G,k)\),
  • an ordering of all outgoing edges at the root \(k\), which accounts for \(\mathrm{deg}(k)!\), and
  • an ordering of all outgoing edges other than the last one at each non-root vertex \(v\neq k\), which accounts for \((\mathrm{deg}(v)-1)!\).

We now show that the map defined by this construction is a bijection.

In one direction, given an Eulerian circuit, we must show that the last outgoing edges at the non-root vertices form a root-oriented arborescence. By construction every non-root vertex has exactly one outgoing edge in the tree, so it is enough to show that these edges do not form a cycle. Order the vertices by their last appearance in the Eulerian circuit. Then the last outgoing edge of a non-root vertex must point to a vertex that comes strictly later in this order. If there were a cycle, it would contain a vertex that comes last in the order among its vertices. Being on the cycle, that vertex points to a vertex that does not come later, which contradicts the previous sentence. So the last outgoing edges of the non-root vertices do form a root-oriented arborescence.

In the other direction, given any root-oriented arborescence and orderings of the remaining outgoing edges, we can recover an Eulerian circuit from which the construction above produces exactly that arborescence and those orderings. Start at the root \(k\). On each arrival at a vertex, leave along the first edge in that vertex's given ordering that has not been used yet. If every edge in the ordering at that vertex has been used, leave along the vertex's outgoing edge in the root-oriented arborescence. The graph is Eulerian, so every vertex has equal in-degree and out-degree. Hence the process cannot stop at a non-root vertex, and the walk obtained is indeed a circuit. To prove that it is a valid Eulerian circuit, it remains to show that the process traverses every edge.

Suppose it does not. Then some outgoing edge of some vertex \(v\) is never traversed. Consider \(v\). It cannot be the root: the process ends at the root, and an unused outgoing edge at the root would contradict the fact that it ended. So \(v\) is not the root. By the process described above, whenever a non-root vertex \(v\) has any outgoing edge left, its outgoing edge \(e\) in the tree is left. Write \(e=(v,u)\). Some incoming edge of \(u\) is then never traversed, and since the out-degree of \(u\) equals its in-degree, some outgoing edge of \(u\) is never traversed either. We can now examine the vertex \(u\) in the same way. This argument has moved our attention from \(v\) to \(u\), one step along the root-oriented arborescence towards its root. By induction, some outgoing edge of the root \(k\) is never traversed. We have already seen that this is impossible, a contradiction. So the walk of the previous paragraph is indeed a valid Eulerian circuit.

One can check that both maps are injective, so both are bijections. This proves the theorem.

Implementation

Write down the Laplacian of the graph, delete one row and one column, and compute the determinant of the resulting matrix. The determinant can be computed by Gaussian 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 \]

Gaussian elimination solves this in \(O(n^3)\) time.

Implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
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--;  // delete one row
    this->m--;  // delete one column
  }

  double gauss() {
    double ans = 1;
    for (int i = 0; i < n; i++) {
      int sid = i;
      for (int j = i + 1; j < n; j++)
        if (abs(mat[j][i]) > abs(mat[sid][i])) sid = j;
      if (abs(mat[sid][i]) <= eps) return 0;
      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 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 straightforward application of the matrix tree theorem. Treat every empty room as a vertex and build the graph from the input. Once you have the Laplacian \(L\), delete row \(i\) and column \(i\) for any \(i\) and compute the determinant of this minor. To compute the determinant, reduce the matrix to an upper triangular matrix by Gaussian elimination and multiply the diagonal entries. The elimination has to be carried out over \(\mathbb{Z}/10^9\mathbb{Z}\), which can be done with the Euclidean algorithm.

Example 2: [FJOI2007] Wheel Virus

Solution This problem has many solutions; the matrix tree theorem is the most direct one. For input \(n\), the Laplacian, of order \(n+1\), is easy to write down:

\[ 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 one of its minors of order \(n\). All that remains is arbitrary-precision arithmetic.

Example 2+

Strengthen the constraints of Example 2 to \(n\leq 100000\), with the answer taken modulo 1000007. (Solving this problem takes some linear algebra.)

Solution Derive a recurrence and evaluate it by matrix exponentiation.

The recurrence is derived as follows:

The matrix obtained from \(L_n\) by deleting row 1 and column 1 is very regular, so what we want is 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} \]

Expanding the determinant of \(M_n\) along the first column gives

\[ \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 by \(d_{n-1}, a_{n-1}, b_{n-1}\).
Since \(d_n\) is a tridiagonal determinant, a similar expansion gives the recurrence \(d_n=3d_{n-1}-d_{n-2}\). Expanding in the same way also gives \(a_{n-1}=-d_{n-2}-1\) and \((-1)^n b_{n-1}=-d_{n-2}-1\).
Substituting these into the expansion above gives:

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

This suggests that \(\det M_n\) also satisfies an inhomogeneous second-order linear recurrence. The method of undetermined coefficients gives the final recurrence

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

Rewrite it as \((\det M_n+2) = 3(\det M_{n-1}+2) - (\det M_{n-2} + 2)\) and compute the answer by matrix exponentiation.

Example 3: [BZOJ3659] WHICH DREAMED IT

Solution This is a direct application of the BEST theorem, with one catch. The statement says that two ways of completing the task are different if and only if the keys are used in a different order, so for each Eulerian circuit you may leave room 1 along any of its outgoing edges, and the answer must also be multiplied by the out-degree of room 1.

Example 4: [Joint Provincial Team Selection 2020 A] Homework Problem

Solution First use Möbius inversion to reduce the problem to computing the sum of edge weights over all spanning trees; this step has little to do with this article, so we skip it.

Write the entries of the determinant in the form \(w_ix+1\); the answer is the coefficient of the linear term of the determinant. The answer is really the sum, over every choice of one fixed edge, of the number of spanning trees containing that edge \(\times\) its weight, and the fixed edge is the one whose linear coefficient is multiplied in. Terms of degree higher than one can be dropped, so this takes \(O(n^3)\) time.

[Beijing Provincial Team Selection Training 2019] Counting Spanning Trees is a more general case: compute the sum over spanning trees of the \(k\)-th power of the sum of the tree's edge weights. Build the entries of the determinant in a similar way; see the Luogu solutions for details.

Example 5: AGC051D C4

Solution Counting Eulerian circuits in an undirected graph is #P-complete, but the graph in this problem is simple enough. Once you fix how many of the \(S-T\) edges point from \(S\) to \(T\), the orientations of the other three edges are determined, and applying the BEST theorem directly gives an \(O(a+b+c+d)\) solution.