Matrix-tree theorem
= Matrix-tree theorem
{wiki=Kirchhoff's_theorem}
The matrix-tree theorem expresses the weighted number of <spanning trees> of a finite <graph> as a cofactor of its <graph Laplacian>. For a directed graph with out-Laplacian $L$, deleting the row and column indexed by a root $r$ gives
$$
\det L^{(r)}=\sum_T\prod_{e\in T}w_e,
$$
where the sum runs over <directed spanning trees> rooted towards $r$.