On a problem of ErdH{o}s about graphs whose size is the Tur{a}n number plus one


Abstract in English

We consider finite simple graphs. Given a graph $H$ and a positive integer $n,$ the Tur{a}n number of $H$ for the order $n,$ denoted ${rm ex}(n,H),$ is the maximum size of a graph of order $n$ not containing $H$ as a subgraph. ErdH{o}s posed the following problem in 1990: For which graphs $H$ is it true that every graph on $n$ vertices and ${rm 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 $kge 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 ${rm 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 $6le nle 11,$ there exists a graph of order $n$ and size ${rm 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 ${rm ex}(n,C_4)+1$ is $2.$

Download