directed matrix tree theorem

Statement

Let $G = (V, E)$ be a directed graph with vertices labeled $1, \dots, n$ . For any root $r$ and $k \in [n]$ , the number of arborescences of $G$ with root $r$ is equal to the cofactor $L^{k r}$ ( $L$ , the Laplacian (Kirchoff) matrix with the $k$ th row and $r$ th column removed).

Proof

We shall proceed via induction on $| E |$ .

Base case: $G$ contains only edges ending at root $r$ . Then, there are no arborescences, and on the other hand, $L$ will only have nonzero entries on the $r$ th column. When we remove it, we'll have the zero matrix and get a determinant of 0.

Inductive case: For any $i$ , pick some edge $i \overset{e}{\to} j$ where $j \neq r$ . Construct $G_{1}$ to be $G$ without the edge $e$ and $G_{2}$ to be $G$ with all edges $f \neq e$ that end at $j$ deleted. Note that

{Arb}_{r} (G) = {Arb}_{r} (G_{1}) + {Arb}_{r} (G_{2})

as any arborescence of $G$ must have a path from $r \to j$ , and so $j$ must have an in-edge. It is either $e$ (then it would be an arborescence of $G_{2}$ ) or it isn't (arborescence of $G_{1}$ ).

On the other hand, since these graphs are obtained only by augmenting edges that end at $j$ , $L_{G_{1}}, L_{G_{2}}$ differ from $L_{G}$ only at the $j$ th column. Furthermore, the sum of the $j$ th columns of the smaller graph is that of $G$ . So, $L_{G}^{k r} = L_{G_{1}}^{k r} + L_{G_{2}}^{k r}$ by linearity of the determinant.

To apply the inductive hypothesis, we note that $G_{1}$ always has less edges than $G$ . We are done if $G_{2}$ has less edges than $G$ . In the case where there are no other edges to $j$ (ie. ${indeg}_{G} (j) = 1$ ) we may pick another edge in place of $e$ and $j$ . If all vertices (except $r$ , but any edge that ends at $r$ will not contribute to an arborescence so we may effectively remove them and assume that this holds for all vertices of the graph) has indegree 1. In particular, we may assume that this graph has exactly $n - 1$ edges, in which it falls in the following two cases:

If $G$ is an arborescence, then ${Arb}_{r} (G) = 1$ and by the key lemma from Kirchoff's matrix tree theorem, we may conclude that $L^{r k} = 1$ as well.
If $G$ is not an arborescence, it has a directed cycle. There are no arborescences, and by a similar argument as in the undirected case, the determinant of the minors will be 0 (because of the cycle).

Example

Suppose we have the following graph:
Pasted image 20260430130201.png|300
If we picked the marked edge $e$ , then our resulting graphs $G_{1}$ and $G_{2}$ would be
Pasted image 20260430130250.png|550