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.
Problems like this typically require a bit of case-work.
Let's view the graph as two triangles connected by three vertical paths.
We need to delete four edges. Since we want minimal spanning trees, we should delete as many high-weight (thin) edges as possible.
However, we have to delete at least one edge from the top triangle and one edge from the bottom triangle. (There are 9 ways to do this.)
The remaining two deletions can be thin edges: We just need to make sure we cut two of the three vertical paths. Depending on which two paths we cut, there are either 2, 4, or 2 ways to do this.
So in total there are $9 \times (2+4+2) = 72$ minimal spanning trees.