# Complete subgraphs and Turán's theorem

We've seen the maximum size of a graph containing no path of a certain length. What is the maximum size of a graph containing no ?

Definition 6..7 (-partite graph)

An -partite graph is a graph with a vertex partition so that each is an independent set (i.e. is empty of edges).

Certainly no -partite graph contains .

What is the maximum size of a -partite graph? Clearly we should look at a complete -partite graph, where any pair of vertices in different classes are joined.

Suppose two class orders differ by more than 1, . Moving a vertex from to increases the number of edges by . Therefore the classes are as equal as possible.

Definition 6..8 (Turán graph, and )

The Turán graph is the complete -partite graph of order with classes orders or .

We write .

Theorem 6..9 (Turán's theorem; maximum sized graph not containing )

Let be a free graph of order with then = .

Proof. The vertices in with least degree belong to vertex class of greatest order, by removing one of these we get .

 (6.1)

Furthermore the degrees are as equal as possible.

 (6.2)

By induction on . True for , because is for .

In general let be a spanning subgraph with edges. Certainly is also free. Now apply the handshaking lemma to

Using 6.2

Pick a vertex of minimum degree. Then is again -free.

by 6.1.

So by the induction hypothesis, is a complete -partite graph. In , cannot be joined to all vertex classes in , since otherwise would contain . So is -partite. But and is the only -partite graph of that size, so .

Adding any new edge to creates a , so .

Theorem 6..10 (Turán's theorem; alternative forumulation and proof)

Let be a -free graph with vertex set . Then there exists a -partite graph with vertex set , and for all .

Proof. By induction on .

Case trivial.

In general, we pick a vertex of of maximum degree.

Let . Then is free. Let .

By induction, there is a -partite graph with vertex set and . Form by joining every vertex in to .

Now construct by joining every vertex in to . Then is -partite. Need to show for all .

If , . But .

Otherwise, . . But . Now , so . Done.

Lemma 6..11 (Alternative formulation of Turán's theorem implies original)

Let be a free graph of order with then = .

Proof. Only remains to show , as certainly is the unique -partite graph of size . By previous theorem there exists a -partite graph with vertex set , and for all .

. Now certainly is -partite, and is the maximum number of edges of an -partite graph. So .

Lemma 6..12 (Variant on the alternative formulation of Turán's theorem)

Let be a graph of order , and let of degree . If , then .

Proof. Let . Let be a copy of with vertex set . Form an -partite graph by joining every vertex in to . Certainly .

Now , so if then .

Corollary 6..13 (Variant on alternative formulation of Turán's theorem)

If has order and size , then contains as a subgraph.

Proof. By induction on . Case is trivial.

In general we take a vertex with degree . By the last lemma as . By induction, contains , so contains .

Observation 6..14 (Method for finding in a graph)

This corollary gives us an algorithm for finding in a graph that has more edges than . Take vertex of degree . Let . Given with , take to be and to be a vertex of highest degree in .

By the lemma, , contains . Therefore .

John Fremlin 2010-02-17