A graph $G$ is called $C_{ 2k+1}$-free if it does not contain any cycle of length $2k+1$. In 1981, Haggkvist, Faudree and Schelp showed that every $n$-vertex triangle-free graph with more than $\frac{ (n-1)^2}{ 4}+1$ edges is bipartite. In this paper, we extend their result and show that for $1\leq t\leq 2k-2$ and $n\geq 318t^2k$, every $n$-vertex $C_{ 2k+1}$-free graph with more than $\frac{ (n-t-1)^2}{ 4}+\binom{ t+2}{ 2}$ edges can be made bipartite by either deleting at most $t-1$ vertices or deleting at most $\binom{ \lfloor\frac{ t+2}{ 2}\rfloor}{ 2}+\binom{ \lceil\frac{ t+2}{ 2}\rceil}{ 2}-1$ edges. The construction shows that this is best possible.
Categories: math.CO