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{.}\)
