\section{Proof of Theorem \ref{edge}}
\label{sec:newedge}

For fixed $t\ge 3$, we assume that $G$ is a minimum counter-example to Theorem \ref{edge}. In particular, we assume that $G$ has $q\binom{k-1}{2}+\binom{r}{2}+s$ edges where $0\le s< r\le k-2$, $k_t(G)\ge q\binom{k-1}{t}+\binom{r}{t}+\binom{s}{t-1}$, and $G$ is not one of the extremal graphs (i.e. $G \not\in \Gf(qK_{k-1}, L)$, where $L\in \C_{t, k}(\binom{r}{2}+s)$). We may assume that $0\le s<r$, because any non-negative integer $b$ can be uniquely written in the form $b = \binom{r}{2} + s$ for integers $0 \le s < r$. Furthermore, we assume that the number of copies of $K_t$ in any other graph with the same number of edges is at most $k_t(G)$. Note that if $q=0$, then Theorem \ref{edge} follows from Theorem \ref{maxkt}. Thus, we may also assume that $q \ge 1$.

\begin{lemma} \label{bigclique}
If $G$ is a minimum counter-example, then $G$ does not contain a copy of $K_{k-1}$.
\end{lemma}

\begin{proof}
Suppose for the sake of contradiction that $G$ does contain a copy of $K_{k-1}$. Fix one such copy $C$ of $K_{k-1}$, let $v_1, v_2, \ldots, v_{k-1}$ denote the vertices of the clique $C$. We first claim that for all $i \neq j$, there is no path $P$ between the vertices $v_i$ and $v_j$ such that all internal vertices are outside of $C$. Indeed, if this is not the case, then we can easily find a cycle of length at least $k$ by using the path $P$ and the clique $C$, contradicting the fact that $G$ is $C_{\ge k}$-free. Then, it follows that for any edge $e\in E(C)$, all the copies of $K_t$ using $e$ must be subgraphs of $C$. Then, by removing the edges in $C$, we obtain a graph $G'$ with $(q-1)\binom{k-1}{2}+\binom{r}{2}+s$ edges and contains at least $(q-1)\binom{k-1}{t}+\binom{r}{t}+\binom{s}{t-1}$ number of $K_t$'s. Since $G'$ is not a counter-example, $G'$ has exactly the optimal number of $K_t$'s and thus is one of the extremal structures where $G'\in \mathcal{G}_{forest}((q-1)K_{k-1}, L)$ for some $L\in \C_{t, k}(\binom{r}{2}+s)$. 

To achieve a contradiction, we show that $G\in \mathcal{G}_{forest}(qK_{k-1}, L)$. Let $F_1, F_2, \ldots, F_{q-1}$ be the $q-1$ edge-disjoint copies of $K_{k-1}$ in $G'$. Let $L_1, \ldots, L_{q'}$ be the connected components in $L$. Let $\mathcal{F}=\{F_1, \dots, F_{q-1}, L_1, \ldots, L_{q'}\}$. Note that the edgesets of the graphs in $\mathcal{F}$ and $E(C)$ partitions the edges of $G$. Furthermore,  $|V(G_1)\cap V(G_2)|\le 1$ for all distinct $G_1, G_2\in \mathcal{F}$. For any $G_1\in \mathcal{F}$, $|V(G_1)\cap V(C)|\le1$; otherwise, two of the vertices in $C$ has a path that does not use any edges in $C$, contradicting our previous claim about $C$. Then, $G$ satisfies the first condition in Definition \ref{def:family} with respect to $\mathcal{G}_{forest}(qK_{k-1}, L)$. Let $H$ be the auxiliary graph created from $G$ according to the second condition in Definition \ref{def:family}. Since $G'\in \mathcal{G}_{forest}(\mathcal{F})$ and no two vertices in $C$ has an external path outside of $C$ in $G$, it follows that $H$ is a forest. Then, $G\in \mathcal{G}_{forest}(\mathcal{F}, C)$ and thus $G$ is one of the extremal graphs, a contradiction. 
\end{proof}

\begin{lemma} \label{connected}
If $G$ is a minimum counter-example, then $G$ is 2-connected.
\end{lemma}

Lemma \ref{connected} is proved at the end of this section to avoid being sidetracked by simple but long convexity arguments. On an intuitive level, if a counter-example $G$ is not connected, then one of its connected components should be a smaller counter-example. Similarly, if a counter-example $G$ is connected but not 2-connected, then $G$ has a cut vertex $v$. Then, by splitting the vertex $v$, we should be able to find a smaller minimal counter-example. For now, we take this fact for granted and prove other structural properties about $G$. 


\begin{lemma}
	\label{mindegedge}
If $G$ is a minimum counter-example, then $G$ has minimum degree at least $r$.
\end{lemma}

\begin{proof}
	For the sake of contradiction, assume that there exists $v\in V(G)$ whose degree is $0 < \b < r$. Consider the graph $G\backslash v$. Let $k=k_t(G)-k_t(G\backslash v)$ be the number of $K_t$'s that contain $v$. Note that $k \le \binom{\b}{t-1}$. 
	
	Since $G\backslash v$ is not a counter-example, $k_t(G\backslash v)\le q\binom{k-1}{t}+k_t(L_{\binom{r}{2}+s-\b})$. If $\b\le s$, then by Lemma \ref{easy:convex}, $k_t(L_{\binom{r}{2}+s}) - k_t(L_{\binom{r}{2}+s-\b}) = \left(\binom{r}{t}+\binom{s}{t-1}\right)-\left(\binom{r}{t} + \binom{s-\b}{t-1}\right)\ge \binom{\b}{t-1}$. If $\b>s$, since $\b\le r-1$, then $k_t(L_{\binom{r}{2}+s}) - k_t(L_{\binom{r}{2}+s-\b}) = \left(\binom{r}{t}+\binom{s}{t-1}\right)-\left(\binom{r-1}{t} + \binom{r-1+s-\b}{t-1}\right)\ge \binom{\b}{t-1}$. Note that in both cases, $$k_t(L_{\binom{r}{2}+s}) - k_t(L_{\binom{r}{2}+s-\b}) \ge \binom{\b}{t-1}.$$ 
	
	Then, we have the following.
	
	\begin{align*}
	k_t(G\backslash v) &= k_t(G) - k \\
	&\ge q\binom{k-1}{t} + k_t(L_{\binom{r}{2}+s}) - \binom{\b}{t-1} \\
	&\ge q\binom{k-1}{t} + k_t(L_{\binom{r}{2}+s-\b}) \ge k_t(G\backslash v).
	\end{align*}
	
	Since $G\backslash v$ is not a counter-example, we conclude that it is one of the extremal graphs in Theorem \ref{edge}. Thus, since $q\ge 1$, both $G\backslash v$ and $G$ contain a copy of $K_{k-1}$, contradicting Lemma \ref{bigclique}. 
	
\end{proof}

\begin{lemma} \label{smallr}
If $G$ is a minimum counter-example, then $r \le \frac{k-1}{2}$.
\end{lemma}

To prove this lemma, we require the following well-known theorem by Dirac \cite{D}.

\begin{theorem} [\cite{D}] \label{dirac}
	If $G$ is an $n$-vertex 2-connected graph with minimum-degree at least $r$, then there exists a cycle of length at least $\min(n, 2r)$. 
\end{theorem}

\begin{proof} [Proof of Lemma \ref{smallr}]
	This follows immediately from Lemmas \ref{connected} and \ref{mindegedge}, and Theorem \ref{dirac}. 
\end{proof}

Next, we bound the number of vertices in $G$. 

\begin{lemma} \label{lem:largen}
	If $G$ is a minimum counter-example, then $G$ has at least $q(k-1) + (r+1)$ vertices.
\end{lemma}

To prove this lemma, we make use of a classical result by Whitney \cite{W32} and a recent result by Luo \cite{Luo}. 

\begin{theorem} [\cite{W32}] \label{Whitney}
A connected graph $G$ with at least three vertices is 2-connected if and only if for every two vertices $u, v \in V(G)$, there is a cycle containing both $u$ and $v$.
\end{theorem}

\begin{theorem} [\cite{Luo}] \label{Luo3}
Let $n \ge k \ge 5$. If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $k_t(G) \le \max\{f_t(n,k,2), f_t(n,k,\lfloor\frac{k-1}{2}\rfloor)\}$, where $f_t(n,k,a) = \binom{k-a}{t} + (n-k+a)\binom{a}{t-1}$.
\end{theorem}

\begin{proof} [Proof of Lemma \ref{lem:largen}]
	First, we claim that $k\ge 5$. Suppose for the sake of contradiction that $k\le 4$. By Lemma \ref{connected} and Theorem \ref{Whitney}, any two vertices $u, v$ are in a cycle. Since $G$ is $C_{\ge k}$-free, then every pair of vertices $u, v$ is in a triangle and in particular, edge $uv$ exists. Therefore $G$ is a clique. However, since $G$ is $C_4$-free, $G$ has at most three vertices and is trivially one of the extremal graphs, a contradiction.
	
Suppose for the sake of contradiction that $G$ has at most $n=q(k-1) + r$ vertices. In order to get a contradiction, it is enough to prove that $k_t(G) < T_t:= k_t(qK_{k-1} \cup L_{\binom{r}{2} + s})=q\binom{k-1}{t} + \binom{r}{t} + \binom{s}{t-1}$. By Lemma \ref{connected} and Theorem \ref{Luo3}, it suffices to prove that $\max\{f_t(n,k,2), f_t(n,k,\lfloor\frac{k-1}{2}\rfloor)\} < T_t$.

We first show that $f_t(n,k,2) < T_t$ as follows:
\begin{align*}
f_t(n,k,2) &= \binom{k-2}{t} + ((q-1)(k-1)+r+1)\binom{2}{t-1} \\
&\le \binom{k-2}{t} + ((q-1)(k-1)+r+1) \\
&< q\binom{k-1}{t} + \binom{r}{t} + \binom{s}{t-1} = T_t.
\end{align*}

Now, we show that $f_t(n,k,\lfloor\frac{k-1}{2}\rfloor) = \binom{k-\lfloor\frac{k-1}{2}\rfloor}{t} + (q(k-1)+r-k+\lfloor\frac{k-1}{2}\rfloor)\binom{\lfloor\frac{k-1}{2}\rfloor}{t-1} < T_t$. Note that it suffices to prove the following:
$$\binom{\lceil\frac{k+1}{2}\rceil}{t} + \left((q-1)(k-1)+r+\left\lfloor\frac{k-3}{2}\right\rfloor\right)\binom{\lfloor\frac{k-1}{2}\rfloor}{t-1} < q\binom{k-1}{t} .$$

By rewriting $q\binom{k-1}{t}$ as $(q-1)\binom{k-1}{t}+\binom{k-1}{t}$ and using the fact that $r\le \lfloor \frac{k-1}{2}\rfloor$ (by Lemma \ref{mindegedge}), the above inequality is implied by the following two inequalities:


\begin{align}
(q-1)(k-1)\binom{\lfloor\frac{k-1}{2}\rfloor}{t-1} &\le (q-1)\binom{k-1}{t} \label{ineq1} \\
\binom{\lceil\frac{k+1}{2}\rceil}{t} + 2\left\lfloor\frac{k-1}{2}\right\rfloor\binom{\lfloor\frac{k-1}{2}\rfloor}{t-1} & < \binom{k-1}{t} \label{ineq2}
\end{align}


To prove Inequality \eqref{ineq1}, we may assume that $\lfloor\frac{k-1}{2}\rfloor\ge t-1$, otherwise the inequality trivially holds. Rearranging the terms, it is equivalent to show $\prod_{i=0}^{t-2} \frac{k-2-i}{\lfloor\frac{k-1}{2}\rfloor -i} \ge t$. For the left-hand-side, when $i=0, \frac{k-2}{\lfloor \frac{k-1}{2}\rfloor} \ge 1.5$ since $k\ge 5$. For the subsequent fractions, note that for $1\le i\le t-2$,  $\frac{k-2-i}{\lfloor\frac{k-1}{2}\rfloor-i} \ge \frac{k-3}{\lfloor\frac{k-1}{2}\rfloor -1}$. Since $k\ge 5$, these fractions are at least $2$. Then, it suffices to show that $1.5(2)^{t-2}\ge t$. This holds for $t\ge 3$, proving Inequality \eqref{ineq1}.


To prove Inequality \eqref{ineq2}, we require the following identity:
$$\binom{x}{t} + y\binom{x}{t-1} + x\binom{y}{t-1} \le \binom{x+y}{t}.$$

If the above identity holds, Inequality \eqref{ineq2} follows immediately by setting $x=\lceil\frac{k+1}{2}\rceil$ and $y=\lfloor\frac{k-1}{2}\rfloor$. To prove the identity, consider the following combinatorial argument. 

 Suppose there are two groups of people $A$ and $B$ of size $x$ and $y$ respectively. The right-hand-side counts the number of ways to form a team of $t$ people out of $A\cup B$. Possible ways of forming a $t$-member team includes: choosing all $t$ members from $A$, choosing one member from $A$ while the rest from $B$, and choosing one member from $B$ while the rest from $A$. Thus, the left-hand-side is at most the right-hand-side. 
\end{proof}


We require one more lemma before proving our main theorem. The following allows us to better compare the value $k_t(G)$ and the optimal value $T_t$. 

\begin{lemma} \label{cor}
If $G$ is a minimum counter-example with $m$ edges, then $$k_t(G) \le \frac{1}{t} \left[\a \binom{k-2}{t-1} + (n-\a) \binom{r}{t-1}\right],$$ where $\a$ is a real number satisfying $\a(k-2) + (n-\a)r = 2m$ and $n = q(k-1) + (r+1)$.
\end{lemma}

\begin{proof}
Let $G$ be a minimum counter-example. Keep in mind that the number of vertices in $G$ is at least $n$ by Lemma \ref{lem:largen}. For any vertex $v$ in a $C_k$-free graph, the neighborhood $N(v)$ is $P_{k-1}$-free, and hence by Theorem \ref{path} (or Theorem \ref{erdos} for $t=3$), $k_t(v) \le a \binom{k-2}{t-1} + \binom{b}{t-1}$, where $a$ and $b$ are non-negative integers satisfying $d(v) = a(k-2) + b$ and $b<k-2$. By using Definition \ref{split}, we have that $\sum_{v \in V(G)} k_t(v) \le \sum_{i=1}^N \binom{y_i}{t-1}$, where $\{y_i\}_{i=1}^{N}=\spl_{k-2}(\bar{d})$ and $\bar{d}$ is the degree sequence of $G$. Now, define the sequence $\{x_i\}_{i=1}^n$ such that $\sum_{i=1}^n x_i = 2m$ and there exists $j$ such that $x_i=k-2$ for all $1\le i\le j$, $r \le x_{j+1} \le k-2$ and $x_i=r$ for all $j+1<i\le n$. Similar to the proof of Theorem \ref{path} in Section 2, Karamata's inequality \ref{karma} implies that $\sum_{v \in V(G)} k_t(v) \le \sum_{i=1}^n \binom{x_i}{t-1}$. Now, find the unique $0 \le \a' \le 1$ such that $\a' (k-2) + (1-\a') r = x_{j+1}$, and apply Jensen's inequality to get $\binom{x_{j+1}}{t-1} \le \a' \binom{k-2}{t-1} + (1-\a') \binom{r}{t-1}$. Our lemma follows immediately where $\a=j+\a'$.
\end{proof}

Now, we are ready to prove Theorem \ref{edge}. 

\begin{proof}[Proof of Theorem \ref{edge}]
	Let $G$ be a minimum counter-example. By Lemma \ref{cor}, one can check that $\a = q(k-1) - \frac{2(r-s)}{k-2-r}$ is the desirable $\alpha$. Then, we have the following:
	\begin{align*}
	k_t(G) &\le \frac{1}{t} \left[ \left(q(k-1) - \frac{2(r-s)}{k-2-r}\right) \binom{k-2}{t-1} + \left(r+1+\frac{2(r-s)}{k-2-r}\right) \binom{r}{t-1} \right] \\
	&\le T_t -\frac{2(r-s)}{t(k-2-r)} \left(\binom{k-2}{t-1} - \binom{r}{t-1}\right) + \binom{r}{t-1} - \binom{s}{t-1}. 
	\end{align*}
	
	Let $C_1=\frac{2(r-s)}{t(k-2-r)} \left(\binom{k-2}{t-1} - \binom{r}{t-1}\right)$ and $C_2=\binom{r}{t-1} - \binom{s}{t-1}$. In order to show that $k_t(G) < T_t$, it suffices to prove that $C_2-C_1<0$. Since $r>s$, the inequality is strict when $r<t-1$. Thus, we may assume $r\ge t-1$. In order to finish the proof, we claim that it suffices to prove the following two inequalities:
	
	\begin{equation} \label{eq1}
		\binom{r}{t-1} - \binom{s}{t-1} \le (r-s)\binom{r-1}{t-2}	
	\end{equation}
	
		\begin{equation} \label{t}
	\frac{\binom{k-2}{t-1} - \binom{r}{t-1}}{(k-2-r) \binom{r-1}{t-2}} > \frac{t}{2}.
	\end{equation}
	
	If the inequalities above were true, Equation \eqref{t} provides a bound to $C_1$. Then, $C_2-C_1<0$ follows from Equation \eqref{eq1}.
	
	To show that Equation \eqref{eq1} holds, the left side can be interpreted as choosing $t-1$ people in a group $R$ of size $r$ without choosing all of them from a subgroup $S\subset R$ of size $s$. The right side is an upper-bound on the number of ways a team can be formed by making sure at least one of them is from $R \setminus S$. It follows that the right side is at least as large as the left side. 
	
	
	To prove Equation \eqref{t}, since $t\ge 3$, we can first lower-bound the numerator of the left side by the following:
	\begin{equation} \label{4}
	\binom{k-2}{t-1} - \binom{r}{t-1} \ge (k-2-r) \binom{r}{t-2} + \binom{k-2-r}{2} \binom{r}{t-3}.
	\end{equation}
	
	The above inequality can be proved by using a similar argument as before: the left side is forming a team of $t-1$ players from a group $K$ of size $k-2$ without having all of them from a subgroup $R\subset K$ of size $r$. Meanwhile, the right side corresponds to first choosing one or two person from $K\setminus R$ and filling the rest of the team from $R$. Then,
	
	
	\begin{align} \label{6}
	\frac{\binom{k-2}{t-1} - \binom{r}{t-1}}{(k-2-r) \binom{r-1}{t-2}} &\ge \frac{(k-2-r)\binom{r}{t-2}+\binom{k-2-r}{2}\binom{r}{t-3}}{(k-2-r)\binom{r-1}{t-2}} \nonumber \\
	&= \frac{r}{r-t+2} + \frac{r}{r-t+3}\cdot \frac{k-3-r}{r-t+2} \cdot \frac{t-2}{2}.
	\end{align}
	
	Thus, for $t=3$, one can easily plug in the value of $t$ in \eqref{6} and check the validity of \eqref{t} by using Lemma \ref{smallr}. For $t \ge 4$, we have the following from \eqref{6}:
	
	 \begin{align*} 
	\frac{\binom{k-2}{t-1} - \binom{r}{t-1}}{(k-2-r) \binom{r-1}{t-2}} > 1 + \frac{k-3-r}{r-2} \cdot \frac{t-2}{2}. 
	\end{align*}
	
	Thus, to prove \eqref{t}, it is enough to show that $\frac{k-3-r}{r-2} \ge 1$. This follows from Lemma \ref{smallr}, which concludes our proof of Theorem \ref{edge}.
	
	
	
\end{proof}

We now finish this section by giving a proof of Lemma \ref{connected}. We need the following couple of lemmas about a minimum counter-example to Theorem \ref{edge}. 

\begin{lemma}
	\label{lem:posr}
	If $G$ is a minimum counter-example, then $r \ge 2$. 
\end{lemma}
	
\begin{proof}
	Suppose for the sake of contradiction that $r=1$ and $s=0$. This implies that $|E(G)|=q\binom{k-1}{2}$ and $k_t(G)\ge q\binom{k-1}{t}$. We split into two cases depending on the maximum degree of $G$. 
	\smallskip
	
	Case 1: If the maximum degree of $G$ is strictly less than $k-2$, then for any edge $e$, its endpoints have less than $k-3$ common neighbors in $G$. Hence, $e$ belongs in less than $\binom{k-3}{t-2}$ distinct copies of $K_t$. Summing over all edges, since each $K_t$ is counted $\binom{t}{2}$ times, $k_t(G)$ is less than $q\binom{k-1}{2}\frac{\binom{k-3}{t-2}}{\binom{t}{2}}=q\binom{k-1}{t}$, a contradiction. 
	\smallskip
	
	Case 2: If the maximum degree of $G$ is at least $k-2$, we claim that $G$ contains a copy of $K_{k-1}$ which contradicts Lemma \ref{bigclique}. For a vertex $v$, by Theorem \ref{path} and using the fact that the neighborhood of $v$ is $P_{k-1}$-free, we have that 
	\begin{equation} \label{copy}
	k_t(v) \le a \binom{k-2}{t-1} + \binom{b}{t-1},
	\end{equation}
	where $a$ and $b < k-2$ are non-negative integers satisfying $d(v) = a(k-2) + b$. By using the convexity of the function $x \rightarrow \binom{x}{t-1}$ with the set of integers as domain, it is easy to see that $a\binom{k-2}{t-1} + \binom{b}{t-1} \le \frac{d(v)}{k-2} \binom{k-2}{t-1}$. Hence, it follows that 
	\begin{align}
	k_t(G) = \frac{1}{t} \sum_{v \in V(G)} k_t(v) 
	\le \frac{1}{t} \sum_{v \in V(G)} \frac{d(v)}{k-2} \binom{k-2}{t-1} 
	= q \binom{k-1}{t}. \label{conseq}
	\end{align} 
	Thus, we have an equality in \eqref{conseq} and consequently, we have equality in \eqref{copy} for each vertex of $G$. Suppose that $v$ is a vertex with degree at least $k-2$. Then, by using the equality in \eqref{copy} for $v$, it follows from Theorem \ref{path} that there is a copy of $K_{k-2}$ in the neighborhood $N(v)$ of $v$. This $K_{k-2}$ together with the vertex $v$ makes a copy of $K_{k-1}$ in $G$, contradicting Lemma \ref{bigclique}.
\end{proof}


\begin{lemma}
	\label{alledget}
	If $G$ is a minimum counter-example, then every edge in $G$ is in a copy of $K_t$. 
\end{lemma}

\begin{proof}
	Suppose for the sake of contradiction that an edge $e$ is not in a copy of $K_t$. Consider the graph $G'=G\backslash e$. 
	\smallskip
	
	Case 1: $s>0$. Observe that $q\binom{k-1}{t}+\binom{r}{t}+\binom{s}{t-1}\le k_t(G) = k_t(G') \le q\binom{k-1}{t}+\binom{r}{t}+\binom{s-1}{t-1}$. Since the right-hand-side is at most the left-hand-side, the above equation is at equality and $s<t-1$. Then, $G'$ has an extremal structure $\Gf(qK_{k-1}, L)$, where $L\in \C_{t, k}(\binom{r}{2}+s-1)$. Since $q\ge 1$, $G$ contains a copy of $K_{k-1}$, contradicting Lemma \ref{bigclique}.
	\smallskip
	
	Case 2: $s=0$. Keep in mind that by Lemma \ref{lem:posr}, we have that $r-2\ge 0$. Then, $q\binom{k-1}{t}+\binom{r}{t}\le k_t(G) = k_t(G') \le q\binom{k-1}{t}+\binom{r-1}{t}+\binom{r-2}{t-1}$. Once again, the above equation is tight and thus $r<t$. Then, $G'$ is an extremal graph with $q$ cliques of order $k-1$ and a graph $L\in \C_{t, k}(\binom{r}{2}-1)$. Similarly, $G$ contains a copy of $K_{k-1}$, contradicting Lemma \ref{bigclique}.  
	
\end{proof}


\begin{proof}[Proof of Lemma \ref{connected}]
	Suppose for the sake of contradiction that $G$ is not 2-connected. Let $v$ be a vertex in $G$ such that $G' = G \backslash v$ is not connected. Now, suppose $G'$ contains a proper subgraph $H'$ that is a union of connected components of $G'$ such that $|E(H)| \ge \binom{k-1}{2}$ where $H$ is the graph induced by $V(H')\cup\{v\}$. Since $H$ is not a counter-example to Theorem \ref{edge}, either $H$ contains strictly less $K_t$'s than an extremal graph with the same number of edges, or $H$ is an extremal graph. In the first case, deleting the edges in $H$ and replacing with one of the extremal graphs result in a graph that strictly increases the number of $K_t$'s in $G$ while maintaining the same number of edges, creating a worse minimum counter-example, a contradiction. In the latter case, $H$ contains at least one copy of $K_{k-1}$, contradicting Lemma \ref{bigclique}. Thus, we may assume that for all proper subgraphs $H'$ that is a union of connected components of $G' = G \backslash v$, the graph induced by $V(H') \cup \{v\}$ has strictly less than $\binom{k-1}{2}$ edges. 
	
	Let $G'_1$ be a connected component of $G'$ and $G'_2=G'\backslash G'_1$. Let $G_i$ be the graph induced by $V(G'_i) \cup \{v\}$ for $i=1, 2$. Note that if one of $G_1$ and $G_2$ is not an extremal structures, then by replacing them with an extremal structure, one strictly increases the number of $K_t$'s, contradicting the choice of $G$. Since neither are counter-examples nor contain at least $\binom{k-1}{2}$ edges, we may assume that $G_i\in \C_{t, k}(\binom{r_i}{2}+s_i)$, where $|E(G_i)|=\binom{r_i}{2}+s_i$ and $0\le s_i< r_i\le k-2$ for $i=1, 2$. Observe that if $0<s_i<t-1$, some edges in $G_i$ will not be part of any $K_t$'s, contradicting Lemma \ref{alledget}. Similar contradiction is achieved if $r_i<t$. Thus we may assume that $r_i\ge t$ and either $s_i=0$ or $s_i\ge t-1$ for $i=1, 2$. Observe in either cases, $G_i$ is a colex graph. Without loss of generality, we can assume that $r_1 \ge r_2$. Now, depending on the values of $s_1$ and $s_2$, we move a certain amount of edges from $G_2$ to $G_1$ and obtain a graph with strictly more $K_t$'s than before, achieving contradicting the choice of $G$.
	\smallskip
	
	Case 1: $s_1, s_2> 0$. Let $s'=\min\{s_2, r_1-s_1\}$. Note that $s' \ge 1$. Let $G_1''$ be the colex graph with $|E(G_1)|+s'=\binom{r_1}{2}+s_1+s'$ edges, let $G_2''$ be the colex graph with $|E(G_2))|-s'=\binom{r_2}{2}+s_2-s'$ edges. Essentially, we are moving $s'$ edges from $G_2$ to $G_1$. The value $s'$ is chosen such that this process is equivalent to moving one edge at a time from $G_2$ to $G_1$ and stopping as soon as one of $G_1$ or $G_2$ becomes a clique. Doing so keeps the calculation of $k_t(G_1'')$ and $k_t(G_2'')$ as simple as possible. Note that $s_1, s_2 \ge t-1\ge 1$, and $s' \ge 1$. Hence, we have the conditions that $s_1, s_2 < s_1+s'$ and $s_1+s' \ge t-1$. Then, it follows from Lemma \ref{easy:convex} that
	
	\begin{align*}
		k_t(G_1\cup G_2) &= \binom{r_1}{t}+\binom{s_1}{t-1}+\binom{r_2}{t}+\binom{s_2}{t-1}\\
		&< \binom{r_1}{t} + \binom{s_1+s'}{t-1} + \binom{r_2}{t} + \binom{s_2-s'}{t-1}\\
		&= k_t(G_1''\cup G_2''), 
	\end{align*} 
	a contradiction.
	\smallskip
	
	Case 2: $s_1 = 0$, $s_2> 0$. Let $s'=\min\{r_2 -1, r_1-s_2\}$. Recall that $r_2\ge t\ge 1$ so after deleting $s_2$ edges from $G_2$, there are still more edges one can remove. Then, let $G_1''$ be the colex graph with $|E(G_1)|+s_2+s'=\binom{r_1}{2}+s_2+s'$ edges and $G_2''$ be the colex graph with $|E(G_2)|-s_2-s'=\binom{r_2-1}{2} +r_2-1-s'$ edges (moving $s_2+s'$ edges from $G_2$ to $G_1$). Since $s'\ge r_2-1> s_2-1 \ge t-2> 0$, we have that $s_2+s'\ge t-1$. Furthermore, since $r_1\ge r_2$, we have that $s_2+s' = \min\{r_2-1+s_2, r_1\}> r_2-1, s_2$, Then, by Lemma \ref{easy:convex},
	
	\begin{align*}
		k_t(G_1\cup G_2) &= \binom{r_1}{t}+\binom{r_2-1}{t}+\binom{r_2-1}{t-1}+\binom{s_2}{t-1}\\
		&< \binom{r_1}{t}  +\binom{s_2+s'}{t-1} + \binom{r_2-1}{t} + \binom{r_2-1-s'}{t-1}\\
		&= k_t(G_1''\cup G_2''),
	\end{align*}
	a contradiction. 
	\smallskip
	
	Case 3: $s_1>0$, $s_2 = 0$. Let $s'=\min\{r_1-s_1, r_2-1\}$. Keep in mind that $r_1>s_1\ge t-1\ge 1$. Let $G_1''$ be the colex graph with $|E(G_1)|+s'=\binom{r_1}{2}+s_1+s'$ edges and let $G_2''$ be the colex graph with $|E(G_2)|-s'=\binom{r_2-1}{2}+r_2-1-s'$ edges (moving $s'$ edges from $G_2$ to $G_1$ while ensuring not adding more than $r_1-s_1$ many edges to $G_1$). Note that $s'\ge 1$ and $s_1+s'\ge t-1$. Since $r_1\ge r_2$, we have that $s_1+s'=\min\{r_1, r_2-1+s_1\}>r_2-1$. Then, it follows from Lemma \ref{easy:convex} that
	
	\begin{align*}
		k_t(G_1\cup G_2) &= \binom{r_1}{t}+\binom{s_1}{t-1}+\binom{r_2-1}{t}+\binom{r_2-1}{t-1}\\
		&< \binom{r_1}{t}+\binom{s_1+s'}{t-1} +\binom{r_2-1}{t}+\binom{r_2-1-s'}{t-1}\\
		&= k_t(G_1''\cup G_2''),
	\end{align*}
	a contradiction.
	\smallskip
	
	Case 4: $s_1=s_2=0$. Keep in mind that $r_2\ge t\ge 2$. Let $G_1''$ be the colex graph with $|E(G_1)|+r_2=\binom{r_1}{2}+r_2$ edges, let $G_2''$ be the colex graph with $|E(G_2)|-r_2=\binom{r_2-2}{2}+r_2-3$ edges. Then by Lemma \ref{easy:convex}, 
	
	\begin{align*}
		k_t(G_1\cup G_2) &= \binom{r_1}{t}+\binom{r_2-2}{t}+\binom{r_2-1}{t-1}+\binom{r_2-2}{t-1}\\
		&< \binom{r_1}{t}+\binom{r_2}{t-1} +\binom{r_2-2}{t}+\binom{r_2-3}{t-1}\\
		&= k_3(G_1''\cup G_2''),
	\end{align*}
	a contradiction.
	
\end{proof}
{"config": "arxiv", "file": "2006.04681/newedge.tex"}