a. Prove that any graph without a -clique that has a maximum number of edges is a complete -partite graph. In other words, the graph can be partitioned into subsets of vertices such that each vertex is connected to all others except those in its own subset.
b. Prove Turán's theorem in the case of a complete -partite graph.
c. Let be a graph with vertices with respective degrees . Show that the maximum cardinality of a clique in is bounded below by
From this, derive a proof of theorem 6.