Let $\alpha>1$ be a constant and define $B\_n$ as the number of (labeled) *balanced* graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper [Strongly Balanced Graphs
and Random Graphs](https://people.clas.ufl.edu/avince/files/StronglyBalanced.pdf "Ruciński, A. and Vince, A. (1986). J. Graph Theory, 10: 251-264. doi:10.1002/jgt.3190100214. zbMATH review at https://zbmath.org/?q=an:0651.05057") by A. Ruciński and A. Vince implies that $B\_n\geq1$. What better lower bounds are known? In particular, is it known to be bounded from below by $n^{(1+o(1))\alpha n}$?


Edit: adding a definition of balanced graphs. The *density* of a graph $G$ with $v$ vertices and $e$ edges is $$\mathrm{den}(G)=\frac{e}{v}$$
A graph $G$ is *balanced* if $\mathrm{den}(G)\geq \mathrm{den}(H)$ for every subgraph $H$ of $G$. Balanced graphs appear naturally when counting copies of a given graph in the random graph, as explained in the paper I referred to.



Lower bound on the number of balanced graphs
The bound of Ruciński and Vince is for *strongly balanced*, which is a more strict condition. If only *balanced* is required, the example of connected regular graphs provides a bound much greater than $n^{\Omega(n)}$.


The total number of regular graphs with $n$ vertices is
$$\alpha(n) \frac{2^{n^2/2}\sqrt{2e}}{\pi^{n/2} n^{n/2}},$$
where $\alpha(n)$ is a constant depending on $n\pmod{4}$.


B. D. McKay and N. C. Wormald, [Asymptotic enumeration by degree sequence of graphs of high degree](https://www.sciencedirect.com/science/article/pii/S019566981380042X), European J. Combin., 11 (1990) 565-580.


Note that the formula is stated for all regular graphs, not necessarily connected, but the vast majority of regular graphs are connected. (All degrees apart from 0,1,2 guarantee almost sure connectivity.)


