The number of $C_4$-free graphs

Abstract

Erdős, Frankl and Rödl showed that the number of graphs on $n$ vertices with no copy of a non-bipartite graph $H$ is $2^{(1+o(1))ex(n,H)}$, whereas Morris and Saxton showed that this fails for $C_6$. Answering a question of Erdős, we prove that the number of $C_4$-free graphs on $n$ vertices is $2^{(1+o(1))ex(n,C_4)}$. The proof combines a modified hypergraph container method that treats pairs of vertices with large codegree separately, with a new bound on the number of matchings in a graph.