On extremal numbers of the triangle plus the four-cycle

Abstract For a family $\mathcal {F}$ of graphs, let ${\mathrm {ex}}(n,\mathcal {F})$ denote the maximum number of edges in an n -vertex graph which contains none of the members of $\mathcal {F}$ as a subgraph. A longstanding problem in extremal graph theory asks to determine the function ${\mathrm {ex}}(n,\{C_3,C_4\})$ . Here we give a new construction for dense graphs of girth at least five with arbitrary number of vertices, providing the first improvement on the lower bound of ${\mathrm {ex}}(n,\{C_3,C_4\})$ since 1976. As a corollary, this yields a negative answer to a problem in Chung-Graham [3].