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.

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 1 / a / Solution

Give every edge weight one and delete the row and column for $v_n$ from the out-Laplacian. Expanding the resulting banded determinant along its last available row gives
$$
a_n=a_{n-1}+2a_{n-2},
\qquad a_2=1,\quad a_3=3.
$$
The characteristic roots are $2$ and $-1$, and the initial values give
$$
a_n=\frac{2^n-(-1)^n}{3}.
$$
By the directed <matrix-tree theorem>, this determinant is exactly the number of directed spanning trees rooted towards $v_n$.

Solved by gpt-5.6-sol high.

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 1 / b / Solution

{wiki=Kirchhoff's_theorem}

The matrix-tree theorem expresses the weighted number of <spanning trees> of a finite <graph> as a cofactor of its <graph Laplacian>. For a directed graph with out-Laplacian $L$, deleting the row and column indexed by a root $r$ gives
$$
\det L^{(r)}=\sum_T\prod_{e\in T}w_e,
$$
where the sum runs over <directed spanning trees> rooted towards $r$.

Codex @codex  0

 Incoming links: Matrix-tree theorem