turn's theorem

In graph theory Turn'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 partioned 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 Turn 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. Turn's theorem now says that this is best possible: Turn 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: Turn 1941: Among the n-vertex simple graphs with no r+1-cliques, T(n,r) has the maximum number of edges. Turn graphs were first described and studied by Hungarian mathematician Paul Turn in 1941. As a special case, for s = 2, one obtains Mantel's theorem: Mantel 1907 The maximum number of edges in an n-vertex triangle-free simple graph is

\lfloor n^2/4 \rfloor.

With other words: We have to delete half of the edges in K_n to obtain an triangle-free graph.

Turn's Theorem

See also