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

Root the graph at $x_0$ and let $P^{(0)}$ be the transition matrix of simple random walk killed on hitting $x_0$, indexed by the remaining vertices. Its Green matrix is $G=(I-P^{(0)}{)}^{-1}$. Successively eliminating vertices in an order $x_1,\dots ,x_n$ takes Schur complements; the corresponding diagonal pivot at step $j$ is exactly $g_{D\setminus \{x_0,\dots ,x_{j-1}\}}(x_j)$. The product of the pivots is thereforewhich is invariant under the elimination order.

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)$.