Turán's theorem

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]

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]

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]

• Erdős–Stone theorem, a generalization of Turán's theorem from forbidden cliques to forbidden Turán graphs