What we will prove is that there is a set \(E_1\subseteq E(G)\) of cardinality at most \(t\) such that \(G-E_1\) has chromatic number at most \(r-1\text{.}\) We claim that this is sufficient to prove the theorem. Indeed, if such a set \(E_1\) exists, then \(G-E_1\) is a graph of chromatic number at most \((r-1)\) with at least \(\ex(n,K_r)-2t\) edges. If we let \(E_2\) be the set of all missing edges between vertices in different colour classes, we get that \((G-E_1)\cup E_2\) is a complete \((r-1)\)-partite graph. This graph is \(K_r\)-free, and so it must have at most \(\ex(n,K_r)\) edges; thus, the number of edges in \(E_2\) is at most \(2t\text{.}\)
So, we focus on proving that a set
\(E_1\) of the type described above exists. We analyse the so-called Erdős degree majorization algorithm
[88]. Initialize
\begin{equation*}
V_0^+:=V(G)\text{.}
\end{equation*}
Now, for \(i\geq1\text{,}\) if \(V_{i-1}^+\) is non-empty, then let \(x_i\) be a vertex of maximum degree in \(G[V_{i-1}^+]\text{.}\) Define
\begin{equation*}
V_i^+:=V_{i-1}^+\cap N(x_i)
\end{equation*}
and
\begin{equation*}
V_i:=V_{i-1}^+\setminus N(x_i)\text{.}
\end{equation*}
By a simple handshaking argument, we have
\begin{equation*}
\sum_{v\in V_i} |N(v)\cap V_{i-1}^+| = 2e(V_i) + e(V_i,V_i^+)\text{.}
\end{equation*}
By our choice of \(x_i\text{,}\) we have that \(|N(v)\cap V_{i-1}^+|\leq |N(x_i)\cap V_{i-1}^+| = |V_i^+|\) for all \(v\in V_i\text{.}\) Combining this with the above equality gives us
\begin{equation}
2e(V_i) + e(V_i,V_i^+)\leq |V_i^+||V_i|\text{.}\tag{4.5.1}
\end{equation}
Let \(s\) be the minimum integer so that \(V_s^+=\emptyset\text{;}\) i.e. this is when the procedure terminates. Note that we must have \(s\leq r-1\) since the vertices \(x_1,\dots,x_s\) form a complete graph. By construction, the sets \(V_1,\dots,V_s\) partition \(V(G)\text{.}\)
Now, to finish the proof, we sum up the inequality
(4.5.1) over
\(1\leq i\leq s\text{.}\) The left side of the resulting inequality counts each edge within any of the sets
\(V_i\) exactly twice and any edge from
\(V_i\) to
\(V_j\) for
\(i\lt j\) exactly once; to see why the latter is true, observe that
\(V_i^+=\bigcup_{j=i+1}^s V_j\) for all
\(i\text{.}\) Therefore, in total, the left side is equal to
\begin{equation*}
|E(G)| + \sum_{i=1}^s e(V_i) = \ex(n,K_r)-t+ \sum_{i=1}^s e(V_i)\text{.}
\end{equation*}
The right side precisely counts the number of edges in a complete \(s\)-partite graphs whose parts are \(V_1,\dots,V_s\text{,}\) which is at most \(\ex(n,K_r)\) (here, we use that \(s\leq r-1\)). Therefore,
\begin{equation*}
\ex(n,K_r)-t+ \sum_{i=1}^s e(V_i) \leq \ex(n,K_r)
\end{equation*}
which implies that \(\sum_{i=1}^s e(V_i)\leq t\text{.}\) Define \(E_1\) to be the set of all edges which lie within one of the sets \(V_i\text{.}\)
