Turán's theorem

From Wikipedia, the free encyclopedia

In graph theory, Turán's theorem is a result on the number of edges in a K_s+1-free graph. Suppose we have given the graph K_n. We can easily obtain an K_s+1-free graph by deleting some edges.

For example, we can partition the set of vertices into s parts of equal size (or almost equal size). Then we delete all the edges which take place in only one part. By this construction we obtain the Turán graph T(n,s). And we have to delete the fraction 1/s of all the edges in K_n. So there remains the fraction (s-1)/s of all the edges in K_n.

Turán's theorem now says that this is best possible:

Turán [1941]: Let G be any subgraph of K_n such that G is K_s+1 -free. Then the number of edges in G is at most

$\frac{s-1}{s}\cdot\frac{n^2}{2} = \left( 1-\frac{1}{s} \right) \cdot\frac{n^2}{2}.$

An equivalent formulation is the following:

Turán [1941]: Among the n-vertex simple graphs with no r+1-cliques, T(n,r) has the maximum number of edges.

Proof:

Let $G$ be an n-vertex simple graph with no r+1-clique and with the maximum number of edges.

Claim 1:Graph

G

does not contain any three vertices

u, v, w

such that

G

contains

edge $u v$ , but does not contain edges $u w$ and $v w$ . (This claim is equivalent to the relation x~y iff x not connected to y being an equivalence relation. ~ is always reflexive and symmetric, but only in special cases is it transitive. ~ is not transitive precisely when we have u,v and w with u~w and w~v without u~v.)

We assume the claim is false. We construct a new n-vertex simple graph $G'$ that contains no r+1-clique but has more edges than $G$ .

Case 1: $d (w) < d (u)$ or $d (v) < d (u)$

Assume that $d (w) < d (u)$ . Delete vertex $w$ and create a copy of vertex $u$ (with all of the same neighbors as $u$ ); call it $u'$ . Any clique in the new graph contains at most one vertex among ${u, u'}$ . So this new graph does not contain any r+1-clique. However, it contains more edges: $| E (G') | = | E (G) | - d (w) + d (u) > | E (G) | .$

Case 2: $d(w)\geq d(u)$ and $d(w)\geq d(v)$

Delete vertices $u$ and $v$ and create two new copies of vertex $w$ . Again, the new graph does not contain any r+1-clique. However it contains more edges: $|E(G')| = |E(G)| -(d(u) + d(v) - 1) + 2d(w) \geq |E(G)| + 1$ .

This proves Claim 1.

The claim proves that we can partition the vertices of $G$ into equivalence classes based on their nonneighbors; i.e. two vertices are in the same equivalence class if they are nonadjacent. This implies that $G$ is a complete multipartite graph (where the parts are the equivalence classes).

Claim 2: The number of edges in a complete k-partite graph is maximized when the size of the parts differs by at most one.

If G is a complete k-partite graph with parts A and B and $| A | > | B | + 1$ , then we can increase the number of edges in G by moving a vertex from part A to part B. By moving a vertex from part A to part B, we lose $| B |$ edges, but gain $| A | - 1$ edges. Thus, we gain at least $|A|-1-|B|\geq 1$ edge. This proves Claim 2.

This proof shows that the Turan graph has the maximum number of edges. Additionally, the proof shows that the Turan graph is the only graph that has the maximum number of edges. $\Box$