How Many Spanning Trees Can a Graph Have?

[Marvin94]

How many trees are in a graph if the number of nodes and the number of branches (or meshes) is given? I refer to the trees which has to "walk" through the nodes along the given branches (so no tree between 2 nodes without a connecting branch between them)

 

[jbstemp]

I don't think there is a way to count the number of spanning trees of a graph if you only have the number of nodes and branches.

However, If you are able to label the vertices and edges of a graph then there is the "deletion-contraction" theorem which says that the number of spanning trees of a graph, G, is equal to the number of spanning trees of G by deleting an edge plus the number of spanning trees of the G by contracting an edge. From there, it's clear to see that you can recursively apply this theorem until you end up with a bunch of small graphs with trees that you can count easily. Another method is to calculate any cofactor of the graph's laplacian matrix (https://en.wikipedia.org/wiki/Laplacian_matrix), but again to do so you must be able to label the graph.

I hope this helps a bit.