[Math] How many non-isomorphic graphs of 50 vertices and 150 edges

graph theory

Is there an way to estimate (if not calculate) the number of possible non-isomorphic graphs of 50 vertices and 150 edges?

Best Answer

The simplest guess one could make is $\frac{1}{50!} { {50 \choose 2} \choose 150}$. That is, we first count the number of labeled such graphs, then assume that most of them have trivial automorphism group so we can approximately divide out by $50!$ when removing the labels. You can estimate how big this is using Stirling's formula.

Edit: Actually, you can also just ask WolframAlpha to compute this estimate. You get $7.028... \times 10^{131}$, which is apparently within 1% of the true answer according to Brendan McKay.