Turán Graph¶

The balanced complete r-partite graph T(n,r), formed by making nearly equal vertex blocks independent and joining every cross-block pair, uniquely maximizing edges among n-vertex graphs with no K_(r+1).

Version: v2 · 2026-08-30 · History
Domain-specific #: 3012
Origin domain: mathematics
Subdomain: extremal graph theory
Aliases: Turan graph

Core Idea¶

For integers \(1\le r\le n\), the Turán graph (T(n,r)) is the complete ®-partite simple graph whose part sizes differ by at most one. Write

\[ n=qr+s,\qquad 0\le s<r. \]

Then (T(n,r)) has (s) independent parts of size (q+1) and (r-s) independent parts of size (q). Two vertices are adjacent exactly when they lie in different parts. Thus the construction combines three commitments that must remain together: partition the vertex set into exactly ® nonempty blocks, balance the blocks as evenly as integer arithmetic permits, and complete every cross-block adjacency while leaving every within-block pair nonadjacent.

The object is central because the construction and the extremal certificate coincide. A clique can contain at most one vertex from each independent part, so (T(n,r)) contains no (K_{r+1}). Turán's theorem says more: among every simple graph on (n) vertices with no (K_{r+1}), (T(n,r)) has the largest possible number of edges, and it is the unique maximizer up to graph isomorphism.^[1]^[2]^[3] Its edge count is

\[ t_r(n)=\binom{n}{2}-s\binom{q+1}{2}-(r-s)\binom{q}{2} =\left\lfloor \frac{r-1}{2r}n^2\right\rfloor. \]

The Turán graph is therefore not merely a named family of graphs. It is a reusable extremal witness: a balanced exclusion construction that converts a forbidden-clique condition into a sharp density bound and an equality classification. It provides the canonical lower-bound construction for the clique Turán number (operatorname{ex}(n,K_{r+1})), a model equality case for proof techniques such as symmetrization, and a reference configuration for stability and forbidden-subgraph reasoning.

Structural Signature¶

(n)-vertex ground set -> partition into ® independent blocks -> block sizes differ by at most one -> add every edge between different blocks and no edge inside a block -> obtain a (K_{r+1})-free graph with the maximum possible edge count.

The mandatory roles are:

order (n): the total number of vertices;
part count ®: both the multipartite count and the largest clique size when every part is nonempty;
quotient-remainder balance: (n=qr+s), yielding (s) parts of size (q+1) and (r-s) of size (q);
within-part exclusion: every part is an independent set;
cross-part completion: every pair in different parts is an edge;
forbidden configuration: (K_{r+1}) cannot occur because a clique uses at most one vertex per part;
objective: maximize edge count subject to the forbidden clique;
equality certificate: any (n)-vertex (K_{r+1})-free graph attaining the bound is isomorphic to (T(n,r)).

Recognition test. A graph is (T(n,r)) exactly when it is complete ®-partite and its nonempty part sizes differ by at most one. Merely having an equitable ®-coloring is insufficient: the graph may omit cross-part edges. Merely being complete multipartite is insufficient: the parts may be unbalanced. Merely attaining high (K_{r+1})-free density is insufficient: only exact attainment forces the equality graph.

What It Is Not¶

The Turán graph is not Turán's theorem. The graph is the extremal construction and equality object; the theorem is the universal statement that no (K_{r+1})-free (n)-vertex graph has more edges and that equality identifies this construction.

It is not the Turán number (operatorname{ex}(n,H)), which is a numerical maximum over all (H)-free (n)-vertex graphs. For (H=K_{r+1}), the number equals (e(T(n,r))), but an integer is not a graph.

It is not an arbitrary complete multipartite graph. (K_{1,1,8}) is complete tripartite but is not (T(10,3)), whose parts have sizes (4,3,3). The balancing condition is what maximizes cross edges for fixed (n) and ®.

It is not a complete graph except in the boundary case (r=n), and not a generic complete bipartite graph except when (r=2) and the two parts are balanced. It is not a cut: a cut names edges crossing one bipartition, whereas a Turán graph uses an ®-block partition, removes all within-block edges, and completes all pairs of different blocks.

It is not a generic graph representation or Graph Data Type. Those describe how vertices and edges are stored or accessed; (T(n,r)) is a particular mathematical isomorphism class with extremal meaning.

Scope of Application¶

The home domain is extremal graph theory, especially forbidden-subgraph problems. The basic problem asks for the largest number of edges in an (n)-vertex graph avoiding a fixed graph (H). The corresponding maximum is (operatorname{ex}(n,H)). For cliques, Turán's 1941 result gives the exact answer and unique equality structure: (operatorname{ex}(n,K_{r+1})=e(T(n,r))).^[1]^[2]

The construction also sits naturally in multipartite graph theory. Its parts are independent color classes, its chromatic number is ® for \(1\le r\le n\), and its complement is the disjoint union of ® cliques whose orders are as equal as possible. This complement view turns the same balancing argument into minimizing the number of missing edges.

In graph coloring, a graph (G) is a spanning subgraph of some labeled copy of (T(n,r)) exactly when (G) admits a proper equitable ®-coloring: its color classes can be made the balanced independent parts, and the Turán graph supplies every permissible cross-color edge. This is a related characterization, not an identity between Turán Graph and Graph Coloring.

In broader extremal theory, (T(n,r)) is the canonical construction against forbidden graphs of chromatic number (r+1). The Erdős–Stone theorem makes balanced complete multipartite graphs the asymptotic density template for a much larger class of forbidden-subgraph problems. The present node remains the exact graph family and does not absorb the theorem, Turán density, hypergraph Turán problems, Ramsey–Turán theory, or every “Turán-type” extremal statement.

Clarity¶

The concept separates three levels often blurred in informal usage: construction, objective value, and theorem. (T(n,r)) is the constructed graph. (t_r(n)=e(T(n,r))) is its edge count and the relevant Turán number. Turán's theorem proves that this value is optimal and characterizes equality. Keeping the three distinct prevents statements such as “the Turán graph is the bound” or “a graph with nearly the bound is the Turán graph.”

The quotient-remainder notation also eliminates ambiguity in “as equal as possible.” If (n=qr+s), exactly (s) parts have (q+1) vertices and the rest have (q). There is no choice of other sizes once (n) and ® are fixed, up to permuting blocks. The resulting graph is likewise unique up to relabeling vertices.

A useful diagnostic checks both directions of adjacency. In (T(n,r)), same-part means nonadjacent, and different-part means adjacent. A proper coloring supplies only the first implication. The missing converse is why a sparse ®-colorable graph is not a Turán graph.

Manages Complexity¶

The Turán graph compresses an enormous feasible family—all (K_{r+1})-free graphs on (n) vertices—into a single canonical equality object. Instead of comparing arbitrary edge sets, a reasoner can calculate one balanced multipartite construction, read off the optimum, and use deviations from its structure to understand why a candidate graph loses edges or creates the forbidden clique.

Its balance rule reduces integer optimization to quotient and remainder. For a complete ®-partite graph with part sizes \(n_1,\ldots,n_r\),

\[ e=\sum_{i<j}n_i n_j=\frac12\left(n^2-\sum_i n_i^2\right). \]

At fixed \(\sum_i n_i=n\), maximizing edges is equivalent to minimizing \(\sum_i n_i^2\). If two part sizes differ by at least two, moving one vertex from the larger to the smaller decreases the square sum and increases the edge count. Repeating this exchange forces the nearly equal sizes. A many-variable discrete problem collapses to one local balancing move.

The equality classification then becomes a diagnostic. If a (K_{r+1})-free graph has exactly (t_r(n)) edges, no alternative irregular structure needs to be searched: it must be isomorphic to (T(n,r)). If it has slightly fewer edges, the Turán graph becomes the natural comparison object for asking whether the deficit comes from missing cross edges, unbalanced parts, or a more basic failure to be multipartite.

Abstract Reasoning¶

Clique exclusion. Since every edge lies between parts, a clique contains at most one vertex from each of the ® parts. Hence (omega(T(n,r))=r) and (K_{r+1}) is absent. Conversely, selecting one vertex from each nonempty part produces a (K_r).

Balancing inference. Suppose a complete ®-partite graph has two parts of sizes (a) and (b) with \(a\ge b+2\). Moving one vertex from the larger part to the smaller changes the within-part square sum by

\[ (a-1)^2+(b+1)^2-a^2-b^2=-2(a-b-1)<0, \]

so the cross-edge count increases by (a-b-1). Therefore no unbalanced complete ®-partite graph can be edge-maximal.

Degree inference. A vertex is adjacent to every vertex outside its own part. Vertices in a (q+1) part have degree (n-q-1); vertices in a (q) part have degree (n-q). For \(1\le r\le n\), the graph is regular exactly when (s=0), that is, (rmid n).

Complement inference. (overline{T(n,r)}) is \(sK_{q+1}\cup(r-s)K_q\). This makes independent sets, coloring, and missing-edge counts transparent and supplies a direct recognition algorithm: connected components of the complement must be cliques with balanced orders.

Threshold inference. Any (n)-vertex graph with more than (t_r(n)) edges contains (K_{r+1}). Exact equality plus (K_{r+1})-freeness forces the Turán graph. These statements turn a density observation into either a forbidden-structure guarantee or an equality classification.^[2]^[3]

Knowledge Transfer¶

Within graph theory the construction transfers as an exact mechanism. The same (n,r) partition and completion rule can serve as a forbidden-clique extremizer, an equitable-coloring completion, a complement-of-balanced-cliques representation, a benchmark graph for spectral or geometric questions, and a base construction in stability arguments. In every case the graph is literally (T(n,r)), not an analogy.

The proof move also transfers within extremal combinatorics: symmetrize a candidate until nonadjacency behaves like an equivalence relation, obtain a complete multipartite graph, then balance its parts by a convexity or exchange argument. Later results generalize or perturb this route, but the exact node remains the equality object for clique exclusion.

Beyond mathematics, “divide groups evenly and connect across groups” can inspire network design, but that is not automatically a Turán graph. A real network must have every cross-group link, no within-group link, and the exact balanced-block and forbidden-clique interpretation. Without those commitments, only Partition, balancing, or Optimization transfers. Thus the named construction is domain-specific even though its parent patterns travel more broadly.

Examples¶

(T(7,3)). Here \(7=2\cdot3+1\), so (q=2) and (s=1). The part sizes are (3,2,2), and the graph is (K_{3,2,2}). Its edge count is

\[ 3\cdot2+3\cdot2+2\cdot2=16 =\left\lfloor\frac{2}{6}\cdot49\right\rfloor. \]

No (K_4) can occur because four vertices force two into the same independent part. Turán's theorem says every seven-vertex (K_4)-free graph has at most 16 edges, with equality only for (K_{3,2,2}). Vertices in the size-three part have degree four, and those in size-two parts have degree five.

Mantel case (T(n,2)). The graph is \(K_{\lfloor n/2\rfloor,\lceil n/2\rceil}\), the balanced complete bipartite graph. It has \(\lfloor n^2/4\rfloor\) edges and no triangle. This is the equality construction in Mantel's theorem, the (r=2) case of Turán's theorem.

Octahedral case (T(6,3)). The three parts all have size two, so (T(6,3)=K_{2,2,2}). It is the graph of the octahedron, has 12 edges, is 4-regular, contains triangles, and contains no (K_4). The geometric realization is a special instance; octahedral graph is not an alias for the whole parameterized family.

False example (K_{1,3,3}). This graph is complete tripartite and (K_4)-free, but its parts are not balanced. Moving one vertex from the size-three part to the singleton produces sizes (2,2,3) and increases the edge count. It is therefore not (T(7,3)).

Structural Tensions¶

Density versus forbidden structure. Adding edges improves the objective but risks creating (K_{r+1}). Diagnostic: compare the edge count with (t_r(n)); crossing the threshold forces the clique.

Completion versus exclusion. All cross-part edges are needed for maximality, while all within-part edges must be absent to preserve the immediate ®-partite certificate. Diagnostic: a missing cross edge leaves attainable density unused; a within-part edge destroys the displayed coloring and may help form a forbidden clique.

Balance versus integrality. Convexity favors equal parts, but integer vertices cannot always divide equally. Diagnostic: use (n=qr+s); only sizes (q) and (q+1) are optimal, with exactly (s) larger parts.

Exact extremality versus stability. Exact equality gives a unique graph, whereas near-equality need not give literal isomorphism. Diagnostic: distinguish a zero edge deficit, which triggers uniqueness, from a small positive deficit, which requires a stability theorem and an explicit distance notion.

Object versus theorem. The construction witnesses the bound; the theorem universally certifies it. Diagnostic: ask whether the statement names a graph, a number, or a claim over all forbidden-subgraph graphs.

Structural–Framed Character¶

Turán Graph is mixed-structural. Its definition is formal, exact, evaluatively neutral, and independent of any material substrate. The partition, adjacency rule, balance exchange, and forbidden-clique certificate are mathematical relations. The same object is recognized under labeling changes and across uses within combinatorics.

It remains domain-specific because the identity is graph-theoretic furniture: vertices, edges, cliques, complete multipartite graphs, chromatic number, isomorphism, and extremal edge count. Outside graph theory, an evenly divided cross-connected organization only resembles the construction unless every relation is mapped literally and the forbidden-clique objective is preserved. The transferable general mechanisms—Partition and Optimization under Constraint—already have broader catalog homes.

Structural Core vs. Domain Accent¶

The structural core is balanced partition under a pairwise exclusion/completion rule. Fixed total size and block count create an exchange argument: moving mass from a larger block to a smaller one improves a symmetric cross-block objective until block sizes differ by at most one. The object then acts as a sharp boundary witness between feasible density and forced forbidden structure.

The domain accent supplies the exact meaning: blocks are independent vertex sets; the objective counts graph edges; all cross-block vertex pairs are adjacent; the forbidden configuration is (K_{r+1}); and uniqueness is up to graph isomorphism. Remove that accent and one has a general balancing or partition optimization pattern, not the Turán graph. Preserve it and the exact construction, formulas, and theorem transfer throughout extremal graph theory.

Turán Graph strictly presupposes prime:partition: its vertex set is divided into disjoint, exhaustive partite blocks, and the balance and adjacency rules are defined entirely relative to those blocks. The proposed DAG relation is composition rather than subsumption because a graph is not itself a kind of partition; the partition is a constitutive component of the construction.

prime:graph_coloring is strongly related. The partite blocks are color classes, and (T(n,r)) is the complete graph permitted by that proper equitable coloring. Coloring is not proposed as a second parent because the partition edge already captures the constitutive grouping, while coloring adds a conflict-label interpretation rather than another necessary object layer.

prime:optimization and prime:constraint explain the maximum-edge-under-(K_{r+1})-exclusion reading. They remain related explanatory primes; adding both as parents would be redundant and would turn every extremal object into a multi-parent list of generic reasoning ingredients.

Relationships to Other Abstractions¶

Current abstraction Turán Graph Domain-specific

Parents (1) — more general patterns this builds on

Turán Graph presupposes Partition Prime

Turán Graph strictly presupposes prime:partition: its vertex set is divided into disjoint, exhaustive partite blocks, and the balance and adjacency rules are defined entirely relative to those blocks.

Hierarchy path (1) — routes to 1 parentless root

Turán Graph → Partition → Set and Membership

Neighborhood in Abstraction Space¶

Turán Graph sits in a sparse region of the domain-specific corpus (81^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Coloring Games & Drawings (7 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Turán's theorem: the extremal bound and equality theorem.
Turán number (operatorname{ex}(n,H)): a maximum edge count, not a graph.
Turán density: an asymptotic normalized extremal quantity, especially in hypergraphs.
Complete ®-partite graph: may have unbalanced part sizes.
Equitably ®-colorable graph: may omit any number of cross-color edges.
Complete bipartite graph: equals a Turán graph only when its two parts differ by at most one.
Balanced incomplete block design: a design-theory incidence structure, not this graph construction.
Turán-type problem: a broad family of extremal questions, not an alias for the equality graph.
Graph Data Type: a software representation abstraction rather than a mathematical graph family.

References¶

[1] Turán, P. (1941). “Egy gráfelméleti szélsőértékfeladatról” [“On an Extremal Problem in Graph Theory”]. Matematikai és Fizikai Lapok, 48, 436–452. Bibliographic record and English-translation reference are preserved by the Erdős Problems archive. registry ↩a ↩b

[2] Fox, J. Extremal Graph Theory I: Classical Results. Institute for Advanced Study lecture notes giving the complete-multipartite reduction, balancing argument, and Turán theorem. registry ↩a ↩b ↩c

[3] Babai, L. (2021). Honors Graph Theory: definitions and theorems. University of Chicago notes defining (T(n,r)) as the balanced complete ®-partite graph and stating the exact edge maximum and uniqueness theorem. registry ↩a ↩b

[4] Aigner, M., and Ziegler, G. M. (2004). “Turán's Graph Theorem.” In Proofs from THE BOOK, Springer, pp. 235–240. Authoritative collection of proofs and references for the theorem. registry