Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 209 / 4 / b / Solution

The reduced graph Laplacian is $L^{(0)}=\Delta (I-P^{(0)})$. By the matrix-tree theorem, the number $\tau (D)$ of spanning trees isCombining this with part (a) givesThis is also the normalization behind Wilson algorithm: loop-erased random walks attach the vertices successively, and the order-independent product ensures that every rooted spanning tree has probability $1/\tau (D)$.