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

Answer rating: 100% (QA)

A bipantite goaph paa tition ed is a se of vestex th at can be n to two in depen den sets that is in... View the full answer