# Total weight of all spanning trees

Given a weighted simple undirected connected graph $$G = (V, E, w:E \to \mathbb{R})$$, let $$\tau(G)$$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with high probability the number

$$W = \sum_{\mathcal{T} \in \tau(G)} \sum_{e \in E(\mathcal{T})} w(e)$$

without actually enumerating all the spanning trees? Are there asymptotic estimates on this number?

• For each $e$, it suffices to count in how many spanning trees it pparticipates. For that, you merge endpoints of $e$ and find the number of spanning trees in the resulting graph. en.wikipedia.org/wiki/Kirchhoff%27s_theorem may work (as I understand from the proof outline, you should find the determinant of minor $M_{11}$ of the Laplacian) (note that you'll need a multigraph version). Maybe this answer can also be useful. – Dmitry Aug 26 '20 at 15:05
• @Dmitry thanks! I will accept that as the answer if you post it. – abhi01nat Aug 28 '20 at 8:13