Turán's theorem

Turán's theorem is a fundamental result in graph theory that tells us the maximum number of edges a graph can have without containing a complete subgraph of a certain size, like a clique. Specifically, it states that to avoid creating a clique of size \(r + 1\), the densest possible graph is a balanced \(r\)-partite graph, where vertices are divided into \(r\) groups with edges connecting every pair of vertices from different groups. This optimal structure maximizes edges without forming larger completely interconnected groups, providing a precise limit on how dense such a graph can be.