Third proof let a be the largest independent set in the graph G.since the neighborhood of everv vertexisan independent we must have d()A.Let B be the complement of A.Every edge in G must meet a vertex of B.Therefore,the number of edges in G satisfies 4a≤Σs≤（生）- Suppose that n is even.Then equality holds if and only if A =B=n/2,d(z)=|Al for every B and B has no internal edges.This easily implies that the unique structure with n2/4 edges is a bipartite graph with equal partite sets.For n odd,the number of edges is maximised when A [n/2] and B=n/2].Again,this yields a unique bipartite structure. ▣ The last proof tells us that not only is [n2/4]the maximum number of edges in a triangle-free graph but also that any triangle-free graph with this number of edges is bipartite with partite sets of almost equal size. The natural generalisation of this theorem to cliques of size r is the following,proved by Paul Turan in1941. Theorem 2 (Turan's theorem)If a graph G on n vertices contains no copy of Kr+,the complete graph onr+1 vertices,then it contains at most (1-1)edges. First proof By induction on n.The theorem is trivially true for n=1,2....,.We will therefore assume that it is true for all values less than n and prove it for n.Let G be a graph on n vertices which contains no K+and has the maximum possible number of edges.Then G contains copies of K.Otherwise,we could add edges to G,contradicting maximality. Let A be a clique of size r and let B be its complement.Since B has size n-r and contains no Kr+ there are at most (1-1)edges in B.Moreover,since every vertex in B can have at most r-1 neighbours in A,the number of edges between A and B is at most (r-1)(n-r).Summing,we see that e4@=ea+caa+B≤（付）+G-10a-m+(-)a,=(-) 21 where eA,eA.B and eg are the number of edges in A,between A and B and in B respectively.The theorem follows. ■ Second proof We again assume that has the maximum possible number of edges.We will begin by proving that if ry E(G)and yz E(G),then rzE(G).This implies that the property of not being connected in G is an equivalence relation.This in turn will imply that the graph must be a complete multipartite graph. Suppose,for contradiction,that ry E(G)and yz(G),but xz E(G).If d(y)<d(a)then we m a new Kr+1-free graph G'by deleting y and creating a new copy of the vertex say Since a eioue in can contain at most one of andwe sce thatse Moreover. E(G)=E(G)I-d(y)+d()>E(G), contradicting the maximality of G.A similar conclusion holds if d(y)<d(z).We may therefore assume that d(y)>d(x)and d(y)>d(z).We create a new graph G"by deleting x and z and creating two extra copies of the vertex y.Again,this has no Kr+and 1E(G")1=1E(G-(dx)+d(z)-1)+2d(y)>1E(G 2 Third proof Let A be the largest independent set in the graph G. Since the neighborhood of every vertex x is an independent set, we must have d(x) ≤ |A|. Let B be the complement of A. Every edge in G must meet a vertex of B. Therefore, the number of edges in G satisfies e(G) ≤ X x∈B d(x) ≤ |A||B| ≤  |A| + |B| 2 2 = n 2 4 . Suppose that n is even. Then equality holds if and only if |A| = |B| = n/2, d(x) = |A| for every x ∈ B and B has no internal edges. This easily implies that the unique structure with n 2/4 edges is a bipartite graph with equal partite sets. For n odd, the number of edges is maximised when |A| = dn/2e and |B| = bn/2c. Again, this yields a unique bipartite structure. ✷ The last proof tells us that not only is bn 2/4c the maximum number of edges in a triangle-free graph but also that any triangle-free graph with this number of edges is bipartite with partite sets of almost equal size. The natural generalisation of this theorem to cliques of size r is the following, proved by Paul Tur´an in 1941. Theorem 2 (Tur´an’s theorem) If a graph G on n vertices contains no copy of Kr+1, the complete graph on r + 1 vertices, then it contains at most ￾ 1 − 1 r
n 2 2 edges. First proof By induction on n. The theorem is trivially true for n = 1, 2, . . . , r. We will therefore assume that it is true for all values less than n and prove it for n. Let G be a graph on n vertices which contains no Kr+1 and has the maximum possible number of edges. Then G contains copies of Kr. Otherwise, we could add edges to G, contradicting maximality. Let A be a clique of size r and let B be its complement. Since B has size n − r and contains no Kr+1, there are at most ￾ 1 − 1 r
(n−r) 2 2 edges in B. Moreover, since every vertex in B can have at most r − 1 neighbours in A, the number of edges between A and B is at most (r − 1)(n − r). Summing, we see that e(G) = eA + eA,B + eB ≤  r 2  + (r − 1)(n − r) +  1 − 1 r  (n − r) 2 2 =  1 − 1 r  n 2 2 , where eA, eA,B and eB are the number of edges in A, between A and B and in B respectively. The theorem follows. ✷ Second proof We again assume that G contains no Kr+1 and has the maximum possible number of edges. We will begin by proving that if xy /∈ E(G) and yz /∈ E(G), then xz /∈ E(G). This implies that the property of not being connected in G is an equivalence relation. This in turn will imply that the graph must be a complete multipartite graph. Suppose, for contradiction, that xy /∈ E(G) and yz /∈ E(G), but xz ∈ E(G). If d(y) < d(x) then we may construct a new Kr+1-free graph G0 by deleting y and creating a new copy of the vertex x, say x 0 . Since any clique in G0 can contain at most one of x and x 0 , we see that G0 is Kr+1-free. Moreover, |E(G 0 )| = |E(G)| − d(y) + d(x) > |E(G)|, contradicting the maximality of G. A similar conclusion holds if d(y) < d(z). We may therefore assume that d(y) ≥ d(x) and d(y) ≥ d(z). We create a new graph G00 by deleting x and z and creating two extra copies of the vertex y. Again, this has no Kr+1 and |E(G 00)| = |E(G)| − (d(x) + d(z) − 1) + 2d(y) > |E(G)|, 2