Skip to content
Omnikalc

Turán’s theorem calculator

Enter the number of vertices and the clique size to avoid to get the maximum number of edges of the Turán graph, the sizes of its parts, the edge density and the number of edges that force a clique.

Updated on
Your inputs

Value out of range

Value out of range

Results

Maximum edges without the clique

133

Edges that force a clique

134

Edges of the complete graph
190
Share of all possible edges
70.00 %
Number of parts (r)
3
Parts of the larger size
2
Size of the smaller parts
6

The Turán’s theorem calculator gives the maximum number of edges a graph on n vertices can have without a clique of a given size, the structure of the extremal Turán graph, its density, and the number of edges that forces the clique.

How the calculation works

  • Enter the number of vertices n.
  • Enter the clique size to avoid, r + 1, with at least 3.
  • Read the maximum number of edges, the parts and the density.

Example

A graph with 20 vertices and no clique of 4 can have at most 133 edges, which is 70.00 % of the 190 edges of the complete graph. The Turán graph has 3 parts: 2 of them are one vertex larger than the smaller parts of 6. With 134 edges, a clique cannot be avoided.

Why it matters

The calculator helps students and teachers of discrete mathematics, computer scientists and network analysts who study extremal graph problems, check exercises on Mantel’s and Turán’s theorems, or estimate how dense a network can be before it must contain a tight group.

Good to know

The clique size to avoid is r + 1, so a triangle-free graph has r = 2 and a value of 3 here. The formula needs the vertices split in parts as equal as possible. The maximum is reached only by the Turán graph, so any other graph with this many edges and no clique is impossible. The result is the largest number of edges and not the typical one. Real graphs, even dense ones, are usually far below this bound. When the number of vertices is not a multiple of r, the parts differ in size by one vertex, and the calculator handles that case with the remainder.

The Catalan number calculator counts other combinatorial structures, the combinations calculator counts subsets, the binomial calculator gives coefficients and the polygonal numbers calculator lists related figurate counts.

Frequently asked questions

What does Turán’s theorem say?

Turán’s theorem gives the maximum number of edges in a graph with n vertices that contains no complete subgraph on r + 1 vertices. The extremal graph is the complete r-partite graph with parts as equal in size as possible, called the Turán graph. For r = 2, no triangle, the answer is Mantel’s theorem: at most n² / 4 edges.

What is the formula?

If n = q × r + s with 0 ≤ s < r, the Turán graph has s parts of size q + 1 and r − s parts of size q. Its number of edges is (1 − 1/r) × n² / 2 − s × (r − s) / (2r). If r divides n, this reduces to (1 − 1/r) × n² / 2.

What does it say about forcing a clique?

Any graph with more edges than the Turán number must contain a clique on r + 1 vertices. For 20 vertices, a graph with 133 edges or more must contain a clique of 4. This is the starting point of extremal graph theory, which asks how many edges force a given structure.

Where is it used?

It appears in extremal combinatorics, network design, coding theory and the analysis of dense graphs. A social network with more connections than the Turán bound must contain a tight group of friends of a given size, which gives a way to prove the existence of cliques without finding them.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.