Turán's theorem

In graph theory, Turán's theorem is a result on the number of edges in a K_r+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. The resulting graph is 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 K_r+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 K_r+1 -free. Then the number of edges in G is at most

${\displaystyle {\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 ${\displaystyle T(n,r)}$. For example, with ${\displaystyle 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 ${\displaystyle |A|=12}$ and ${\displaystyle |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 ${\displaystyle 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 ${\displaystyle k<r+1}$.

Define a relation over the vertices of G:

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

It suffices to show that ${\displaystyle \sim }$ is an equivalence relation, as it would partition the vertices of G into k equivalence classes ${\displaystyle 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 ${\displaystyle k<r+1}$. 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 ${\displaystyle u\sim v}$ and ${\displaystyle v\sim w}$, but ${\displaystyle u\not \sim w}$. Letting ${\displaystyle d(x)}$ denote the degree of a vertex x, one of the following must be true:

Case 1: ${\displaystyle d(v)<d(u){\text{ or }}d(v)<d(w)}$

Assume that ${\displaystyle d(v)<d(u)}$. 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:

${\displaystyle |E(G')|=|E(G)|-d(v)+d(u)>|E(G)|.}$

Case 2: ${\displaystyle d(v)\geq d(u)}$ and ${\displaystyle 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:

${\displaystyle |E(G')|=|E(G)|-(d(u)+d(w)-1)+2d(v)\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 ${\displaystyle \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 ${\displaystyle |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 ${\displaystyle |B|}$ edges, but gains ${\displaystyle |A|-1}$ edges. Thus, it gains at least ${\displaystyle |A|-1-|B|\geq 1}$ edge. This proves Claim 2.

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

The only other possibility is that it has fewer than r parts. But in this case one can treat it as a r-partite graph in which some of the parts are empty and apply the same reasoning as in claim 2.

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 ${\displaystyle \lfloor n^{2}/4\rfloor .}$ (Mantel 1907)

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

A strengthened form of Mantel's theorem states that any hamiltonian graph with at least n²/4 edges must either be the complete bipartite graph K_n/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 ${\displaystyle \lfloor n^{2}/4\rfloor }$ cliques which are either edges or triangles. As a corollary, the intersection number is at most ${\displaystyle \lfloor n^{2}/4\rfloor }$ (Erdős, Goodman & Pósa 1966).

See also

• Extremal graph theory
• Erdős–Stone theorem
• A probabilistic proof of Turán's theorem
• Turán's method in analytic number theory
• Forbidden subgraph problem

References

• Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Berlin, New York: Springer-Verlag.
• Bondy, J. A. (1971), "Pancyclic graphs I", Journal of Combinatorial Theory, Series B, 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5.
• Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106–112, doi:10.4153/CJM-1966-014-3, MR 0186575.
• Mantel, W. (1907), "Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)", Wiskundige Opgaven, 10: 60–61.
• Turán, Paul (1941), "On an extremal problem in graph theory", Matematikai és Fizikai Lapok (in Hungarian), 48: 436–452.
• West, Douglas Brent (1999) [1996], Introduction to Graph Theory (2nd ed.), Prentice Hall, ISBN 978-0-13-014400-3.