[Math] Total number of possible graphs in a network with $m$ edges and $n$ vertices

graph theorypermutations

How do you calculate the total number of possible graphs in a network with $m$ undirected edges and $n$ vertices? No self-loops.

For instance, if I have a network with $7$ vertices in it, I want to find how many unique graphs can be made using $10$ total undirected edges between vertices.

Best Answer

This is a combination problem, as the order of the edges doesn't matter.

For an undirected graph with $n$ vertices, there are $\frac{n!}{2!(n-2)!}$ or $\frac{n(n-1)}{2}$ possible edges. You could also say, "$n$ choose $2$" possible edges. Of these possible edges, we are choosing $m$ of these edges. Therefore, there are computing "$n$ choose $2$ choose $m$".

http://www.wolframalpha.com/input/?i=(n+choose+2)+choose+m

In your case, (7 choose 2) choose 10 = 352716

Related Question