1.(z,eX,×X,where(X,X)is not()△△-1 regular; 2.(z,∈Xi×Xi,where d(Xi,X)<: 3.EXi;where Xil roxn The total number of edges removed is at mostn2 from the first condition,since if I is the set of (i,j)corresponding to non-regular pairs (Xi,Xj),we have ∑xx≤(g)△-1r≤62 (住.)∈ The total number of edges removed by condition 2 is clearly at most n2 and the total number removed by condition 3 is at most in. Overall,we have removed at most n2 edges.Hence,the graph G'that remains after all these edges have been removed has density at least 1- +It must,therefore,contain a copy of Kr.We may suppose that this lies between setsV(so me of which may be equal).Because of our removal process,l吲≥on,the graph between Vi and Vi has density at least and is2(g)∽△-l-regular.. Therefore,if 16M"≥2()6 an application of the previous lemma with implies that G contains a copy of H. Because of the observation made after the previous lemma,we know that,for n large,G not only contains one copy of any givencromatic graph H,it must contain copies.This phenomenon, that once one passes the extremal density one gets a very large number of copies rather than one single copy,is known as supersaturation. 21. (x, y) ∈ Xi × Xj , where (Xi , Xj ) is not 1 2 ￾  8
∆ ∆−1 -regular; 2. (x, y) ∈ Xi × Xj , where d(Xi , Xj ) <  4 ; 3. x ∈ Xi , where |Xi | <  16M n. The total number of edges removed is at most  16n 2 from the first condition, since if I is the set of (i, j) corresponding to non-regular pairs (Xi , Xj ), we have X (i,j)∈I |Xi ||Xj | ≤ 1 2   8 ∆ ∆−1n 2 ≤  16 n 2 . The total number of edges removed by condition 2 is clearly at most  4 n 2 and the total number removed by condition 3 is at most  16n 2 . Overall, we have removed at most 3 8 n 2 edges. Hence, the graph G0 that remains after all these edges have been removed has density at least 1 − 1 r−1 +  8 . It must, therefore, contain a copy of Kr. We may suppose that this lies between sets V1, . . . , Vr (some of which may be equal). Because of our removal process, |Vj | ≥  16M n, the graph between Vi and Vj has density at least  4 and is 1 2 ￾  8
∆ ∆−1 -regular. Therefore, if  16M n ≥ 2   8 −∆ t, an application of the previous lemma with  8 implies that G contains a copy of H. ✷ Because of the observation made after the previous lemma, we know that, for n large, G not only contains one copy of any given r-chromatic graph H, it must contain cnv(H) copies. This phenomenon, that once one passes the extremal density one gets a very large number of copies rather than one single copy, is known as supersaturation. 2