Turán's theorem

From Wikipedia, the free encyclopedia
  (Redirected from Turan theorem)
Jump to navigation Jump to search

In graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.

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[edit]

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.

Proof[edit]

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:

Case 1:

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.

From Claim 1, we know that G is a complete k-partite graph, but if , then by the pigeonhole principle there would be one part with vertices, and another part with vertices. By Claim 2, this contradicts the assumption that G has a maximal number of edges. Thus, G must be a complete r-partite graph with sets , where for all i,

.

Letting , it is straightforward arithmetic to show that there must be partitions with vertices, and partitions with vertices. Thus, the number of edges in G is

Mantel's theorem[edit]

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 is (Mantel 1907)

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

See also[edit]

References[edit]

  • 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) [1996], Introduction to Graph Theory (2nd ed.), Prentice Hall, ISBN 978-0-13-014400-3.