# The probability that two graphs have same number of edges

Maybe this question is off topic or duplicate, but maybe there is some information which I am not aware of.

Let $G_n$ denote the set of non-isomorphic simple graphs and $|G_n|=g_n$. Also, let $U_{n,m}$ denote the set of non-isomorphic simple graphs with $n$ vertices and $m$ edges, and $|U_{n,m}|=u_{n,m}$. I am interested in the below limit:

$$\lim_{n\rightarrow \infty}{T_n=\frac{\sum\limits_{m=1}^{\binom{n}{2}}{\binom{u_{n,m}}{2}}}{\binom{g_n}{2}}}.$$

The sequence $T_n$ shows the probability that two graphs among graphs with $n$ vertices have the same number of edges. Is it possible that the above limit exists and is not equal to zero?

Maybe this observation helps to see something. We have $$u_{n,1}+\cdots+u_{n,\binom{n}{2}}=g_n,$$

so, $$\binom{u_{n,1}}{2}+\cdots+\binom{u_{n,\binom{n}{2}}}{2}=\binom{g_n}{2}-\sum\limits_{1\leq i<j\leq \binom{n}{2}}{u_{n,i}u_{n,j}}.$$

Therefore, we can write $T_n$ as follows

$$T_n=1-\frac{\sum\limits_{1\leq i<j\leq \binom{n}{2}}{u_{n,i}u_{n,j}}}{\binom{g_n}{2}}.$$

Some numerical results: $T_4=0.09090909091, T_5=0.1051693405, T_6=0.1055417701, T_7= 0.09997318375,$ $T_8=0.09345209613, T_9=0.08721068637, T_{10}=0.08077014830$.

Since the vast majority graphs has trivial groups, and this is even more true (to exponential precision) for graphs with likely numbers of edges, the answer will be the same if you consider labelled graphs. This makes it a simple exercise if you know the identity $$2^{-2N} \sum_{i=0}^N \binom Ni^2 = \frac{\Gamma(N+\frac12)}{\sqrt{\pi}\,N!}.$$
I get $$\frac{\sqrt{2}}{\sqrt{\pi}\,n} + O(n^{-2}).$$
• @ShahroozJanbaz, to predict the $1/n$ decay (and hence limit $0$) without doing any computation you can use the fact that a random graph has binomial $B(\binom n 2, 1/2)$ edges, which is (i) concentrated in an interval of length order $1/n$ about its mean and (ii) does take values at either end of the range fairly often. So very roughly you are looking for the probability that two random choices from a set of size $n$ agree, which is of order $1/n$. – Ben Barber May 26 '17 at 13:20
• [length order $1/n$ $\mapsto$ length order $n$] – Ben Barber Jun 3 '17 at 9:55