Turán's theorem


In graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.
An -vertex graph that does not contain any -vertex clique may be formed by partitioning the set of vertices into 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. Turán's theorem states that the Turán graph has the largest number of edges among all -free -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

An equivalent formulation is the following:

Proof

Let be an -vertex, simple graph with no -clique and with the maximum number of edges.
Overview We show that an -vertex graph with no -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: and, where and. Put an edge between every vertex in and every vertex in but put no edges within or. This gives us a total of.
Claim 1: is a complete -partite graph with.
Define a relation over the vertices of :
It suffices to show that is an equivalence relation, as it would partition the vertices of into 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 -clique, it follows that. Clearly the relation is reflexive, 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 such that and, but. Letting denote the degree of a vertex, one of the following must be true:
Case 1:
Assume that. Delete vertex and create a copy of vertex ; call it. Call this new graph. Since and are not adjacent, the largest clique in can be no bigger than the largest clique in. However, contains more edges:
Case 2: and
Delete vertices and and create two new copies of vertex. As in Case 1, the new graph cannot contain any -cliques, but does contains more edges:
Since in either case, a graph with more edges than 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 -partite graph is maximized when the size of the parts differs by at most one.
If is a complete -partite graph with parts and and, then we can increase the number of edges in by moving a vertex from part to part. By moving a vertex from part to part, the graph loses edges, but gains edges. Thus, it gains at least edge. This proves Claim 2.
Claim 3: must be a Turán graph.
The only other possibility is that it has fewer than parts. But in this case one can treat it as a -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:
In other words, one must delete nearly half of the edges in 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.
Another strengthening of Mantel's theorem states that the edges of every -vertex graph may be covered by at most cliques which are either edges or triangles. As a corollary, the intersection number is at most .