= Solution
For edge weights $w_{ij}$, form the out-Laplacian
$$
L_{ij}=\begin{cases}
\sum_{k\ne i}w_{ik},&i=j,\\
-w_{ij},&i\ne j.
\end{cases}
$$
The directed <matrix-tree theorem> states that the cofactor $\det L^{(r)}$, obtained by deleting row and column $r$, equals the sum of $\prod_{e\in T}w_e$ over directed spanning trees oriented towards $r$.
Expand the determinant by permutations, and in each diagonal entry expand the sum of outgoing edge weights. A term chooses one outgoing edge at every vertex other than $r$. If the resulting functional digraph contains a directed cycle, sign-reversing inclusion-exclusion over its cycles cancels the term. The surviving choices are precisely the acyclic ones; every vertex then reaches $r$, so they are rooted directed spanning trees, each with positive sign and its product weight. This proves the theorem.
Back to article page
