On the girth of extremal graphs without shortest cycles

Let EX(ν;{C3,…,Cn})EX(ν;{C3,…,Cn}) denote the set of graphs GG of order νν that contain no cycles of length less than or equal to nn which have maximum number of edges. In this paper we consider a problem posed by several authors: does GG contain an n+1n+1 cycle? We prove that the diameter of GG is at most n−1n−1, and present several results concerning the above question: the girth of GG is g=n+1g=n+1 if (i) ν≥n+5ν≥n+5, diameter equal to n−1n−1 and minimum degree at least 3; (ii) ν≥12ν≥12, ν∉{15,80,170}ν∉{15,80,170} and n=6n=6. Moreover, if ν=15ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3ν≥2n−3 and n≥7n≥7 the girth is at most 2n−52n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋ν≤n+1+⌊(n−2)/2⌋.