2020/01/31 by Qiao, Pu, Zhan, Xingzhi
#05C30 #05C35 #05C75 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2001.11723
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 \rm 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 \rm ex(n,H)+1 edges contains at least two Hs? Perhaps this is always true." We solve the second part of this problem in the negative by proving that for every integer k≥ 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 C4 the 4-cycle. We also prove that for every integer n with 6≤ n≤ 11, there exists a graph of order n and size \rm ex(n,C4)+1 which contains exactly one copy of C4, but for n=12 or n=13, the minimum number of copies of C4 in a graph of order n and size \rm ex(n,C4)+1 is 2.