Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 214 / 4 / a

Let $\mathcal{T}(G)$ be the finite set of spanning trees of the connected graph. A spanning tree has all the graph vertices, is connected, and contains no graph cycle. Connectedness ensures that at least one exists, for example by repeatedly deleting an edge of a graph cycle while retaining connectedness. The uniform spanning tree is the random edge set $T$ withEvery tree has $|V|-1$ edges, so uniformity is over complete trees, not over arbitrary subsets of that size. Such subsets can be disconnected or cyclic and do not belong to $\mathcal{T}(G)$. Nor are indicators of the tree edges generally independent. The matrix-tree theorem gives $|\mathcal{T}(G)|$ as any cofactor of the unweighted graph Laplacian if a numerical normalizing constant is needed.

This definition uses the ordinary undirected unweighted graph convention. With positive conductances the analogous law for spanning trees weights $t$ proportionally to ${\prod }_{e\in t}{c}_e$ and is generally not uniform. When the graph has one graph vertex the empty edge set is the unique spanning tree, so its probability is one.