I have posted this question on Mathematics, but unfortunately no luck so far.
Let $\mathcal{G}$ be the family of simple connected graphs on $n$ vertices, where each graph has more than $m$ edges, and the maximal degree is less than $\frac{n-1}{2}$. We can assume that m is large, i.e., $m \geq c\frac{n(n-1)}{2}$ for some $0 < c <0.5$.
I don't need a specific formula, but rather a bound on the number of graphs. Can it be that $|\mathcal{G}| \in O(2^{C\binom{n}{2}})$ for some $0 < C < 1$? Or is this claim false?
I know that almost all of the possible $2^{\binom{n}{2}}$ are connected (see the answer here). And that for $c = 0.5$ we have a bound a bit less than $\frac{1}{2}2^{\binom{n}{2}}$. So there is not much hope in the multiplicative edge constant. But, maybe something can be done with the fact that for each $i \in [n]:=\{1,\ldots,n\}$ we have $\deg(i)\leq \frac{n-1}{2}$.
Maybe there is some literature you can refer me to.
