# How many different trees can we form from given graph?

I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$

In this graph I want to count the sub-sets of edges such that each subset will have exactly $N-1$ edges and the edges forming the subset will form connected graph.

Example

Let's say we have the following graph

We can count a total of 3 subsets: {1,2,3,5}, {1,2,3,4}, {1,2,4,5}. Please note the the numbers from 1 to 5 are marking the edges, not the nodes.

What I think

Let's say our graph is complete graph, it is the worse case. If we have 500 nodes and 499 nodes going out from each node, I think that there could be $500^{500}$ possible combinations which is huge number.

• It's not quite as bad, since we're drawing without replacement here. – Raphael Aug 1 '17 at 14:07

There is a simple algebraic algorithm based on the Matrix Tree Theorem. Just make the Laplacian matrix of the graph and compute $N^{-1}$ times the product of its non-zero eigenvalues.