Problem Statement
Is it true that the number of graphs on $n$ vertices which do not contain $G$ is\[\leq 2^{(1+o(1))\mathrm{ex}(n;G)}?\]
Categories:
Graph Theory Turan Number
Progress
If $G$ is not bipartite the answer is yes, proved by Erdős, Frankl, and Rödl [EFR86]. The answer is no for $G=C_6$, the cycle on 6 vertices. Morris and Saxton [MoSa16] have proved there are at least\[2^{(1+c)\mathrm{ex}(n;C_6)}\]such graphs for infinitely many $n$, for some constant $c>0$. It is still possible (and conjectured by Morris and Saxton) that the weaker bound of\[2^{O(\mathrm{ex}(n;G))}\]holds for all $G$.Source: erdosproblems.com/59 | Last verified: January 13, 2026