We consider the minimum degree stability of graphs forbidding odd cycles: What is the tight bound on the minimum degree to guarantee that the structure of a ‐free graph inherits from the extremal graph (a balanced complete bipartite graph)? Andrásfai, Erdős, and Sós showed that if a ‐free graph on vertices has minimum degree greater than , then it is bipartite. Häggkvist showed that for , if a ‐free graph on vertices has minimum degree greater than , then it is bipartite. Häggkvist also pointed out that this result cannot be extended to . In this paper, we give a complete answer for any . We show that if and is an ‐vertex ‐free graph with , then is bipartite, and the bound is tight.
No takes yet. Share an insight, caveat, or question.
Yuan et al. (2024) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: