XXV OBM

Let's count the number of ordered pairs $(f,D)$, where $f$ is a labeling of vertices and $D$ a possible set of differences of labels of vertices joined by an edge. Note that an ordered pair $(f,D)$ determines at most one great graph, since the labeling $f$ determine the vertices and the set of differences $D$ determine the edges of the graph (we join two vertices if and only if the difference between their labels is in $D$), unless there is some contradiction among the differences. In the latter case $(f,D)$ determines no great graph. There are $\frac{\lfloor \frac{n^2}{4}\rfloor !}{\left(\lfloor \frac{n^2}{4}\rfloor -n\right)!}\le {\left(\frac{n^2}{4}\right)}^n$ labelings and since $D\subset \{1,2,\dots ,\lfloor \frac{n^2}{4}\rfloor \}$, there are $2^{\lfloor \frac{n^2}{4}\rfloor }\le 2^{\frac{n^2}{4}}$ possibilities for $D$. Thus the number of ordered pairs (and, henceforth, the number of great graphs with $n$ vertices) is not greater than ${\left(\frac{n^2}{4}\right)}^n\cdot 2^{\frac{n^2}{4}}$. But the number of graphs with $n$ vertices is $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}=2^{\frac{n(n-1)}{2}}$. Therefore it suffices to show that for sufficiently large $n$ $${\left(\frac{n^2}{4}\right)}^n\cdot 2^{\frac{n^2}{4}}<2^{\frac{n(n-1)}{2}}$$ Taking logarithms on both sides, $$n\cdot {\log }_2\frac{n^2}{4}+\frac{n^2}{4}<\frac{n^2}{2}-\frac{n}{2}⟺2{\log }_2\left(\frac{n}{2}\right)<\frac{n}{4}-\frac{1}{2}$$ which is true for sufficiently large $n$, since log grows slower than any polynomial with degree at least 1 and positive leader coefficient (it is true, indeed, for $n>33$).