# Turán's theorem

In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the largest or smallest graphs with given properties, and is a special case of the forbidden subgraph problem on the maximum number of edges in a graph that does not have a given subgraph.

An example of an ${\displaystyle n}$-vertex graph that does not contain any ${\displaystyle (r+1)}$-vertex clique ${\displaystyle K_{r+1}}$ may be formed by partitioning the set of ${\displaystyle n}$ vertices into ${\displaystyle 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 ${\displaystyle 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's theorem, and the Turán graphs giving its extreme case, were first described and studied by Hungarian mathematician Pál Turán in 1941.[1] The special case of the theorem for triangle-free graphs is known as Mantel's theorem; it was stated in 1907 by Willem Mantel, a Dutch mathematician.[2]

## Statement

Turán's theorem states that every graph ${\displaystyle G}$  with ${\displaystyle n}$  vertices that does not contain ${\displaystyle K_{r+1}}$  as a subgraph has a number of edges that is at most

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

The same formula gives the number of edges in the Turán graph ${\displaystyle T(n,r)}$ , so it is equivalent to state Turán's theorem in the form that, among the ${\displaystyle n}$ -vertex simple graphs with no ${\displaystyle (r+1)}$ -cliques, ${\displaystyle T(n,r)}$  has the maximum number of edges.[3]

## Proofs

Aigner & Ziegler (2018) list five different proofs of Turán's theorem.[3]

Turán's original proof uses induction on the number of vertices. Given an ${\displaystyle n}$ -vertex ${\displaystyle K_{r+1}}$ -free graph with more than ${\displaystyle r}$  vertices and a maximal number of edges, the proof finds a clique ${\displaystyle K_{r}}$  (which must exist by maximality), removes it, and applies the induction to the remaining ${\displaystyle (n-r)}$ -vertex subgraph. Each vertex of the remaining subgraph can be adjacent to at most ${\displaystyle r-1}$  clique vertices, and summing the number ${\displaystyle (n-r)(r-1)}$  of edges obtained in this way with the inductive number of edges in the ${\displaystyle (n-r)}$ -vertex subgraph gives the result.[1][3]

A different proof by Paul Erdős finds the maximum-degree vertex ${\displaystyle v}$  from a ${\displaystyle K_{r+1}}$ -free graph and uses it to construct a new graph on the same vertex set by removing edges between any pair of non-neighbors of ${\displaystyle v}$  and adding edges between all pairs of a neighbor and a non-neighbor. The new graph remains ${\displaystyle K_{r+1}}$ -free and has at least as many edges. Repeating the same construction recursively on the subgraph of neighbors of ${\displaystyle v}$  eventually produces a graph in the same form as a Turán graph (a collection of ${\displaystyle p}$  independent sets, with edges between each two vertices from different independent sets) and a simple calculation shows that the number of edges of this graph is maximized when all independent set sizes are as close to equal as possible.[3][4]

Motzkin & Straus (1965) prove Turán's theorem using the probabilistic method, by seeking a discrete probability distribution on the vertices of a given ${\displaystyle K_{r+1}}$ -free graph that maximizes the expected number of edges in a randomly chosen induced subgraph, with each vertex included in the subgraph independently with the given probability. For a distribution with probability ${\displaystyle p_{i}}$  for vertex ${\displaystyle v_{i}}$ , this expected number is ${\displaystyle \textstyle \sum _{(v_{i},v_{j})\in E(G)}p_{i}p_{j}}$ . Any such distribution can be modified, by repeatedly shifting probability between pairs of non-adjacent vertices, so that the expected value does not decrease and the only vertices with nonzero probability belong to a clique, from which it follows that the maximum expected value is at most ${\displaystyle (r-1)/2r}$ . Therefore, the expected value for the uniform distribution, which is exactly the number of edges divided by ${\displaystyle 1/n^{2}}$ , is also at most ${\displaystyle (r-1)/2r}$ , and the number of edges itself is at most ${\displaystyle n^{2}(r-1)/2r}$ .[3][5]

A proof by Noga Alon and Joel Spencer, from their book The Probabilistic Method, considers a random permutation of the vertices of a ${\displaystyle K_{r+1}}$ -free graph, and the largest clique formed by a prefix of this permutation. By calculating the probability that any given vertex will be included, as a function of its degree, the expected size of this clique can be shown to be ${\displaystyle \textstyle \sum 1/(n-d_{i})}$ , where ${\displaystyle d_{i}}$  is the degree of vertex ${\displaystyle v_{i}}$ . There must exist a clique of at least this size, so ${\displaystyle \textstyle r\geq \sum 1/(n-d_{i})}$ . Some algebraic manipulation of this inequality using the Cauchy–Schwarz inequality and the handshaking lemma proves the result.[3] See Method of conditional probabilities § Turán's theorem for more.

Aigner and Ziegler call the final one of their five proofs "the most beautiful of them all"; its origins are unclear. It is based on a lemma that, for a maximal ${\displaystyle K_{r+1}}$ -free graph, non-adjacency is a transitive relation, for if to the contrary ${\displaystyle (u,v)}$  and ${\displaystyle (v,w)}$  were non-adjacent and ${\displaystyle (u,w)}$  were adjacent one could construct a ${\displaystyle K_{r+1}}$ -free graph with more edges by deleting one or two of these three vertices and replacing them by copies of one of the remaining vertices. Because non-adjacency is also symmetric and reflexive (no vertex is adjacent to itself), it forms an equivalence relation whose equivalence classes give any maximal graph the same form as a Turán graph. As in the second proof, a simple calculation shows that the number of edges is maximized when all independent set sizes are as close to equal as possible.[3]

## Mantel's theorem

The special case of Turán's theorem for ${\displaystyle r=2}$  is Mantel's theorem: The maximum number of edges in an ${\displaystyle n}$ -vertex triangle-free graph is ${\displaystyle \lfloor n^{2}/4\rfloor .}$ [2] In other words, one must delete nearly half of the edges in ${\displaystyle K_{n}}$  to obtain a triangle-free graph.

A strengthened form of Mantel's theorem states that any Hamiltonian graph with at least ${\displaystyle n^{2}/4}$  edges must either be the complete bipartite graph ${\displaystyle 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.[6]

Another strengthening of Mantel's theorem states that the edges of every ${\displaystyle 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 graph's intersection number (the minimum number of cliques needed to cover all its edges) is at most ${\displaystyle \lfloor n^{2}/4\rfloor }$ .[7]