Turán's theorem

The set of Turán ( by Pál Turán ) is a statement from the mathematical branch of graph theory. He makes a statement about the maximum number of edges, which can have a graph with a given number of nodes to have to contain without a complete subgraph with nodes.

The case of triangles

It should be an undirected graph with nodes. A subgraph of three nodes is, in an obvious way a triangle if two of these three nodes are connected by an edge. The set of Turán clarified the statement that the graph if it is to contain no triangles can not have too many edges:

• Set of Turán (triangles): if a graph with nodes no triangles, so it has at most edges.

Here, the largest integer that is smaller or equal.

For small, the message is clear:

• This graph has neither edges nor triangles and it is.
• : Such graphs have no triangles and at most one edge; it is.
• : Such graphs have exactly then a triangle, if the number of edges 3; and it is.
• : It is and actually has any 4- graph with 5 edges at least one triangle.

For larger one performs the statement on graphs back with nodes, which then allows a proof by induction, where one has to distinguish even and odd. Here only the case for just to be briefly indicated:

Take away an edge connecting two nodes and, from. The subgraph obtained also contains no triangles and only nodes, ie according to the induction hypothesis, at most edges. The graph has also still the far edge and other edges emanating from or and end. Go about by, so have the outgoing edges in other nodes of end, for otherwise contained a triangle, that is, can at most assume edges ending in. The maximum possible number of edges of is therefore. It follows from the assertion for just. The case of odd can be treated very similarly.

The specified by the set of Turán boundary is sharp, as the example of bipartite graph shows, since this graph has nodes and edges.

The Turán graph

A triangle is the complete graph. This raises the question whether one can specify a limit to the number of edges of a graph which does not contain isomorphic to subgraph. To answer this question, the so-called Turán graph is defined as follows:

The Turán graph is the complete m- partite graph in the k-th class has elements. Note to the fact that

Area and therefore has nodes. The number of edges of is denoted by. It can be shown that

Being and represents the division with remainder.

The adjacent Turán graph has edges accordingly.

A simple calculation shows. This upper estimate of the number of edges of the Turán graph is often used.

The general case

• Set of Turán: if a graph with nodes not to isomorphic subgraphs (), so he has at most edges. Every graph without an induced subgraph isomorphic to with nodes and edges is isomorphic to Turán graph.

In the extremal graph theory is defined on a graph the number as the maximum number of edges, which can have a graph with nodes and without too isomorphic subgraphs. The set of Turán therefore has the following corollary:

However, the set of Turán says more, namely that any two graphs with nodes without too isomorphic subgraphs that realize this extreme value, are isomorphic to.

Is and straight, it is and therefore. Is odd, then and therefore. Therefore, and you get the already discussed above special case of triangles.

The analysis in rate limitation can be mitigated to, even if the resulting case is not particularly interesting. A graph without an induced subgraph isomorphic to a edgeless graph and in fact for all. The cases do not need to be excluded. For in the formula given above for, and therefore it is; Therefore, we obtain the trivial statement that a graph with nodes if and only contains a subgraph isomorphic to, when it is completely because has edges. If so, and therefore, is and is therefore likewise; that is, in the cases of the graph can have as many edges as possible, which is clear as it can not contain a subgraph isomorphic to anyway.