Combinatorics • Topic 39

Turán's Theorem

Turán's Theorem is the starting point of Extremal Graph Theory. It answers the question: "What is the maximum number of edges a graph can have without containing a specific subgraph (like a triangle or $K_{r}$ )?"

Mantel's Theorem (Special Case)

The simplest case involves avoiding triangles (

K_{3}

Theorem (Mantel's Theorem)

The maximum number of edges in a graph with

n

vertices that contains no triangle (

K_{3}

) is:

⌊ \frac{n ^{2}}{4} ⌋

This maximum is achieved by the complete bipartite graph

K_{⌊ n /2 ⌋, ⌈ n /2 ⌉}

Turán Graphs

To avoid a complete graph

K_{r + 1}

, we construct a Turán Graph

T (n, r)

Partition the $n$ vertices into $r$ sets as equally as possible.
Connect two vertices if and only if they are in different sets.
This is a complete multipartite graph.

General Statement

Theorem (Turán's Theorem)

Among all graphs with

n

vertices that do not contain

K_{r + 1}

, the unique graph with the maximum number of edges is the Turán Graph

T (n, r)

Edge Count

The number of edges in

T (n, r)

is approximately:

∣ E ∣ \approx (1 - \frac{1}{r}) \frac{n ^{2}}{2}

Practice Problems

Exercise (Problem 1)

What is the maximum number of edges in a graph with 10 vertices that has no triangle?

Exercise (Problem 2)

Prove that any graph with

2 n

vertices and

n^{2} + 1

edges contains a triangle.

Exercise (Problem 3)

Find the maximum number of edges in a graph with

n

vertices that contains no

K_{4}

(tetrahedron).