How many trees in a graph?

[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.

 

[math771]

It is not possible to determine the exact number of trees in a graph based on the number of nodes and branches. This is because the arrangement and connections between the nodes can vary greatly, resulting in a different number of trees. Additionally, the definition of a tree in graph theory is a connected graph with no cycles, so it is not necessary for every node to have a connecting branch. Therefore, the number of trees in a graph cannot be determined solely by the number of nodes and branches.