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.