Girth of {C3,…,Cs}-free extremal graphs

AbstractLet G be a {C3,…,Cs}-free graph with as many edges as possible. In this paper we consider a question studied by several authors, the compulsory existence of the cycle Cs+1 in G. The answer has already been proved to be affirmative for s=3,4,5,6. In this work we show that the girth of G is g(G)=s+1 when the order of G is at least 1+s(s−22)s−2−4s−4 if s is even, and 1+(s−1)3((s−2)2−14)s−32−8s2(s−2)2−10 if s is odd. This bound is an improvement of the best general result so far known. Moreover, we also prove in the case s=7 that the girth is g(G)=8 for order at least 14 and characterize all the extremal graphs whose girth is not 8