Also,since C has at most edges,we have os-+)9+a+-(-+)+(任-到号+a9 2 2 2 But we also have le(G)2 (1-1+e).Therefore,the process stops once (-)竖-<号-量 that is,when n'vern.From now on,we will assume that we are working within this large well- behaved subgraph G. We will show,by induction on r,that there are r+I sets A1,A2,...,Ar+of size t such that every edge between Ai and Aj,with 1<i<j<r+1,is in G.For r =0,there is nothing to prove. Givenr>0and s=[3t/el,we apply the induction hypothesis to find r disjoint sets B,B2,...,B of size s such that the graph between every two disjoint sets is complete.Let U=V(G)\{BIU...UB} and let W be the set of vertices in U which are adjacent to at least t vertices in each Bi. We are going to estimate the number of edges missing between U and BiU...UBr.Since every vertex in U\W is adjacent to fewer than t vertices in some Bi,we have that the number of missing edges is at least m≥1U八wI(s-t)2(m'-rs-1wD(1-)s On the other hand,every vertex in G'has at most ()n'missing edges.Therefore,counting over all vertices in BU...UBr,we have m≤r(目)r=(-)m Therefore, w1-)2-r0-)-(-)m=(-》m-(-)2 Since ,r and s are constants,we can make W]large by making n'large.In particular,we may make W]such that wm>(食'e- Every element in W has at least t neighbours in each Bi.There are at most ()ways to choose a t-element subset from each of BiU...UBr.By the pigeonhole principle and the size of Wl,there must therefore be some subsets A1,...,Ar and a set Ar+of size t from W such that every vertex in Ar+ is conected to every vertex in A are already joined in the appropriate manner,this completes the proof Note that a careful analysis of the proof shows that one may take t=c(r,e)logn.It turns out that this is also best possible (see example sheet). It remains to prove the Erdos-Stone-Simonovits theorem itself. 2Also, since G0 has at most n 02 2 edges, we have |e(G)| ≤  1 − 1 r +  2  (n 2 − n 02 ) 2 + (n − n 0 ) 2 + n 02 2 =  1 − 1 r +  2  n 2 2 +  1 r −  2  n 02 2 + (n − n 0 ) 2 . But we also have |e(G)| ≥ ￾ 1 − 1 r + 
n 2 2 . Therefore, the process stops once  1 r −  2  n 02 2 − n 0 2 <  n 2 4 − n 2 , that is, when n 0 ≈ √ rn. From now on, we will assume that we are working within this large well￾behaved subgraph G0 . We will show, by induction on r, that there are r + 1 sets A1, A2, . . . , Ar+1 of size t such that every edge between Ai and Aj , with 1 ≤ i < j ≤ r + 1, is in G0 . For r = 0, there is nothing to prove. Given r > 0 and s = d3t/e, we apply the induction hypothesis to find r disjoint sets B1, B2, . . . , Br of size s such that the graph between every two disjoint sets is complete. Let U = V (G0 )\{B1 ∪ · · · ∪ Br} and let W be the set of vertices in U which are adjacent to at least t vertices in each Bi . We are going to estimate the number of edges missing between U and B1 ∪· · ·∪Br. Since every vertex in U\W is adjacent to fewer than t vertices in some Bi , we have that the number of missing edges is at least m˜ ≥ |U\W|(s − t) ≥ (n 0 − rs − |W|)  1 −  3  s. On the other hand, every vertex in G0 has at most ￾ 1 r −  2
n 0 missing edges. Therefore, counting over all vertices in B1 ∪ · · · ∪ Br, we have m˜ ≤ rs  1 r −  2  n 0 =  1 − r 2  sn0 . Therefore, |W|  1 −  3  s ≥ (n 0 − rs)  1 −  3  s −  1 − r 2  sn0 =   r 2 − 1 3  sn0 −  1 −  3  rs2 . Since , r and s are constants, we can make |W| large by making n 0 large. In particular, we may make |W| such that |W| >  s t r (t − 1). Every element in W has at least t neighbours in each Bi . There are at most ￾ s t
r ways to choose a t-element subset from each of B1∪· · ·∪Br. By the pigeonhole principle and the size of |W|, there must therefore be some subsets A1, . . . , Ar and a set Ar+1 of size t from W such that every vertex in Ar+1 is connected to every vertex in A1 ∪ · · · ∪ Ar. Since A1, . . . , Ar are already joined in the appropriate manner, this completes the proof. ✷ Note that a careful analysis of the proof shows that one may take t = c(r, ) log n. It turns out that this is also best possible (see example sheet). It remains to prove the Erd˝os-Stone-Simonovits theorem itself. 2