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.
An example of 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 Kr+1-free n-vertex graphs.
Turán's theorem, and the Turán graphs giving its extreme case, were first described and studied by Hungarian mathematician Pál Turán in 1941.[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.[2]
Statement
Turán's theorem states that every graph with vertices that does not contain as a subgraph has a number of edges that is at most
The same formula gives the number of edges in the Turán graph , so it is equivalent to state Turán's theorem in the form that, among the -vertex simple graphs with no -cliques, has the maximum number of edges.[3]
Proofs
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 -vertex -free graph with more than vertices and a maximal number of edges, the proof finds a clique (which must exist by maximality), removes it, and applies the induction to the remaining -vertex subgraph. Each vertex of the remaining subgraph can be adjacent to at most clique vertices, and summing the number of edges obtained in this way with the inductive number of edges in the -vertex subgraph gives the result.[1][3]
A different proof by Paul Erdős finds the maximum-degree vertex from a -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 and adding edges between all pairs of a neighbor and a non-neighbor. The new graph remains -free and has at least as many edges. Repeating the same construction recursively on the subgraph of neighbors of eventually produces a graph in the same form as a Turán graph (a collection of 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 -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 for vertex , this expected number is . 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 . Therefore, the expected value for the uniform distribution, which is exactly the number of edges divided by , is also at most , and the number of edges itself is at most .[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 -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 , where is the degree of vertex . There must exist a clique of at least this size, so . 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 -free graph, non-adjacency is a transitive relation, for if to the contrary and were non-adjacent and were adjacent one could construct a -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]
Mantel's theorem
The special case of Turán's theorem for is Mantel's theorem: The maximum number of edges in an -vertex triangle-free graph is [2] 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 edges must either be the complete bipartite graph 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 -vertex graph may be covered by at most 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 .[7]
See also
- Erdős–Stone theorem, a generalization of Turán's theorem from forbidden cliques to forbidden Turán graphs
References
- ^ a b Turán, Paul (1941), "On an extremal problem in graph theory", Matematikai és Fizikai Lapok (in Hungarian), 48: 436–452
- ^ a b 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
- ^ a b c d e f g Aigner, Martin; Ziegler, Günter M. (2018), "Chapter 41: Turán's graph theorem", Proofs from THE BOOK (6th ed.), Springer-Verlag, pp. 285–289, doi:10.1007/978-3-662-57265-8_41, ISBN 978-3-662-57265-8
- ^ Erdős, Pál (1970), "Turán Pál gráf tételéről" [On the graph theorem of Turán] (PDF), Matematikai Lapok (in Hungarian), 21: 249–251, MR 0307975
- ^ Motzkin, T. S.; Straus, E. G. (1965), "Maxima for graphs and a new proof of a theorem of Turán", Canadian Journal of Mathematics, 17: 533–540, doi:10.4153/CJM-1965-053-6, MR 0175813
- ^ 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