= Solution
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$ with
$$
\boxed{\mathbb P(T=t)=\frac1{|\mathcal T(G)|}\quad\text{for each }t\in\mathcal T(G).}
$$
Every <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.
Back to article page
