7.3. Complete Subgraphs

First we examine the  case.

Lemma 7.5. Every graph of order  and size at least  con-tains a triangle .

Proof.

We proceed by induction on n.

For  the only graph of order n and size at least  is , which is a triangle.

For  the only graphs with the given conditions are  and . Both graphs contain triangle.

Thus the result is true for  and .

Assume that every graph of order k and size at least  contains a triangle for each integer k with , where .

Now let G be a graph of order n containing at least  edges.

Let u and v be adjacent vertices of G and define .

If u and v are mutually adjacent to a vertex of H, then G contains a triangle.

Otherwise, each vertex of H is adjacent to at most one of u and v, and so, the size of H is at least

By the induction hypothesis, H contains a triangle, consequently, so does G.

Theorem 7.6. .

Proof.

The bipartite graph  has order n and size and it is triangle-free. So, from the

Lemma the statement follows immediately.

We can generalize the above Lemma:

Theorem 7.7. .

For  and  the above Theorem gives that every graph of order 10 and size at least 35 contains  as a subgraph.

However, every graph of order 10 and size 34 also contains  as a subgraph.

So, the upper bound is not sharp for .

The exact values were given by Turán.

The Problem: What is the maximal number of edges in a graph of order n not containing a  (a complete graph of order n)? ?

If G is -partite then it does not contain a  since every vertex class of G  contains at most one vertex of a complete subgraph.

Consequence:  the maximal size of an -partite graph of order n.

Is there a unique -partite graph of order n that has maximal size? How looks like this graph?

Let  be the -partite complete graph which has in k. class

vertices.

Let we realize that  is the complete -partite graph of order n whose classes are as equal as possible: there are  vertices in the kth class and .

Theorem 7.8. If G is an -partite graph of order n and maxim-al size then .

Proof.

Let G be a graph with maximal size and suppose the classes of G are not as equal as possible.

Say, there are  vertices in the ith class and  in the jth class and .

Transfer one vertex from the jth class to the ith class.

The number of ignored edges:   

The number of new edges:         

So the difference is: .

So we would increase the number of edges. This is a contradiction.

Denote the number of edges in .

Consequence: .

The fundamental theorem of Turán states that this trivial inequality, in fact, an equality for every n and r.

First, we shall show that the degree sequence of a graph without a Kr is dominated by the degree sequence of an -partite graph. In view of the remarks above this will imply Turán's theorem.