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.