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.
Related tools
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.