Nearly bipartite graphs Original Research Article

We prove that if a nonbipartite graph G on n vertices has minimal degree δ⩾n/(4k+2)+ck,m, where ck,m does not depend on n and n is sufficiently large, if C2s+1⊂G for some k⩽s⩽4k+1 then C2s+2j+1⊂G for every j=1,…,m. We give a structural description of all graphs on n vertices with δ⩾n/(4k+2) and not containing odd cycles of order larger than 2k+1 and show that they can be made bipartite by deletion of a fixed number of edges or vertices. Such graphs will be called nearly bipartite graphs.