We show that variants of spectral sparsification routines can preserve the total spanning tree
counts of graphs. By Kirchhoff's matrix-tree theorem, this is equivalent to preserving the
determinant of a graph Laplacian minor or, equivalently, of any symmetric diagonally
dominant matrix (SDDM). Our analyses utilize this combinatorial connection to bridge the
gap between statistical leverage scores/effective resistances and the analysis of random
graphs by Janson Combin. Probab. Comput., 3 (1994), pp. 97--126. This leads to a routine …

We show variants of spectral sparsification routines can preserve the total spanning tree
counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a
graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilizes this
combinatorial connection to bridge between statistical leverage scores/effective resistances
and the analysis of random graphs by [Janson, Combinatorics, Probability and
Computing94]. This leads to a routine that in quadratic time, sparsifies a graph down to …