5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.