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.

[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.

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

This increases the number of edges by our maximality assumption and keeps the graph

Repeating this argument eventually produces a graph in the same form as a Turán graph, which is a collection of independent sets, with edges between each two vertices from different independent sets.

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] This proof, as well as the Zykov Symmetrization proof, involve reducing to the case where the graph is a complete multipartite graph, and showing that the number of edges is maximized when there are

independent sets of size as close as possible to equal.

To prove the Turán Graph is optimal, one can argue that no two

This can be seen by examining the changes to either side of the above expression for the number of edges, or by noting that the degree of the moved vertex increases.

[3][5] The key claim in this proof was independently found by Caro and Wei.

This proof is due to Noga Alon and Joel Spencer, from their book The Probabilistic Method.

The proof attempts to find such an independent set as follows: A vertex of degree

Applying this fact to the complement graph and bounding the size of the chosen set using the Cauchy–Schwarz inequality proves Turán's theorem.

[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".

As in the maximal degree vertex proof, a simple calculation shows that the number of edges is maximized when all independent set sizes are as close to equal as possible.

is Mantel's theorem: The maximum number of edges in an

A strengthened form of Mantel's theorem states that any Hamiltonian graph with at least

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.

Turán's theorem shows that the largest number of edges in a

, so the Turán graph establishes the lower bound.

The general question of how many edges can be included in a graph without a copy of some

Another natural extension of Turán's theorem is the following question: if a graph has no

Turan's theorem states that if a graph has edge homomorphism density strictly above

To deal with this, weighted graphs or graphons are often considered.

In particular, graphons contain the limit of any infinite sequence of graphs.

density is as follows:Take a number of vertices approaching infinity.

s. The lower bound was proven by Razborov (2008)[10] for the case of triangles, and was later generalized to all cliques by Reiher (2016)[11].