Extremal Numbers for Odd Cycles

Source abstract

We describe the C 2 k +1 -free graphs on n vertices with maximum number of edges. The extremal graphs are unique for n ∉ {3 k − 1, 3 k , 4 k − 2, 4 k − 1}. The value of ex ( n , C 2 k +1 ) can be read out from the works of Bondy [3], Woodall [14], and Bollobás [1], but here we give a new streamlined proof. The complete determination of the extremal graphs is also new. We obtain that the bound for n 0 ( C 2 k +1 ) is 4 k in the classical theorem of Simonovits, from which the unique extremal graph is the bipartite Turán graph.