Added to Favorites

Popular Searches

Nearby Words

In graph theory, Turán's theorem is a result on the number of edges in a K_{r+1}-free graph.## Formal statement of the theorem

Formally, Turán's theorem may be stated as follows.## Proof

## See also

## References

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 K_{r+1}-free 'n''-vertex graphs.

Turán graphs were first described and studied by Hungarian mathematician Paul Turán in 1941, though a special case of the theorem was stated earlier by Mantel in 1907.

Let G be any subgraph of K_{n} such that G is K_{r+1} -free. Then the number of edges in G is at most

- $frac\{r-1\}\{r\}cdotfrac\{n^2\}\{2\}\; =\; left(1-frac\{1\}\{r\}\; right)\; cdotfrac\{n^2\}\{2\}.$

An equivalent formulation is the following:

Among the n-vertex simple graphs with no (r + 1)-cliques, T(n,r) has the maximum number of edges.

As a special case, for r = 2, one obtains Mantel's theorem:

The maximum number of edges in an n-vertex triangle-free graph is $lfloor\; n^2/4\; rfloor.$

In other words, one must delete nearly half of the edges in K_{n} to obtain a triangle-free graph.

Let $G$ be an n-vertex simple graph with no (r + 1)-clique and with the maximum number of edges.

- Claim 1: Graph $G$ does not contain any three vertices $u,v,w$ such that $G$ contains edge $uv$, but contains neither edge $uw$ nor $vw$.

Assume the claim is false. Construct a new n-vertex simple graph $G\text{'}$ that contains no (r + 1)-clique but has more edges than $G$, as follows:

Case 1: $d(w)\; <\; d(u)text\{\; or\; \}d(w)\; <\; d(v).$

Assume that $d(w)\; <\; d(u)$. Delete vertex $w$ and create a copy of vertex $u$ (with all of the same neighbors as $u$); call it $u\text{'}$. Any clique in the new graph contains at most one vertex among $\{u,u\text{'}\}$. So this new graph does not contain any (r + 1)-clique. However, it contains more edges: $|E(G\text{'})|\; =\; |E(G)|\; -\; d(w)\; +\; d(u)\; >\; |E(G)|.$

Case 2: $d(w)geq\; d(u)$ and $d(w)geq\; d(v)$

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: $|E(G\text{'})|\; =\; |E(G)|\; -(d(u)\; +\; d(v)\; -\; 1)\; +\; 2d(w)\; geq\; |E(G)|\; +\; 1$.

This proves Claim 1.

The claim proves that one can partition the vertices of $G$ into equivalence classes based on their nonneighbors; 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 $|A|\; >\; |B|+1$, 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 $|B|$ edges, but gains $|A|-1$ edges. Thus, it gains at least $|A|-1-|B|geq\; 1$ edge. This proves Claim 2.

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.

- Turán, Paul (1941). "On an extremal problem in graph theory".
*Matematicko Fizicki Lapok*48 436–452. - .
- .

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday October 05, 2008 at 13:45:46 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday October 05, 2008 at 13:45:46 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.