so again we have a contradiction. We now know that the graph is a complete multipartite graph.Clearly,it can have at mostparts We will show that the number of edges is maximised when all of these parts have sizes which differ by at most one.Indeed,if there were two parts A and B with A>B+1,we could increase the number of edges in G by moving one vertex from A to B.We would lose Bl edges by doing this,but gain A]-1.Overall,we would gain A]-1-|B]2 1. ◇ This second proof also determines the structure of the extremal graph,that is,it must be r-partite with all parts having size as close as possible.So if n=mr+,we get g sets of size m+1 and r-q sets of size m. 3so again we have a contradiction. We now know that the graph is a complete multipartite graph. Clearly, it can have at most r parts. We will show that the number of edges is maximised when all of these parts have sizes which differ by at most one. Indeed, if there were two parts A and B with |A| > |B| + 1, we could increase the number of edges in G by moving one vertex from A to B. We would lose |B| edges by doing this, but gain |A| − 1. Overall, we would gain |A| − 1 − |B| ≥ 1. ✷ This second proof also determines the structure of the extremal graph, that is, it must be r-partite with all parts having size as close as possible. So if n = mr + q, we get q sets of size m + 1 and r − q sets of size m. 3