Problem #608: Let $G$ be a graph with $n$ vertices and $>n^2/4$ many edges

---

Progress

Erdős, Faudree, and Rousseau [EFR92] proved that any graph on $n$ vertices with $>n^2/4$ edges contains at least $2\lfloor n/2\rfloor+1$ edges in triangles.

Erdős [Er97d] stated that, under the same assumptions, there at least $\frac{2}{9}n^2$ edges of $G$ which are contained in some odd cycle - this is best possible, as witnessed by taking a complete graph on $\lfloor \frac{2n+4}{3}\rfloor$ and a complete balanced bipartite graph on $\lfloor \frac{n+1}{3}\rfloor$ vertices, which overlap on exactly one vertex.

Erdős wrote that a positive answer to this question would follow if we knew that $G$ must contain a triangle such that there at least $n/2-O(1)$ vertices joined to at least two vertices of the triangle. Erdős and Faudree observed that every graph with $2n$ vertices and at least $n^2+1$ edges has a triangle whose vertices are joined to at least $n+2$ vertices.

Erdős, Faudree, and Rousseau [EFR92] ask, more generally, if for any fixed $k\geq 2$ every graph with $n$ vertices and $>n^2/4$ edges contains at least $\frac{2}{9}n^2-O_k(n)$ edges which are contained in a $C_{2k+1}$.

The answer to the original question with $C_5$ is no - Füredi and Maleki (in unpublished work which is described by Grzesik, Hu, and Volec [GHV19]) have constructed graphs with $n$ vertices and $>n^2/4$ edges in which the number of edges contained in a $C_5$ is at most $cn^2+O(n)$ where\[c=\frac{2+\sqrt{2}}{16}\approx 0.2134.\]This is the best possible: Grzesik, Hu, and Volec [GHV19] have proved that a graph on $n$ vertices with $>n^2/4$ edges contains at least $(c-o(1))n^2$ edges in a $C_5$. They further prove the conjecture of Erdős, Faudree, and Rousseau [EFR92] for all $k\geq 3$ (that $>n^2/4$ edges ensures at least $\frac{2}{9}n^2-O(n)$ edges in a $C_{2k+1}$).


See also the entry in the graphs problem collection.