In graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.
Contents
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 mostAn 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: The proof consists of two claims about G, which we outline, before proving. The first claim is that G must be a complete r-partite graph (although it is stated more technically below). In other words, we can partition the vertex set into r subsetsAssume the claim is false. Construct a new n-vertex simple graph G′ that contains no (r + 1)-clique but has more edges than G, as follows:
Case 1:
Assume that
Case 2:
Delete vertices u and v and create two new copies of vertex w. Again, the new graph does not contain any (r + 1)-clique. However it contains more edges:
This proves Claim 1.
The claim proves that one can partition the vertices of G into equivalence classes based on their non-neighbors; i.e. two vertices are in the same equivalence class if they are nonadjacent. This implies that G is a complete multipartite graph (where the parts are the equivalence classes).
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
This proof shows that the Turan graph has the maximum number of edges. Additionally, the proof shows that the Turan graph is the only graph that has the maximum number of edges.
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 isIn 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