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

For edge weights $w_{ij}$, form the out-LaplacianThe 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.