Strong Subgraph-Count Stability in $C_{2\ell +1}$-Free Graphs

Abstract

Starting from the stability theorem of Erdős and Simonovits, stability problems for graphs forbidding a fixed subgraph have been studied in terms of edge numbers, spectral radii and subgraph counts. Let $\mathcal{N}(F,G)$ denote the number of unlabeled copies of $F$ in $G$. It is known that, for every fixed path $P_t$ and even cycle $C_{2a}$, the maximum number of copies in an $n$-vertex $C_{2\ell +1}$-free graph is attained by the bipartite Turán graph $T_{n,2}$. In this paper we obtain strong structural stability for $C_{2\ell +1}$-free graphs in terms of copies of paths and even cycles. For fixed $\ell \ge 2$ and $3\le r\le 2\ell -1$, we show that if an $n$-vertex $C_{2\ell +1}$-free graph contains at least as many copies of $P_t$ or $C_{2a}$ as the corresponding suspended extremal construction, then it has the corresponding suspension structure. This gives exact high-chromatic extremal theorems for paths and even cycles. We also prove a counting theorem for nearly complete bipartite graphs. It shows that, for every fixed matching-admissible connected bipartite graph $F$, both imbalance between the two parts and missing cross-edges decrease the number of copies of $F$ by a term with a specified main coefficient. This theorem is independent of the forbidden odd cycle and converts subgraph-count assumptions into the edge bounds needed for the structural theorem.