On a problem of Erdős about graphs whose size is the Turán number plus one

Abstract

We consider finite simple graphs. Given a graph $H$ and a positive integer $n,$ the Turán number of $H$ for the order $n,$ denoted $\mathrm{ex}(n,H),$ is the maximum size of a graph of order $n$ not containing $H$ as a subgraph. Erdős posed the following problem in 1990: "For which graphs $H$ is it true that every graph on $n$ vertices and $\mathrm{ex}(n,H)+1$ edges contains at least two $H$s? Perhaps this is always true." We solve the second part of this problem in the negative by proving that for every integer $k\ge 4,$ there exists a graph $H$ of order $k$ and at least two orders $n$ such that there exists a graph of order $n$ and size $\mathrm{ex}(n,H)+1$ which contains exactly one copy of $H.$ Denote by $C_4$ the $4$-cycle. We also prove that for every integer $n$ with $6\le n\le 11,$ there exists a graph of order $n$ and size $\mathrm{ex}(n,C_4)+1$ which contains exactly one copy of $C_4,$ but for $n=12$ or $n=13,$ the minimum number of copies of $C_4$ in a graph of order $n$ and size $\mathrm{ex}(n,C_4)+1$ is $2.$

16 pages, 6 figures