What is the maximum number of simple graphs possible with $n$ vertices and $m$ edges?

The number of edges possible in a simple graph with $n$ vertices would be ${n \choose 2}$. So the total number of possible graphs would involve the total number of subsets possible out of this which would be ${2^{n \choose 2}}$. Now we are restricted to selecting graphs which have only $m$ number of edges. How do I calculate this?

  • $\begingroup$ See here: math.stackexchange.com/questions/1072726/… $\endgroup$ – Rohan Dec 14 '16 at 7:22
  • 2
    $\begingroup$ You have $\binom{n}{2}$ locations where edges can be. To have $m$ edges, you need to pick which $m$ of the $\binom{n}{2}$ locations actually have edges. There are then $\binom{\binom{n}{2}}{m}$ labeled graphs with $n$ vertices and $m$ edges. $\endgroup$ – JMoravitz Dec 14 '16 at 7:39

Your Answer

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

Browse other questions tagged or ask your own question.