On the structure of extremal graphs of high girth

Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1‐cycle? In this paper we establish some properties of extremal graphs and present several results where this question is answered affirmatively. For example, this is always the case for (i) v ≥ 8 and n = 5, or (ii) when v is large compared to n : v ≥ $2^{a^{2}+a+1}n^{a}$ , where a = n ‐ 3 ‐ $\lfloor{n-2}\over{4}\rfloor$ , n ≥ 12. On the other hand we prove that the answer to the question is negative for v = 2 n + 2 ≥ 26. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 147–153, 1997