Now we'll prove Mantel's Theorem,

recall that a triangle is a clique of size 3.

Mantel's Theorem says,

that a graph on

n vertices without triangles can only have at most floor of n_square/4 edges.

We will prove this theorem again by induction of n,

the number of vertices in our graph.

And we will consider two base cases, n=1 and n=2.

When n=1, graph can

contain only zero edges because there is only one vertex.

And actually floor of n_square/4 in this case is a floor of [inaudible] When n=2,

then a graph on two vertices can contain at most one edge,

and the floor of n_square/4 is exactly one.

So both base cases hold.

An induction assumption, induction hypothesis will be

that the statement of theorem holds for all graphs on at most k minus 2 vertices.

And the induction step would be to

show that this statement also holds for all graphs on at most k vertices.

Note that the step of the induction in this case is of size 2, and this is exactly

why we consider two base cases: we proved that for for graphs of size 1,

we proved it for graphs of size 2, and then

induction step of size 2 will carry on the statement for all integers.

Now we prove induction step.

Let us pick two connected vertices,

u and v. We want to say that the sum of

the degree of u and degree of v is at most n.

Indeed, assume it's greater than n,

then by the pigeonhole principle there exists some vertex x,

such that both u and v are connected to x, which forms a triangle.

But we know that our ground that doesn't contain any of these triangles,

so the degree of u plus the degree of v must be at most

n. Now let's remove u and v from our graph,

and let's denote the remaining graph by H. H now has only k minus 2 vertices.

So we can apply induction hypothesis to the graph H.

So by the induction hypothesis, the number of edges in the graph H

is at most floor of n_minus_2_square /4.

Let's now count the number of edges in G.

It has all edges from H and also edges going from vertices u and v.

We know the sum of zero degrees is at most n,

but these two degrees count the edge between u and v twice.

So the actual number of edges that

u and v have

is at most n minus 1.

So the number of edges in G is upper bounded by the number of edges in

H plus n minus 1. Now we just simplify

the expression n_minus_2_square, we know it's n_square minus 4n plus 4,

and when you divide minus_4n_plus_4 by 4,

you get the following expression: floor of

n_square/4 minus n_minus_1 plus n_minus_1.

Exactly what we wanted to prove.

There is a generalization of Mantel's Theorem which is called Turan's Theorem.

Mantel's Theorem says that if a graph doesn't contain cliques of size 3,

then there are few edges.

Turan's Theorem says that if a graph doesn't contain cliques of size r+1,

then there are some but few edges.

For example, if you take r to be 2 in Turan's Theorem,

you'll get exactly the statement of Mantel's Theorem.

And in fact both theorems are tight,which means that there are graphs

which have exactly this number of edges.

For Mantel's Theorem,

this would be a complete bipartite graph where the left part has n/2 vertices,

the right part has n/2 vertices, and the graph has all edges between these two parts.

This will be n_square/4 edges,

exactly the number from Mantel's Theorem.

For Turan's Theorem,

there is a more general tight example which is called the Turan graph.

You just partition all the vertices of the graph more or less

evenly in r parts and connect all pairs of vertices from different parts.