Size of graphs with high girth

Abstract

Let n≥4 be a positive integer and let ex (ν;{C3, . . . , Cn}) denote the maximum number of edges in a {C3, . . . , Cn}-free simple graph of order ν. This paper givesthe exact value of this function for all νup to ⌊(16n−15)/5⌋. This result allows usto deduce all the different values of the girths that such extremal graphs can have. Let k≥0 be an integer. For each n≥2 log2(k+ 2) there exists ν such that every extremal graph Gwith e(G)−ν(G) = khas minimal degree at most 2,and is obtained by adding vertices of degree 1 and/or by subdividing a graph or a multigraph Hwith δ(H)≥3 and e(H)−ν(H) = k.