Proof. Let $\mathcal{P}=(P_1,\ldots ,P_{t-2})$ be a $(t-2)$ -partition of $[r]$ which attains $f(n_1,\ldots ,n_r,1,t-1)$ . Thus, by the Pigeonhole Principle, one part of $\mathcal{P}$ , say $P_s$ , contains at least two integers $i,j\in [t-1]$ . Hence $\mathcal{P}^\ast =(P_1,\ldots ,\{i\},P_s\setminus \{i\},\ldots ,P_{t-2})$ is a $(t-1)$ -partition of $[r]$ . Note that $n_i\geq n_{t-1}$ and $n_j\geq n_{t-1}$ . Therefore, we have $f(n_1,\ldots ,n_r,1,t-1)+n_{t-1}^2\leq f(n_1,\ldots ,n_r,1,t-1)+n_i n_j \leq f(n_1,\ldots ,n_r,1,t)$ , where the last inequality holds by $\mathcal{P}^\ast$ is a $(t-1)$ -partition of $[r]$ and the definition of $f(n_1,\ldots ,n_r,1,t)$ . The proof of this proposition is complete.

Proof. Suppose for a contradiction that $G_{A \rightarrow B}$ contains a copy of $K_t$ . Clearly, $V(K_t)\cap A$ is not empty, as otherwise $G$ contains a copy of $K_t$ , a contradiction. Since $A$ is independent in $G_{A \rightarrow B}$ , we have $|V(K_t)\cap A|=1$ . However, every vertex of $A$ is adjacent to a $(t-2)$ -partite graph in $G_{A \rightarrow B}$ . Thus there is no copy of $K_t$ in $G_{A \rightarrow B}$ . The result follows.

Proof. Suppose for a contradiction that $G_{A \rightarrow X}$ contains a copy of $F$ . Clearly, $V(F)\cap A$ is not empty, as otherwise $G$ contains a copy of $F$ , a contradiction. We can see that $G[X]$ contains a copy of $F-A$ , implying $G[X\cup B]$ contains a copy of $F$ (note that $A$ is an independent set in $G_{A \rightarrow X}$ ), a contradiction ( $G$ is $F$ -free). The proof of the moreover part is similar and is omitted. We finish the proof of this proposition.

Proof. The proposition holds trivially for $s=0$ . Let $1\leq s\leq \tau$ . Take an extremal $(t-1)$ -partition $\mathcal{P}=(P_1,\ldots , P_{t-1})$ of $K$ with $|P_1| \geq \ldots \geq |P_{t-1}|$ . By Theorem1.12, $\mathcal{P}$ is stable to $\mathcal{V}$ . It is sufficient to show that $P_i=V_i$ for $i=1,\ldots ,\tau$ . Theorem1.1 implies that $H=K_{n_1,\ldots ,n_r}[\mathcal{P}]$ is an extremal graph for $K_t$ . By the definition of $\tau$ , we have $\sum _{i=\tau +1}^{r} n_i \leq rn_{\tau }/r^4\lt n_{\tau }/r.$ We can conclude that each $V_{s\leq \tau }$ is integral in $\mathcal{P}$ . Otherwise, there is a partial class with size at least $n_{\tau }$ in $\mathcal{V}$ , and hence the integral part of each class ( $t-1$ classes) of $\mathcal{P}$ is of size at least $n_{\tau }$ (since $\mathcal{P}$ is stable to $\mathcal{V}$ ), which is impossible since $\tau \leq t-2$ and $\sum _{i=\tau +1}^{r} n_i\lt n_{\tau }/r.$ Thus $|P_{t-1}|\leq \sum _{i=\tau +1}^{r} n_i \leq n_{\tau }/r$ . Moreover, if $P_j$ contains $V_s$ and some other vertices, then the integral $V_s$ has a size larger than $|P_{t-1}|\geq |I(P_{t-1})|$ , which is a contradiction (since $\mathcal{P}$ is stable to $\mathcal{V}$ ). Therefore, we must have $P_i=V_i$ for $i=1,\ldots ,\tau$ . The proof of Proposition3.4 is complete.

Proof. The hierarchy of constants in the proof satisfies $\delta \ll \xi \ll \epsilon _r$ . Since $\delta$ is sufficiently small, by Proposition2.3 for $\delta$ there exists a $\xi \in [\delta ,\sqrt [10^{r}]{\delta }]$ , such that every class of $\mathcal{V}$ is of size either less than $\xi n_{t-1}$ or at least $\sqrt [10]{\xi } n_{t-1}$ . Let $b$ be the minimum integer such that $n_b\leq \xi n_{t-1}$ . Let $\widetilde {X}$ be the union of sets in $\mathcal{V}$ with size less than $\xi n_{t-1}$ and let $|\widetilde {X}|=m_r= \sum _{i=b}^{r}n_i$ . Let $H_0=G^r-\widetilde {X}$ .

We next construct the partition $\mathcal{P}^r$ . Define $H_{i+1}$ to be the subgraph of $H_i$ induced by the neighbours of a vertex with maximum degree in $H_{i}$ recursively. Suppose that the above progress stops when $e(H_{s-1})=0$ and let $V(H_s)=\emptyset$ . Let $A_i=V(H_{i-1}) \setminus V(H_{i})$ for $i \in [s]$ . Let

\begin{equation*}\mathcal{P}^r= \left (A_1,\ldots ,A_{s-1},A_s\cup \widetilde {X}\right ).\end{equation*}

Thus $\mathcal{P}^r_{\widetilde {X}}=(A_1,\ldots ,A_s)$ .

We first show $s= t-1$ . Clearly, $A_s$ is an independent set in $G^r$ . Since $G^r$ is $K_t$ -free, we have $s\leq t-1$ . Otherwise, any vertex in $A_s$ can form a copy of $K_t$ with those vertices picked with maximum degree in $H_i$ ’s.

Note that every set of $\mathcal{V}_{\widetilde {X}}$ is integral in $\mathcal{P}^r_{\widetilde {X}}$ (each vertex in $V_i$ has common neighbours in $G^r$ by the construction of $G^r$ ). In fact, let $x$ be the vertex with maximum degree in $H_0$ . Then $V_i$ which contains $x$ belongs to $A_1$ and if $x$ is not adjacent to $V_j$ , then $V_j$ belongs to $A_1$ . Continue this arguments for $A_2, \ldots , A_s$ , we can show that every set of $\mathcal{V}_{\widetilde {X}}$ is integral in $\mathcal{P}^r_{\widetilde {X}}$ .

Thus

(6) \begin{equation} e(H_0)\leq \sum \limits _{i=1}^{s-1} \left (\sum \limits _{v\in A_i}\frac {d_{A_i}(v)}{2}+d_{H_i}(v)\right )\leq \sum \limits _{1\leq i\lt j\leq s}|A_i||A_j|\leq f(n_1,\ldots ,n_{b-1},1,s+1). \end{equation}

We will show that

(7) \begin{equation} f(n_1,\ldots ,n_{r},1,t)\geq f(n_1,\ldots ,n_{b-1},1,t)+m_r \sum _{i=1}^{t-2}n_i. \end{equation}

Let $\mathcal{Q}=(Q_1,\ldots ,Q_{t-1})$ be a maximal $(t-1)$ -partition of $\{n_1,n_2,\ldots ,n_{b-1}\}$ . Without loss of generality, we may assume that $Q_{t-1}$ does not contain any element in $\{n_1,n_2,\ldots ,n_{t-2}\}$ . Then $\mathcal{Q}^\ast =(Q_1,\ldots ,Q_{t-1}\cup \{n_b,n_{b+1},\ldots ,n_r\})$ is a $(t-1)$ partition of $\{n_1,n_2,\ldots ,n_r\}$ . Thus (7) follows by the definition of the function $f$ and $|\bigcup _{i=1}^{t-2}Q_i| \geq \sum _{i=1}^{t-2}n_i$ .

If $s\lt t-1$ , then by (6), (7), $b\geq t$ and Proposition3.1, we have

\begin{eqnarray*} e(G^r) &\overset {(6)}\leq & f(n_1,\ldots ,n_{b-1},1,s+1)+m_r^2+m_r\sum \nolimits _{i=1}^{b-1}n_i\\ &\leq & f(n_1,\ldots ,n_{b-1},1,t-1)+m_r^2+m_r\sum \nolimits _{i=1}^{b-1}n_i\\ &\overset {Prop.\,3.1}{\leq } & f(n_1,\ldots ,n_{b-1},1,t)-n^2_{t-1}+ m_r^2+m_r\sum \nolimits _{i=1}^{b-1}n_i\\ &\overset {(7)}{\leq } & f(n_1,\ldots ,n_{r},1,t)+ m_r \sum \nolimits _{i=t-1}^{b-1}n_i -n^2_{t-1}+ m_r^2\\ &\leq & f(n_1,\ldots ,n_{r},1,t)-(1-\epsilon _r)n_{t-1}^2 \end{eqnarray*}

contradicting (5). Therefore, we have $s=t-1$ .

We next show $G^r-\widetilde {X}$ is $0$ -close to $K_{n_1,\ldots ,n_r}[\mathcal{P}^r]-\widetilde {X}$ , i.e., every vertex in $V(H_{i})$ for $i\in [s-1]$ is incident with all the vertices of $A_i$ in graph $H_{i-1}$ . Otherwise, suppose that $v_{j_1}\in V(H_{i})\cap V_{j_1}$ is not incident with some vertex $v_{j_2}\in A_i\cap V_{j_2}$ . Then there is no edge between $V_{j_1}$ and $V_{j_2}$ in $G^r$ by our construction. Therefore, we have

\begin{equation*} \begin{aligned} \sum \limits _{v\in A_i}\frac {d_{A_i}(v)}{2}+d_{H_i}(v)&\leq |A_i||V(H_i)|- \frac { |V_{j_1}||V_{j_2}|}{2}\leq |A_i||V(H_i)|-(\sqrt [10]{\xi }n_{t-1})^2. \end{aligned} \end{equation*}

It follows from (6) that $e(H_0)\leq f(n_1,\ldots ,n_{b-1},1,t)-\sqrt [5]{\xi }n_{t-1}^2$ . Since $\xi$ is sufficiently small, similar as the proof of $s=t-1$ , by (7), we have $e(G^r)\le e(H_0)+ m_r^2+m_r\sum \nolimits _{i=1}^{b-1}n_i\leq f(n_1,\ldots ,n_{r},1,t)-\sqrt [4]{\xi }n_{t-1}^2$ , a contradiction to (5). Note that every vertex in $A_i$ has at most $|V(H_{i})|$ neighbours in $H_{i-1}$ . Thus $A_i$ is an independent set in $H_{i-1}$ . Therefore, $\mathcal{P}^r_{\widetilde {X}}$ induces a complete $(t-1)$ -partite subgraph in $H_0$ .

Note that each $V_i$ either belongs to $\widetilde {X}$ or is integral in $\mathcal{P}^r_{\widetilde {X}}$ . Given $A_i$ and distinct $A_{i^\prime }$ , let $V_j$ be an integral set in $A_i$ . Let $S \, :\!= \bigcup _{\iota \neq i^\prime }A_{\iota }$ . Since each vertex in $A_{i^\prime }$ is adjacent to each vertex in $S$ and $A_{i^\prime }$ is an independent set with size at least $\xi n_{t-1}$ , it follows from Proposition3.3 that $G^r_{V_j\to S}$ is $K_t$ -free and hence $e(G^r_{V_j\to S}) \leq f(n_1,\ldots ,n_r,1,t)$ . Combining with (5), we have $|A_i\setminus V_j|- |A_{i^\prime }|\le \delta n_{t-1}^2/|V_j|\le \delta n_{t-1}/ \xi \le \epsilon _r^2 n_{t-1}$ . Thus $\mathcal{P}^r_{\widetilde {X}}$ is $\epsilon _r^2 n_{t-1}$ -stable to $\mathcal{V}_{\widetilde {X}}$ . Applying Lemma2.6, we obtain the required $X_r$ such that $\mathcal{P}^r_{X_r}$ is stable to $\mathcal{V}_{X_r}$ . By above, $\mathcal{P}^r$ is the $(X_r,\epsilon _r)$ -stable $(t-1)$ -partition of $G^r$ .

Proof. Let $\widetilde {P}_i=P_i\setminus (\overline {X}\cup V_k)$ . By induction hypothesis, $G^k-X_k$ is edgeless in each part of $\mathcal{P}_{X_k}^k$ . By our construction, $G^k-V_k=G^{k-1}-V_k$ . Thus, we only need to show that $G^{k-1}$ is edgeless between $\widetilde {P}_i$ and $X_{k,i}$ for $i\in [t-1]$ .

Clearly, we may suppose that $|\widetilde {P}_i|\geq \sqrt [10]{\xi }n_{t-1}$ . Otherwise, by the definition of $Z_2$ , we have $\widetilde {P}_i=\emptyset$ . We immediately finish the proof. Let $a\in X_{k,i}$ . By $|\overline {X}|\leq 4tr \xi n_{t-1}$ and $\mathcal{P}^k_{X_{k}}$ is stable to $\mathcal{V}_{X_k}$ ( $\mathcal{P}^k$ is $(X_k,\epsilon _{k})$ -stable), $\mathcal{P}^k_{\overline {X}}$ is $\sqrt {\xi } n_{t-1}$ -stable to $\mathcal{V}_{\overline {X}}$ . Since $V_k\setminus X_k\subseteq P^k_{i_k}$ , by (10) each part of $(\mathcal{P}^{k}\wedge \mathcal{V})_{\overline {X}}$ has size at least $\sqrt [10]{\xi }n_{t-1}$ . By (9) we have

\begin{eqnarray*} d_{G^{k-1}}(a)&\geq & \sum \nolimits _{\ell \neq i_k} |P_{\ell }^k|- \sqrt {\epsilon _{k}} n_{t-1}\\ &\geq &\sum \nolimits _{\ell \neq i_k} |P_{\ell }^k|-\sqrt {\xi } n_{t-1} \\ &\geq &\sum \nolimits _{\ell \neq i_k}|\overline {P}_\ell \setminus \overline {V}_k|- |\overline {X}|-\sqrt {\xi } n_{t-1}\\ &\geq & \sum \nolimits _{\ell \neq i_k}|\overline {P}_\ell \setminus \overline {V}_k| -\sqrt [5]{\xi } n_{t-1} . \end{eqnarray*}

Thus applying Proposition2.5 (here we consider the edges in $G^{k-1}$ and the partition $(\mathcal{P}^{k}\wedge \mathcal{V})_{\overline {X}}$ ), there exists an $m(a)$ such that $a$ has more than $(\sqrt [10]{\xi }/4)n_{t-1}$ neighbours in the integral part of every $P^k_{i\neq m(a)}\setminus \overline {X}$ . If there is an edge between $a$ and $\widetilde {P}_i$ , then by the definition of $X_{k,i}=B_i$ , there is an edge $ab$ with $b \in \widetilde {P}_{m(a)}$ . Since $\mathcal{P}^k_{X_k}$ is $(X_k,\epsilon _{k})$ -stable, we can construct a copy of $K_t$ in $G^{k-1}$ with vertices $a,b$ and their common neighbours in the integral parts of $\widetilde {P}_{i\neq m(a)}$ ’s, a contradiction. Hence we finish the proof of Claim4.3.

Proof. Without loss of generality, suppose for a contradiction that $\overline {V}_1$ (we do not consider the size of each $\overline {V}_i$ ) is partial in parts $\overline {P}_{i_1},\overline {P}_{i_2}$ with $|\overline {P}_{i_2}\setminus \overline {V}_1|-|\overline {P}_{i_1}\setminus \overline {V}_1|\gt \sqrt {\xi } n_{t-1}$ . Let $S=\bigcup \nolimits _{i\neq i_1} (\overline {P}_i\setminus \overline {V}_1)$ . Note that $|X_{1,i_2}|\geq \sqrt [10]{\xi }n_{t-1}$ by (10). By Claim4.3, $G^{k-1}[S]$ is $(t-2)$ -partite. Hence by (5) and Proposition3.2, $H=G^{k-1}_{X_{1,i_2}\to S}$ is a $K_t$ -free graph with

\begin{eqnarray*} e(H)&\geq & e(G^{k-1})+ \left (\sqrt {\xi }n_{t-1}-|\overline {X}|\right )|X_{1,i_2}|\\ &\geq & f(n_1,\ldots ,n_r,1,t)-\delta n_{t-1}^2+ \left (\sqrt {\xi } n_{t-1}-4tr\xi n_{t-1}\right ) \sqrt [10]{\xi } n_{t-1}\\ &\gt & f(n_1,\ldots ,n_r,1,t), \end{eqnarray*}

a contradiction. We finish the proof of Claim4.4.

Proof. Without loss of generality, suppose for a contradiction that both $\overline {V}_1,\overline {V}_2$ are partial in $\overline {P}_1$ (as in Claim 3, we do not consider the size of each $\overline {V}_i$ ). Let $\overline {V}_1$ be partial in $\overline {P}_{s}$ and $\overline {V}_2$ be partial in $\overline {P}_{\ell }$ (it is possible that $s=\ell$ ). Since $\overline {V}_2$ is partial in $\overline {P}_1,\overline {P}_{\ell }$ , it follows from Claim4.4 that $|\overline {P}_1\setminus \overline {V}_2|-|\overline {P}_{\ell }\setminus \overline {V}_2|\geq -\sqrt {\xi } n_{t-1}$ . Let $S_1=\bigcup _{i\neq \ell } (\overline {P}_i\setminus \overline {V}_2)$ . By Claim4.3, $G^{k-1}[S_1]$ is $(t-2)$ -partite. Thus by Proposition3.2, $H^1=G^{k-1}_{X_{2,1}\to S_1}$ is a $K_t$ -free graph with

\begin{equation*}e(H^1)\geq e(G^{k-1})+ (|\overline {P}_1\setminus \overline {V}_2|-|\overline {P}_{\ell }\setminus \overline {V}_2|-|\overline {X}|)|X_{2,1}| \geq e(G^{k-1}) -2\sqrt {\xi }n_{t-1}|X_{2,1}|.\end{equation*}

Let $S_2=\bigcup _{i=2}^{t-2}(\overline {P}_i\setminus \overline {V}_1)\cup X_{2,1}$ . Then by Claim4.3, $H^1[S_2]$ is $(t-2)$ -partite. Hence by Proposition3.2, $H^2=H^1_{X_{1,s}\to S_2}$ is a $K_t$ -free graph. Since $\overline {V}_1$ is partial in $\overline {P}_1,\overline {P}_{s}$ , Claim4.3 implies $|\overline {P}_1\setminus X_{1,1}|-|\overline {P}_{s}\setminus X_{1,s}|\leq \sqrt {\xi } n_{t-1}$ . By (10), we have $|X_{2,1}|,|X_{1,s}|\geq \sqrt [10]{\xi }n_{t-1}$ . Thus we have

\begin{eqnarray*} e(H^2)&\geq & e(H^1)+\left (|X_{2,1}|-\sqrt {\xi }n_{t-1}-|\overline {X}|\right )|X_{1,s}|\\ &\geq & e(G^{k-1})-2\sqrt {\xi }n_{t-1}|X_{2,1}|+\dfrac {1}{2}|X_{2,1}||X_{1,s}|\\ & \geq & e(G^{k-1})+\dfrac {1}{3}\sqrt [5]{\xi }n_{t-1}^2\\ &\gt &f(n_1,\ldots ,n_r,1,t), \end{eqnarray*}

a contradiction. Thus $\mathcal{P}^{k-1}_{\overline {X}}$ is $1$ -partial to $\mathcal{V}_{\overline {X}}$ .

Proof. Suppose that $\overline {V}_1$ is partial in $\overline {P}_{i_1}$ and $\left |I(\overline {P}_{i_1})\right |\ge m+\sqrt [5]{\xi } n_{t-1}$ . If $\overline {P}_{i_m}$ is integral, then let $S=\bigcup _{i\neq i_m}(\overline {P}_i\setminus \overline {V}_1)$ . By Claim4.3, $G^{k-1}[S]$ is $(t-2)$ -partite. Thus by Proposition3.2, $G^{k-1}_{X_{1,i_1}\to S}$ is a $K_t$ -free graph with $e(G^{k-1})+ \left (\sqrt [5]{\xi }n_{t-1}-\overline {X}\right ) \sqrt [10]{\xi }n_{t-1}\gt f(n_1,\ldots ,n_r,1,t)$ edges, a contradiction. Thus $\overline {P}_{i_m}$ must be partial. By Claims4.4 and $4$ , $\overline {V}_1$ cannot be partial in $\overline {P}_{i_m}$ . Let $\overline {V}_2$ be the set that is partial in $\overline {P}_{i_m}$ . Let $a\in \overline {V}_2$ be a vertex with maximum number of neighbours in $G^{k-1}$ . Without loss of generality, let $a\in P_{\ell _1}$ and $\overline {V}_2\cap P_{\ell _2}\neq \emptyset$ , where $\ell _1\neq \ell _2$ (it is possible that $\ell _1=i_m$ or $\ell _2=i_m$ ). Clearly, $H=G^{k-1}_{\overline {V}_2\to N_{G^{k-1}}(a)}$ is $K_t$ -free by Proposition3.3 and has more number of edges than $G^{k-1}$ . By Claim4.4, $|I(\overline {P}_{\ell _2})|\le |I(\overline {P}_{i_m})|+\sqrt {\xi }n_{t-1}= m+\sqrt {\xi }n_{t-1}.$ Let $S'=(\bigcup _{i\neq \ell _2} \overline {P}_i)\cup \overline {V}_2$ . Then $H[S']$ is $(t-2)$ -partite by Claim4.3. By Proposition3.2, $H_{X_{1,i_1}\to S'}$ is a $K_t$ -free graph with more than

\begin{align*} e(H)& +\left (|S'|-\left |\bigcup \nolimits _{i\neq i_1}\overline {P}_i\setminus \overline {V}_1\right |-|\overline {X}|\right )\cdot |X_{1,i_1}|\\& \ge e(H)+\left (|I(\overline {P}_{i_1})|-|I(\overline {P}_{\ell _2})|-|\overline {X}|\right )\cdot \sqrt [10]{\xi }n_{t-1}\\ & \ge e(G^{k-1})+\sqrt {\xi }n^2_{t-1}\gt f(n_1,\ldots ,n_r,1,t) \end{align*}

edges, a contradiction. The proof of Claim4.6 is complete.

Proof. Without out loss of generality, suppose that $\overline {V}_1$ is partial in $\overline {P}_{i_1},\overline {P}_{i_2}$ . Suppose otherwise that $|\overline {V}_1|\ge m+\sqrt [7]{\xi }n_{t-1}$ . By Claims4.5 and 4.6, we have