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 Kr+1-free n-vertex graphs.
- 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
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.
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 . For example, with , to create the graph with as many edges as possible that contains no triangles, subdivide the vertices into two groups: A and B, where and . 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 .
Claim 1: G is a complete k-partite graph with .
Define a relation over the vertices of G:
- if and only if x is not adjacent to y.
It suffices to show that is an equivalence relation, as it would partition the vertices of G into k equivalence classes 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 . 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 and , but . Letting denote the degree of a vertex x, one of the following must be true:
Assume that . 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:
Case 2: and
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:
Since in either case, a graph G' with more edges than G can be constructed, which is a contradiction, it follows that 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 , 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 edges, but gains edges. Thus, it gains at least 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.
As a special case of Turán's theorem, for r = 2, one obtains:
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 cliques which are either edges or triangles. As a corollary, the intersection number is at most (Erdős, Goodman & Pósa 1966).
- 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) , Introduction to Graph Theory (2nd ed.), Prentice Hall, ISBN 978-0-13-014400-3.