# How many minimal spanning trees has this particular graph?

I'm counting minimal spanning trees and my suggestion was the following, when I have a graph with 10 vertices and 13 edges:

For a minimal spanning tree I need 1 edge less then vertices, so (10,9). I can choose now 4 edges to be deleted to get a minimal spanning tree. However I have to take care to not disconnect the graph. But I'm missing something. Do I have to take care of 4 or 5 circles in the following example? And how can I compute then the amount of spanning trees? Is there a closed formula (not Prims algorithm)?

It should be mentioned, that the normal edges are weighted twice as the bolded edges.

• Are the edge weights relevant in some way to counting the spanning trees? – Matt Sep 11 '18 at 14:27
• Yes, it should be a minimal spanning tree, therefore the minimal weights. – John Smith Sep 11 '18 at 14:33

So in total there are $9 \times (2+4+2) = 72$ minimal spanning trees.