AbstractBy using the Szemer´edi Regularity Lemma , Alon and Sudakov recentlyextended the classical Andr´asfai-Erd˝os-S´os theorem to cover general graphs. Weprove, without using the Regularity Lemma, that the following stronger statementis true.Given any (r+1)-partite graph H whose smallest part has t vertices, there existsa constant C such that for any given ε > 0 and sufficiently large n the following istrue. Whenever G is an n-vertex graph with minimum degreeδ(G) >either G contains H, or we can delete f (n, H) 6 Cnt edges from G to obtain anr-partite graph. Further, we are able to determine the correct order of magnitudeof f (n, H) in terms of the Zarankiewicz extremal function...