Proof. For each $i\in \mathbb{N}$ , let $B_i$ denote the set of vertices at distance at most $i$ from $u$ . Let

(2) \begin{equation} \gamma = (\delta/12\rho )^{1/(\alpha -1)} \mbox{ and } \mu =\min\!\left \{(1/2) (\delta/2\rho )^{1/(\alpha -1)}, (\delta/4\rho )\gamma ^{2-\alpha }, \gamma/\ell _0\right \}. \end{equation}

First, we show that $|B_{\ell _0}|\geq \gamma n$ . Suppose for a contradiction that $|B_{\ell _0}|\lt \gamma n$ . Let $i\in [\ell _0-1]$ . Then clearly $|B_i|\lt \gamma n$ , and since $G$ has minimum degree at least $\delta n^{\alpha -1}$ , we have

(3) \begin{equation} \sum _{v\in B_i} d(v)\geq \delta n^{\alpha -1} |B_i|. \end{equation}

On the other hand, $\sum _{v\in B_i}d(v)=2e(B_i)+e(B_i,B_{i+1}\setminus B_i)$ . Since $G$ is bipartite and $\mathcal{F}$ -free, $e(B_i)\leq \max _{(a,b)} \{\rho ab^{\alpha -1}+Cb^\beta \}$ over all pairs of positive integers $a\leq b$ with $a+b=|B_i|$ . Hence, $e(B_i)\leq \rho |B_i|^\alpha + C |B_i|^\beta \leq 2\rho |B_i|^\alpha$ , when $n$ is sufficiently large. With some generosity, we can upper bound $e(B_i, B_{i+1}\setminus B_i)$ by $z(|B_i|, |B_{i+1}|,\mathcal{F})$ to get $e(B_i, B_{i+1}\setminus B_i)\leq \rho |B_i||B_{i+1}|^{\alpha -1}+C |B_{i+1}|^\beta$ . Putting the above estimations all together, we get

(4) \begin{equation} \sum _{v\in B_i} d(v)\leq 4\rho |B_i|^\alpha + \rho |B_i||B_{i+1}|^{\alpha -1}+C|B_{i+1}|^\beta . \end{equation}

Combining (3) and (4), we get

(5) \begin{equation} \delta n^{\alpha -1}|B_i|\leq \sum _{v\in B_i} d(v)\leq 4\rho |B_i|^\alpha +\rho |B_i||B_{i+1}|^{\alpha -1}+C|B_{i+1}|^\beta . \end{equation}

If the first term on the right-hand side of (5) is the largest term, then we get $\delta n^{\alpha -1}|B_i|\leq 12\rho |B_i|^\alpha$ , from which we get $|B_i|\geq (\delta/12\rho )^{1/(\alpha -1)} n\geq \gamma n$ , contradicting our assumption. If the second term on the right-hand side of (5) is the largest term, then we get $\delta n^{\alpha -1}|B_i|\leq 3\rho |B_i||B_{i+1}|^{\alpha -1}$ , from which we get $|B_{i+1}|\geq (\delta/3\rho )^{1/(\alpha -1)} n\geq \gamma n$ and hence $|B_{\ell _0}|\geq |B_{i+1}|\geq \gamma n$ , contradicting our assumption. Hence we may assume that for each $i\in [\ell _0-1]$ , we have

\begin{equation*} \delta n^{\alpha -1}|B_i|\leq 3C|B_{i+1}|^\beta,\end{equation*}

which yields that for each $i\in [\ell _0-1]$ ,

(6) \begin{equation} |B_{i+1}|\geq (\delta/3C)^{1/\beta } n^{(\alpha -1)/\beta } |B_i|^{1/\beta }. \end{equation}

Let $\{b_i\}$ be a sequence recursively defined by letting $b_1=\alpha -1$ and $b_{i+1}=(1/\beta ) b_i+ (\alpha -1)/\beta$ for each $i\geq 1$ . If $\beta =1$ then a closed form formula for $b_i$ is $b_i=(\alpha -1)i$ . If $\beta \gt 1$ then a closed form formula for $b_i$ is $b_i= \frac{\alpha -1}{\beta -1} + (\frac{1}{\beta })^{i-1}(\alpha -1-\frac{\alpha -1}{\beta -1})$ . Note that we may assume $C\geq 1$ , so $|B_1|\geq \delta n^{\alpha -1}\geq (\delta/3C)n^{b_1}$ . Then it follows by (6) and induction that $|B_i|\geq (\delta/3C)^i n^{b_i}$ for each $i\in [\ell _0]$ . However, using the definition of $\ell _0$ we get $b_{\ell _0}\gt 1$ , which yield $|B_{\ell _0}|\gt n$ as $n$ is sufficiently large. This is a contradiction and thus proves that $|B_{\ell _0}|\geq \gamma n$ .

Let $j\in [\ell _0]$ be the smallest index such that $|N_j|\geq (\gamma/\ell _0) n$ . By the pigeonhole principle, such $j$ exists. By (2), $|N_j|\geq \mu n$ . Let $U=N_j$ and $V=N_{j-1}\cup N_{j+1}$ . We show that $|V|\geq 2\mu n$ , from which it follows that either $|N_{j-1}|\geq \mu n$ or $|N_{j+1}|\geq \mu n$ and thus the lemma holds with $j_0=j$ or $j_0=j-1$ . Since all the edges of $G$ that are incident to $U$ are between $U$ and $V$ , we have $e(G[U,V])\geq \delta n^{\alpha -1} |U|$ . On the other hand, $G[U,V]$ is $\mathcal{F}$ -free. If $|V|\geq |U|$ , then we have $e(G[U,V])\leq \rho |U||V|^{\alpha -1}+ C|V|^\beta \leq 2\rho |U||V|^{\alpha -1}$ , where the last inequality holds as $|U|=|N_j|\geq \mu n$ and $n$ is sufficiently large. Combining the two inequalities and solving for $|V|$ , we get $|V|\geq (\delta/2\rho )^{1/(\alpha -1)} n\geq 2\mu n$ , as desired. Otherwise, we have $|V|\leq |U|$ . Then $\delta n^{\alpha -1}|U|\leq e(G[U,V])\leq \rho |V||U|^{\alpha -1}+C|U|^\beta$ . Since $C|U|^\beta \ll \delta n^{\alpha -1}|U|$ for sufficiently large $n$ , we can derive from the above that $\delta n^{\alpha -1}|U|\leq 2\rho |V||U|^{\alpha -1}$ . Solving for $|V|$ , we have $|V|\geq (\delta/2\rho )n^{\alpha -1} |U|^{2-\alpha }\geq (\delta/2\rho ) n^{\alpha -1} (\gamma n)^{2-\alpha }=(\delta/2\rho )\gamma ^{2-\alpha } n\geq 2\mu n,$ where the last inequality holds by (2), as desired.

Proof. Let $S$ be a maximum set of vertices such that there is an associated family $\mathcal{P}=\{P_v\,{:}\,v\in S\}$ , where for each $v\in S$ , $P_v$ is a path of length at most $\ell _0$ such that no vertex is on more than $\frac{n}{\log n}$ of the paths. Let $W$ denote the set of vertices in $G$ (other than $u$ ) that lie on exactly $\frac{n}{\log n}$ of the paths $P_v$ in $\mathcal{P}$ . Then $|W|\frac{n}{\log n}\leq |S|\ell _0\leq n\ell _0$ and thus $|W|\leq \ell _0\log n\lt (\delta/2)n^{\alpha -1}$ for sufficiently large $n$ . Hence, $G-W$ has minimum degree at least $(\delta/2)n^{\alpha -1}$ . If $|S|\lt \mu (\alpha, \beta, \rho,\delta/2) n$ , then by Lemma 2.2, there exists a vertex $z\notin S$ and a $u,z$ -path $P_z$ of length at most $\ell _0$ in $G-W$ that we can add to $S$ to contradict our choice of $S$ . Hence $|S|\geq \mu (\alpha, \beta, \rho,\delta/2) n$ .

Proof. Let $(X,Y)$ denote a bipartition of $H$ . Suppose for contradiction that $H$ is disconnected and $F$ is a component of $H$ . Since $G$ is connected, it contains an edge $e$ joining $V(F)$ to $V(G)\setminus V(F)$ . But then $H\cup e$ is still bipartite, since adding $e$ does not create a new cycle. Furthermore, $H\cup e$ has more edges than $H$ , contradicting our choice of $H$ .

Next, let $v$ be any vertex in $H$ . Without loss of generality, suppose $v\in X$ . Suppose $d_H(v)\lt (1/2)d_G(v)$ . Then from $H$ by deleting the edges incident to $x$ and adding the edges in $G$ from $v$ to $X$ , we obtained a bipartite subgraph of $G$ that has more edges than $H$ , a contradiction. Hence $\forall v\in V(G), d_H(v)\geq (1/2)d_G(v)$ .

Proof. Let $x,y$ be two vertices at maximum distance in $G$ . Let $v_0v_1\cdots v_\ell$ be a shortest $x,y$ -path in $G$ where $v_0=x$ and $v_\ell =y$ . Let $q=\lfloor \ell/3\rfloor$ . Note that $N(v_0), N(v_3), N(v_6),\cdots, N(v_{3q})$ are pairwise disjoint (or else we can find a shorter $x,y$ -path, a contradiction). Hence $n\geq \sum _{i=0}^q |N(v_{3i})| \geq$ $(q+1)D$ . This implies that $(q+1)\leq n/D$ and hence $\ell \leq 3(q+1)\leq 3n/D$ .

Proof. First we prove the first part (1) of the theorem. Let $B_0=\{u\}$ . Consider any $i\in [\ell ]$ . Let $B_i$ denote the set of vertices at distance at most $i$ from $u$ in $H$ and $H_i$ the subgraph of $H$ induced by $B_i$ . If $H[B_i]$ has average degree at least $4\ell$ , then by Lemma 3.1, $G_i$ contains cycles of $\ell$ consecutive even lengths the shortest of which has length at most $2i\leq 2\ell$ and hence it contains $C_{2\ell }$ , contradicting $G$ being $C_{2\ell }$ -free. So for each $i\in [\ell ]$ , we have $d(H_i)\lt 4\ell$ , which implies that $e(H_i)\lt 2\ell |B_i|$ . On the other hand, $H_i$ contains all the edges of $G$ that are incident to $B_{i-1}$ . So $e(H_i)\geq d|B_{i-1}|/2$ . Combining these two inequalities, we get $ 2\ell |B_i|\gt d|B_{i-1}|/2$ . Hence, $|B_i|\gt (d/4\ell ) |B_{i-1}|$ for each $i\in [\ell ]$ . Thus, $|B_\ell |\geq (d/4\ell )^\ell$ , as desired.

Next, we prove the second part (2). Let us randomly split the vertices of $G$ into $\ell$ parts $V_1,\dots, V_\ell$ . For each vertex $x$ , and each $i\in [\ell ]$ , the degree $d_i(x)$ of $x$ in $V_i$ has a binomial distribution $\text{Bin}(d(x), 1/\ell )$ . Hence, using Chernoff’s inequality (see [Reference Alon and Spencer3] or [Reference Janson, Luczak and Rucinski17] Corollary 2.3), we have

\begin{equation*}\mathbb {P} [d_i(x)\lt (1/2\ell ) d(x)]\leq \mathbb {P}[|d_i(x)-(1/\ell ) d(x)|\gt (1/2\ell ) d(x)]\leq 2e^{-d(x)/12\ell } =o(n^{-1}),\end{equation*}

since $d(x)\geq 15\ell \log n$ . Hence, for sufficiently large $n$ , there exists a splitting of $V(H)$ such that for each $x\in V(H)$ and for each $i\in [\ell ]$ , $d_i(x)\geq (1/2\ell ) d(x)\geq d/2\ell$ . Now, we form a subgraph $H'$ of $H$ as follows. First, we include exactly $d/2\ell$ of the edges from $u$ to $V_1$ . Denote the set of reached vertices in $V_1$ by $S_1$ . Then for each vertex in $S_1$ including exactly $d/2\ell$ edges from it to $V_2$ . Denote the set of reached vertices in $V_2$ by $S_2$ . We continue like this till we define $S_\ell$ . Let $B_0=S_0=\{u\}$ . For each $i\in [\ell ]$ , let $B_i=\bigcup _{j=0}^i S_i$ . and $H_i$ the subgraph of $H'$ induced by $B_i$ . Note that $H_i$ has radius $i$ . As in the proof of the first part of the lemma, since $H_i$ is $C_{2\ell }$ -free, $e(H_i)\lt 2\ell |B_i|$ . On the other hand, $H_i$ contains all the edges of $H'$ that are incident to $B_{i-1}$ . So $e(H_i)\geq (1/2)(d/2\ell )|B_{i-1}|$ . Combining these two inequalities, we get $ 2\ell |B_i|\gt (d/4\ell )|B_{i-1}|$ . Hence, $|B_i|\gt (d/8\ell ^2) |B_{i-1}|$ for each $i\in [\ell ]$ . Thus, $|B_\ell |\geq (d/8\ell ^2)^\ell$ .

It is easy to see that $\sum _{i=0}^{\ell -1} |S_i|\leq \sum _{i=0}^{\ell -1} (d/2\ell )^i\leq 2(d/2\ell )^{\ell -1}$ , when $n$ is sufficiently large. Hence

\begin{equation*}|S_\ell |=|B_\ell \backslash \cup _{i=0}^{\ell -1}S_i|\geq (d/8\ell ^2)^\ell - 2 (d/2\ell )^{\ell -1}\gt (1/2) (d/8\ell ^2)^\ell,\end{equation*}

where $n$ (and thus $d$ ) is sufficiently large. By the definition of $H'$ , for each $v\in S_\ell$ , there is a path of length $\ell$ from $u$ to $v$ that intersects each of $V_1,V_2,\dots, V_\ell$ . From the union of these paths one can find a tree $T$ of height $\ell$ rooted at $u$ , in which all the vertices in $S_\ell$ are at distance $\ell$ from $u$ . Furthermore, by the definition of $H'$ , $T$ has maximum degree at most $(d/2\ell )+1$ . For each $v\in S_\ell$ , let $P_v$ be the unique $u,v$ -path in $T$ . If $x$ is any vertex in $T$ other than $u$ , then clearly $x$ lies on at most $(d/2\ell )^{\ell -1}$ of the paths $P_v$ . Furthermore, each $v\in S_\ell$ doesn’t lie on any $P_{w}$ for $w\in S_\ell \setminus \{v\}$ .

Proof of Theorem 1.6. Let $\alpha,\beta$ be reals with $2\gt \alpha \gt \beta \geq 1$ . Let $\mathcal{F}$ be an $(\alpha,\beta )$ -quasi-smooth family of bipartite graphs that satisfies $z(m,n,\mathcal{F})\leq \rho mn^{\alpha -1}+Cn^\beta$ for all $m\leq n$ .

Given any real $\delta \gt 0$ , we first define $k_0$ as following. Let $\ell _0=\ell _0(\alpha,\beta )$ as in Definition 2.1. Let $\mu (\delta ) = \mu (\alpha, \beta, \rho, \delta )$ as in the proof of Lemma 2.2. Define

(7) \begin{equation} L\,{:\!=}\,\left \lfloor \frac{3}{\mu (\delta/2)}\right \rfloor \cdot \ell _0 \mbox{ and } k_0\,{:\!=}\, 2\ell _0+L+2. \end{equation}

Let $k\geq k_0$ be odd. Let $n$ be sufficiently large so that all subsequent inequalities involving $n$ hold. Let $G$ be an $n$ -vertex $\mathcal{F}\cup \{C_k\}$ -free graph with minimum degree at least $\delta n^{\alpha -1}$ . We may assume that $G$ is connected. Let $H$ be a maximum bipartite spanning subgraph of $G$ . By Lemma 2.4, $H$ is connected and has minimum degree at least $(\delta/2) n^{\alpha -1}$ .

Since $H$ is $\mathcal{F}$ -free, by Lemma 2.2, for each vertex $x$ , the set of vertices that are at distance at most $\ell _0$ from $x$ is at least $\mu (\delta/2) n$ . Hence by Lemma 2.5 (applied to the $\ell _0$ -th power $H^{\ell _0}$ of $H$ ), $H^{\ell _0}$ has diameter at most $\lfloor \frac{3n}{\mu (\delta/2) n}\rfloor =\lfloor \frac{3}{\mu (\delta/2)}\rfloor$ and hence $H$ has diameter at most $\lfloor \frac{3}{\mu (\delta/2)}\rfloor \cdot \ell _0=L$ , as defined in (7).

Let $(X,Y)$ be the unique bipartition of $H$ . We show that $G$ is also bipartite with $(X,Y)$ being a bipartition of it. Suppose otherwise. We may assume, without loss of generality, that there exist two vertices $u,v\in X$ such that $uv\in E(G)$ . We will derive a contradiction by finding a copy of $C_k$ in $G$ that contains $uv$ .

Let us randomly split $V(H)$ into two subsets $A,B$ . For each vertex $x$ of degree $d(x)$ in $H$ , let $d_A(x)$ and $d_B(x)$ denote the degree of $x$ in $A$ and $B$ , respectively. Then both $d_A(x)$ and $d_B(x)$ satisfy the binomial distribution $\text{Bin}(d(x), 1/2)$ . Hence, by Chernoff’s inequality, we have

\begin{equation*}\mathbb {P}(d_A(x)\lt (1/4)d(x))\leq \mathbb {P}(|d_A(x)-d(x)/2|\geq d(x)/4)\leq 2e^{-d(x)/24} =o(n^{-1}),\end{equation*}

since $d(x)\geq (\delta/2)n^{\alpha -1}$ and $n$ is sufficiently large. Hence with positive probability we can ensure that for any $x\in V(H)$ , $\min \{d_A(x), d_B(x)\}\geq (1/4)d(x)\geq (\delta/8) n^{\alpha -1}$ . Let us fix such a partition $A,B$ of $V(H)$ .

Without loss of generality, suppose that the vertex $u$ is in $A$ . Let $H[A]$ denote the subgraph of $H$ induced by $A$ . By our discussion above, $H[A]$ has minimum degree at least $(\delta/8) n^{\alpha -1}$ . By Lemma 2.3, there exists a set $U$ of at least $\mu (\delta/16) n$ vertices and a family $\mathcal{P}=\{P_z\,{:}\, z\in U\}$ , where for each $z\in U$ , $P_z$ is a $u,z$ -path in $H[A]$ of length at most $\ell _0$ and no vertex in $H$ lies on more than $n/\log n$ of these paths $P_z$ . By the pigeonhole principle, there exists a value $p\in [\ell _0]$ and a subset $S\subseteq U$ of size

\begin{equation*}|S|\geq |U|/\ell _0\geq (\mu (\delta/16)/\ell _0) n\end{equation*}

such that for each $z\in S$ , $P_z \in \mathcal{P}$ has length $p$ . Now, let us randomly colour the vertices in $H[A]$ with colours $1$ and $2$ . For each $z\in S$ , the path $P_z$ is good if $z$ is coloured $2$ and the other $p$ vertices on $P_z$ are coloured $1$ . The probability that $P_z$ is good is $1/2^{p+1}$ . Hence, for some colouring, there are at least $|S|/2^{p+1}$ good paths. Let $S'$ denote the subset of vertices $z\in S$ such that $P_z$ is good and let $\mathcal{P}'=\{P_z\,{:}\,z\in S'\}$ . By our discussion,

\begin{equation*}|\mathcal {P}'|=|S'|\geq \left (\mu (\delta/16)/(2^{\ell _0+1}\ell _0)\right )n.\end{equation*}

Note that by our definition of $\mathcal{P}'$ , no vertex in $S'$ is used as an internal vertex of any path in $\mathcal{P}'$ . By our earlier discussion, each vertex in $S'$ has at least $(\delta/8)n^{\alpha -1}$ neighbours in $B$ . Let $H'$ be the subgraph of $H$ whose edge set contains all the edges in $H$ from $S'$ to $B$ . Therefore, $H'$ is bipartite with partition $S'$ and $B$ . Furthermore,

\begin{equation*}e(H')\geq |S'|(\delta/8) n^{\alpha -1}\geq \left (\mu (\delta/16)\delta/(2^{\ell _0+4}\ell _0)\right ) n^\alpha =\gamma n^\alpha,\end{equation*}

where $\gamma \,{:\!=}\,\gamma (\delta )=\mu (\delta/16) \delta/(2^{\ell _0+4}\ell _0)$ . So $H'$ has average degree at least $2\gamma n^{\alpha -1}$ . By a well-known fact, $H'$ contains a subgraph $H''$ of minimum degree at least $\gamma n^{\alpha -1}$ . Let $S''=V(H'')\cap S'$ .

Let $Q$ be a shortest path in $H$ from the vertex $v$ to $V(H'')$ . Let $y$ be the endpoint of $Q$ in $V(H'')$ . By our choice of $Q$ , $y$ is the only vertex in $V(Q)\cap V(H'')$ (note that it is possible that $y=v$ ). Let $q$ denote the length of $Q$ . Since $H$ has diameter at most $L$ , we have $q\leq L$ .

By Lemma 2.2, for some $j_0\leq \ell _0$ , inside the graph $H''$ we have $\min \{|N_{j_0}(y)|,|N_{j_0+1}(y)|\}\geq \mu ( \gamma ) n$ . Note that one of $N_{j_0}(y)$ and $N_{j_0+1}(y)$ lies completely inside $V(H'')\cap A$ . Denote this set by $W$ . Let

\begin{equation*}W_0=\{w\in W\,{:}\, P_w\cap V(Q)\neq \emptyset \}.\end{equation*}

Since $Q$ contains at most $L+1$ vertices, each of which lies on at most $n/\log n$ of the members of $\mathcal{P}$ , we see $|W_0|\leq (L+1)(n/\log n)$ . Since $n$ is sufficiently large, we have

\begin{equation*}|W\setminus W_0|\geq \mu (\gamma ) n - (L+1)n/\log n\geq (1/2)\mu (\gamma ) n.\end{equation*}

Let $H[W\setminus W_0,B]$ denote the subgraph of $H$ consisting of edges that have one endpoint in $W\setminus W_0$ and the other endpoint in $B$ . Since each vertex in $W\setminus W_0$ has at least $(\delta/8) n^{\alpha -1}$ neighbours in $B$ ,

\begin{equation*}e(H[W\setminus W_0, B])\geq |W\setminus W_0| (\delta/8) n^{\alpha -1} \geq (1/16)\mu (\gamma ) \delta n^\alpha .\end{equation*}

Hence $H[W\setminus W_0,B]$ contains a subgraph $H^*$ with minimum degree at least $(1/16)\mu (\gamma )\delta n^{\alpha -1} \geq k$ , for sufficiently large $n$ . Let $w$ be any vertex in $V(H^*)\cap (W\setminus W_0)$ . By our definition of $W$ , there is a path $R_w$ in $H''$ of length $r\leq j_0+1\leq \ell _0+1$ from $y$ to $w$ . Let $t=k-1-q-r-p$ . Since $q\leq L, p\leq \ell _0, r\leq \ell _0+1$ and $k\geq k_0= 2\ell _0+L+2$ , we get $t\geq 0$ . Since there is a path in $H$ of length $p$ from $w$ to $u$ (by the definition of $S''\subseteq W$ ). Since $V(Q)\cap V(H'')=\{y\}$ , $R_w\cup Q$ is a path in $H$ of length $q+r$ from $w$ to $v$ and $u,v\in X$ , $p$ and $q+r$ have the same parity. Since $k$ is odd, we see that $t$ is even. Since $H^*$ has minimum (much) larger than $k$ , greedily we can build a path $T$ of length $t$ in $H^*$ from $w$ to some vertex $w^*$ in $V(H^*)\cap (W\setminus W_0)$ such that $T$ intersects $Q\cup R_w$ only in $w$ . Now, let

\begin{equation*}C\,{:\!=}\,uv\cup Q\cup R_w\cup T\cup P_{w^*}\end{equation*}

By our definitions, $Q\cup R_w\cup T$ is a path. Also, since $w^*\in W\setminus W_0$ , $P_{w^*}$ is vertex disjoint from $Q$ . Finally, by our definition of $\mathcal{P}'$ , $V(P_{w^*})\setminus \{w^*\}$ is disjoint from $S'$ and hence from $S''$ . It is certainly also disjoint from $B$ and hence is vertex disjoint from $R_w\cup T$ . So, $C$ is a cycle in $G$ of length $1+q+r+t+p=k$ , a contradiction. This proves Theorem 1.6.

Proof of Theorem 1.8. Let $\ell \geq 2$ be an integer. Let $\delta \gt 0$ be a real. Define

(8) \begin{equation} L\,{:\!=}\,3\ell (8\ell/\delta )^{\ell } \mbox{ and } k_0\,{:\!=}\, 2\ell +L+2. \end{equation}

Let $k\geq k_0$ be an odd integer. Let $n$ be sufficiently large so that all subsequent inequalities involving $n$ hold. Let $G$ be an $n$ -vertex $C_{2\ell }$ -free graph with minimum degree at least $\delta n^{1/\ell }$ . We may assume that $G$ is connected. Let $H$ be a maximum spanning subgraph of $G$ . By Lemma 2.4, $H$ is connected with minimum degree at least $(\delta/2) n^{1/\ell }$ . Since $H$ is $C_{2\ell }$ -free, by Lemma 3.2, the $\ell$ -th power $H^{\ell }$ of $H$ has minimum degree at least $(\delta n^{1/\ell }/8\ell )^{\ell } =(\delta/8\ell )^{\ell } n$ . Hence, by Lemma 2.5, $H^\ell$ has diameter at most $3n/[(\delta/8\ell )^{\ell } n]=3 (8\ell/\delta )^{\ell }$ . Therefore, $H$ has diameter at most $3\ell (8\ell/\delta )^{\ell }= L$ , as defined in (8).

Let $(X,Y)$ the unique bipartition of $H$ . We show that $G$ is also bipartite with $(X,Y)$ being a bipartition of it. Suppose otherwise. Then without loss of generality, we may assume that there exist two vertices $u,v\in X$ such that $uv\in E(G)$ . We will derive a contradiction by finding a copy of $C_k$ in $G$ that contains $uv$ . As in the proof of Theorem 1.6, we can split $V(H)$ into two subsets $A,B$ such that for each vertex $x\in V(H)$ , we have $d_A(x), d_B(x)\geq (1/4)d(x)\geq (\delta/8) n^{1/\ell }$ .

Without loss of generality, suppose $u\in A$ . Let $H[A]$ denote the subgraph of $H$ induced by $A$ . By our discussion above, $H[A]$ has minimum degree at least $(\delta/8) n^{1/\ell }$ . By Lemma 3.2 (with $d=(\delta/8) n^{1/\ell }$ ), there exists a set $S$ of size at least $(\delta/64\ell ^2)^\ell (n/2)$ and a family $\mathcal{P}=\{P_z\,{:}\, z\in S\}$ , where for each $z\in S$ , $P_z$ is a $u,z$ -path in $H[A]$ of length $\ell$ , such that no vertex other than $u$ in $H$ lies on more than $(\delta n^{1/\ell }/8)^{\ell -1}=(\delta/8)^{\ell -1} n^{1-1/\ell }$ of these paths. Furthermore, for each $z\in S$ , $z$ lies only on $P_z$ .

Let $H[S,B]$ denote the bipartite subgraph of $H$ induced by the two parts $S$ and $B$ . By our earlier discussion, each vertex in $S$ has at least $(\delta/8)n^{1/\ell }$ neighbours in $B$ . Hence,

\begin{equation*}e(H)\geq |S|(\delta/8) n^{1/\ell }\geq (\delta ^{\ell +1}/2^{6\ell +4}\ell ^{2\ell }) n^{1+1/\ell }=\gamma n^{1+1\ell },\end{equation*}

where $\gamma \,{:\!=}\,\delta ^{\ell +1}/2^{6\ell +4}\ell ^{2\ell }$ . Then $H[S,B]$ has average degree at least $2\gamma n^{1/\ell }$ and thus contains a subgraph $H'$ of minimum degree at least $\gamma n^{1/\ell }$ . Let $S'=V(H')\cap S$ and $B'=V(H')\cap B$ .

If $\ell$ is even, then $S'\subseteq X$ and let $Q$ be a shortest path in $H$ from $v$ to $S'$ . If $\ell$ is odd, then $B'\subseteq X$ and let $Q$ be a shortest path in $H$ from $v$ to $B'$ . Let $y$ denote the endpoint of $Q$ opposing $v$ (it is possible that $y=v$ ). Let $q$ denote the length of $Q$ . So $q$ is even and $y\in X$ . In either case, it is easy to see that $q\leq L+1$ and that $V(H')$ contains $y$ and at most one other vertex of $Q$ . Hence $H'-(V(Q)\setminus \{y\})$ has minimum degree at least $\gamma n^{1/\ell }-1\geq (\gamma/2)n^{1/\ell }$ . By Lemma 3.2 (with $d=(\gamma/2)n^{1/\ell }$ ), inside the graph $H'-(V(Q)\setminus \{y\})$ there is a set $W$ of size at least $(1/2)(\gamma/16\ell ^2)^\ell n$ such that for each $w\in W$ there is a path $R_w$ of length $\ell$ from $y$ to $w$ in $H'-(V(Q)\setminus \{y\})$ . Furthermore, by our definition of $Q$ , we can get $W\subseteq S'$ . Recall the paths $P_w$ in $\mathcal{P}$ . Let

\begin{equation*}W_0=\{w\in W\,{:}\, P_w\cap V(Q)\neq \emptyset \}.\end{equation*}

Since $Q$ contains at most $L+1$ vertices each of which lies on at most $(\delta/8)^{\ell -1} n^{1-1/\ell }$ of the members of $\mathcal{P}$ , we see $|W_0|\leq (L+1)(\delta/8)^{\ell -1} n^{1-1/\ell }$ . Since $n$ is sufficiently large, we have

\begin{equation*}|W\setminus W_0|\geq (1/2)(\gamma/16\ell ^2)^\ell n - (L+1)(\delta/8)^{\ell -1} n^{1-1/\ell } \geq (1/4)(\gamma/16\ell ^2)^\ell n.\end{equation*}

Since each vertex in $W\setminus W_0$ has at least $(\delta/8) n^\ell$ neighbours in $B$ ,

\begin{equation*}e(H[W\setminus W_0, B])\geq |W\setminus W_0| (\delta/8) n^{1/\ell }\geq (\delta \cdot \gamma ^\ell )/(2^{4\ell +5}\cdot \ell ^{2\ell }) n^{1+1/\ell }.\end{equation*}

Hence $H[W\setminus W_0,B]$ contains a subgraph $H^*$ with minimum degree at least $(\delta \cdot \gamma ^\ell )/(2^{4\ell +5}\cdot \ell ^{2\ell }) n^{1/\ell }\geq k$ , for sufficiently large $n$ . Let $w$ be any vertex in $V(H^*)\cap (W\setminus W_0)$ . By our definition of $W$ , there is a path $R_w$ in $H'-(V(Q)\setminus \{y\})$ of length $\ell$ from $y$ to $w$ . Let $t=k-1-q-2\ell$ . Since $q\leq L+1$ and $k\geq k_0= 2\ell +L+2$ , we see $t\geq 0$ . Since $k$ is odd and $q$ is even, we also see that $t$ is even. Since $H^*$ has minimum degree (much) larger than $k$ , greedily we can build a path $T$ of length $t$ in $H^*$ from $w$ to some vertex $w^*$ in $V(H^*)\cap (W\setminus W_0)$ such that $T$ intersects $Q\cup R_w$ only in $w$ . Now, let

\begin{equation*}C\,{:\!=}\,uv\cup Q\cup R_w\cup T\cup P_{w^*}\end{equation*}

By our definition of $T$ , $Q\cup R_w\cup T$ is path. Also, since $w^*\in W\setminus W_0$ , $P_{w^*}$ is vertex disjoint from $Q$ . Finally $P_{w^*}\setminus \{w^*\}$ does not contain any vertex of $S'\cup B$ and hence is vertex disjoint from $R_w\cup T$ . Hence, $C$ is a cycle in $G$ of length $1+q+2\ell +t=k$ , a contradiction.

Proof of Theorem 1.7. Let $2\gt \alpha \gt \beta \geq 1$ and $\mathcal{F}$ be an $(\alpha,\beta )$ -smooth family with relative density $\rho$ . Then by the remark after Definition 1.2, there exist constants $C_1\lt C_2$ such that for sufficiently large $n$ ,

\begin{equation*}\rho (n/2)^\alpha +C_1n^\beta \leq z(n,\mathcal {F})\leq \rho (n/2)^\alpha +C_2n^\beta .\end{equation*}

Fix $\delta \,{:\!=}\,\rho/2^{\alpha +3}$ . Let $k_0$ be from Theorem 1.6 such that for any odd $k\geq k_0$ and sufficiently large $m$ , any $m$ -vertex $\mathcal{F}\cup \{C_k\}$ -free graph with minimum degree at least $\delta m^{\alpha -1}$ is bipartite.

Now consider any odd $k\geq k_0$ and sufficiently large $n$ . Let $G$ be an $n$ -vertex extremal $\mathcal{F}\cup \{C_k\}$ -free graph. Then

(9) \begin{equation} e(G)=\textrm{ex}(n,\mathcal{F}\cup \{C_k\})\geq z(n,\mathcal{F})\geq \frac{\rho }{2^\alpha }n^\alpha +C_1n^\beta . \end{equation}

Let $G_0=G$ . If there exists some vertex $x$ of degree less than $\delta n^{\alpha -1}$ in $G_0$ , then we delete the vertex $x$ and rename the remaining subgraph as $G_0$ . We repeat the above process until there is no such vertex in $G_0$ . Let $H$ denote the remaining induced subgraph of $G$ and let $t=n-|V(H)|$ . We note that as $\alpha \lt 2$ and $n$ is sufficiently large, using (9) and $\delta =\frac{\rho }{2^{\alpha +3}}$ ,

(10) \begin{equation} e(H)\geq e(G)-t\cdot \delta n^{\alpha -1}\geq \left (\frac{\rho }{2^\alpha }n^\alpha +C_1n^\beta \right )-n\cdot \delta n^{\alpha -1}=\frac{7}{8}\frac{\rho }{2^\alpha } n^\alpha +C_1n^\beta . \end{equation}

Let $m=|V(H)|$ . By definition, $H$ is an $m$ -vertex $\mathcal{F}\cup \{C_k\}$ -free graph with minimum degree at least $\delta n^{\alpha -1}\geq \delta m^{\alpha -1}$ . By taking $n$ sufficiently large, we can make $m$ large enough to apply Theorem 1.6 to conclude that $H$ is bipartite. Since $H$ is also, $\mathcal{F}$ -free, we have

(11) \begin{equation} e(H)\leq z(m,\mathcal{F})=z(n-t,\mathcal{F})\leq \frac{\rho }{2^\alpha } (n-t)^\alpha +C_2 n^\beta . \end{equation}

Comparing (10) and (11), we see that $n-t\geq \frac{3}{4}n$ . By (9), (10) and (11), we have

\begin{equation*}\left (\frac {\rho }{2^\alpha }n^\alpha +C_1n^\beta \right )-t\cdot \delta n^{\alpha -1}\leq \frac {\rho }{2^\alpha }(n-t)^\alpha +C_2 n^\beta \end{equation*}

Recall that $\delta =\rho/2^{\alpha +3}$ . Rearranging the above inequality, we get

\begin{equation*}\frac {\rho }{2^\alpha }n^\alpha -\frac {\rho }{2^\alpha }(n-t)^\alpha -t\cdot \delta n^{\alpha -1}\leq (C_2 - C_1)n^\beta . \end{equation*}

By the Mean Value Theorem, for some $n - t \leq n' \leq n$ , this is equivalent to

\begin{equation*}\frac {\rho \alpha }{2^\alpha }t(n')^{\alpha -1}-t\cdot \delta n^{\alpha -1}\leq (C_2 - C_1)n^\beta .\end{equation*}

Since $n-t\geq \frac{3}{4}n$ and $\frac{\rho \alpha }{2^{\alpha }}(\frac{3}{4})^{\alpha -1} \gt 2\cdot \frac{\rho }{2^{\alpha +3}}$ , the above inequality yields

\begin{equation*}\frac {\rho }{2^{\alpha +3}}tn^{\alpha - 1} \leq (C_2 - C_1)n^\beta .\end{equation*}

So, $t=O(n^{1+\beta -\alpha })$ and in obtaining $H$ from $G$ at most $t\cdot \delta n^{\alpha -1}=O(n^\beta )$ edges are removed.