Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How many trees in a graph?

  1. Aug 10, 2015 #1
    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)
  2. jcsd
  3. Aug 15, 2015 #2
    Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
  4. Aug 15, 2015 #3
    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook