Turan Graph

The Turan graph, written T(n,r), is the graph on n vertices formed by dividing the vertices into r groups as equal in size as possible and joining every pair of vertices that lie in different groups, while leaving no edges between vertices in the same group. It is named after the Hungarian mathematician Pal Turan, who introduced it in a 1941 paper to prove what is now called Turan's theorem, a foundational result in extremal graph theory stating that the Turan graph has the maximum possible number of edges among all graphs on n vertices that contain no complete subgraph on r plus one vertices. Turan's own motivation, and the origin of the wider field of extremal graph theory that grew out of it, was to understand how large a graph can be made while still avoiding some prohibited substructure, a question that has since been generalized far beyond forbidding complete subgraphs to forbidding many other kinds of pattern. The Turan graph itself is a complete multipartite graph, meaning it consists of several independent groups of vertices with every possible edge present between different groups, and the case with only two groups, T(n,2), is the complete bipartite graph that comes closest to splitting its vertices evenly in half.