Let G be a simple graph on 2k vertices containing no triangles. Prove, by induction on k, that G has at most k2 edges, and give an example of a graph for which this upper bound is achieved. (This result is often called Turán’s extremal theorem.)

Theorem: Let G be a simple graph with 2n vertices and n2 edges. If G has no triangles, then G is the complete bipartite graph Kn,n.
*Use this theorem to help establish problem 2.44.
For each proof complete the following:

- State the hypotheses
- State the conclusions
- Clearly and precisely prove the conclusions from the hypotheses