Turán's theorem

In graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.

An n-vertex graph that does not contain any (r + 1)-vertex clique may be formed by partitioning the set of vertices into r parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. We call the resulting graph the Turán graph T(n, r). Turán's theorem states that the Turán graph has the largest number of edges among all Kr+1-free n-vertex graphs.

Turán graphs were first described and studied by Hungarian mathematician Pál Turán in 1941, though a special case of the theorem was stated earlier by Mantel in 1907.

Formal statement

Turán's Theorem. Let G be any graph with n vertices, such that G is Kr+1 -free. Then the number of edges in G is at most
${\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}.$ An equivalent formulation is the following:

Turán's Theorem (Second Formulation). 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.

Overview We show that an n-vertex graph with no (r + 1)-clique and the maximum number of edges must be the Turàn graph $T(n,r)$ . For example, with $n=23$ , to create the graph with as many edges as possible that contains no triangles, subdivide the vertices into two groups: A and B, where $|A|=12$ and $|B|=11$ . Put an edge between every vertex in A and every vertex in B but put no edges within A or B. This gives us a total of $11\cdot 12=132\leq {\frac {23^{2}}{2}}\left(1-{\frac {1}{2}}\right)=132.25$ .

Claim 1: G is a complete k-partite graph with $k .

Define a relation over the vertices of G:

$x\sim y$ if and only if x is not adjacent to y.

It suffices to show that $\sim$ is an equivalence relation, as it would partition the vertices of G into k equivalence classes $S_{1},\ldots ,S_{k}$ such that no vertices within the same class are adjacent, and every two vertices from different classes share an edge. Furthermore, as the subgraph induced by choosing exactly one vertex from each equivalence class is a k-clique, it follows that $k . Clearly the relation is reflexive (as G contains no self-loops), and symmetric, so it suffices to show that the relation is transitive.

Assume for a contradiction that the relation is not transitive. In other words, there exist u, v, w such that $u\sim v$ and $v\sim w$ , but $u\not \sim w$ . Letting $d(x)$ denote the degree of a vertex x, one of the following must be true:

Case 1: $d(v) Assume that $d(v) . Delete vertex v and create a copy of vertex u (with all of the same neighbors as u); call it u′. Call this new graph G'. Since u and u' are not adjacent, the largest clique in G' can be no bigger than the largest clique in G. However, G' contains more edges:

$|E(G')|=|E(G)|-d(w)+d(u)>|E(G)|.$ Case 2: $d(v)\geq d(u)$ and $d(v)\geq d(w)$ Delete vertices u and w and create two new copies of vertex v. As in Case 1, the new graph G' cannot contain any (r + 1)-cliques, but does contains more edges:

$|E(G')|=|E(G)|-(d(u)+d(v)-1)+2d(w)\geq |E(G)|+1.$ Since in either case, a graph G' with more edges than G can be constructed, which is a contradiction, it follows that $\sim$ is transitive, and thus an equivalence relation.

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, the graph loses $|B|$ edges, but gains $|A|-1$ edges. Thus, it gains at least $|A|-1-|B|\geq 1$ edge. This proves Claim 2.

Claim 3: G must be a Turàn graph.

From Claim 1, we know that G is a complete k-partite graph, but if $k , then by the pigeonhole principle there would be one part $S_{i}$ with $|S_{i}|\geq {\frac {n}{r}}+2$ vertices, and another part $S_{j}$ with $|S_{j}|\leq {\frac {n}{r}}$ vertices. By Claim 2, this contradicts the assumption that G has a maximal number of edges. Thus, G must be a complete r-partite graph with sets $S_{1},S_{2},\ldots ,S_{r}$ , where for all i,

$\left\lfloor {\frac {n}{r}}\right\rfloor \leq |E(S_{i})|\leq \left\lceil {\frac {n}{r}}\right\rceil$ .

Letting $m=n{\bmod {r}}$ , it is straightforward arithmetic to show that there must be $m$ partitions with $\left\lceil {\frac {n}{r}}\right\rceil$ vertices, and $r-m$ partitions with $\left\lfloor {\frac {n}{r}}\right\rfloor$ vertices. Thus, the number of edges in G is

${\frac {1}{2}}\left(m\cdot \left\lceil {\frac {n}{r}}\right\rceil \cdot (n-\left\lceil {\frac {n}{r}}\right\rceil )+(r-m)\cdot \left\lfloor {\frac {n}{r}}\right\rfloor \cdot (n-\left\lfloor {\frac {n}{r}}\right\rfloor )\right)\leq {\frac {1}{2}}\cdot n\cdot \left(n-{\frac {n}{r}}\right)={\frac {n^{2}}{2}}\left(1-{\frac {1}{r}}\right)$ Mantel's theorem

As a special case of Turán's theorem, for r = 2, one obtains:

Mantel's Theorem. The maximum number of edges in an n-vertex triangle-free graph is $\lfloor n^{2}/4\rfloor .$ (Mantel 1907)

In other words, one must delete nearly half of the edges in Kn to obtain a triangle-free graph.

A strengthened form of Mantel's theorem states that any hamiltonian graph with at least n2/4 edges must either be the complete bipartite graph Kn/2,n/2 or it must be pancyclic: not only does it contain a triangle, it must also contain cycles of all other possible lengths up to the number of vertices in the graph (Bondy 1971).

Another strengthening of Mantel's theorem states that the edges of every n-vertex graph may be covered by at most $\lfloor n^{2}/4\rfloor$ cliques which are either edges or triangles. As a corollary, the intersection number is at most $\lfloor n^{2}/4\rfloor$ (Erdős, Goodman & Pósa 1966).