Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-13
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Turán's theorem with equality: ex⁡(n,Kr+1)=e(Tn,r), and Tn,r is the unique extremal graph

Statement

For n∈N and r≥1,

ex⁡(n,Kr+1)=e(Tn,r).

Moreover, an n-vertex Kr+1-free graph has this many edges if and only if it is isomorphic to Tn,r.

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

ex⁡(n,H) is the maximum edge count of an n-vertex graph with no ordinary copy of H (Ordinary-subgraph extremal number ex⁡(n,H), Turán graph Tn,r, and balanced blowup H[s]).

[F2]

Zykov symmetrisation takes an extremal Kr+1-free graph to a complete k-partite graph with k≤r and the same edge count (Zykov symmetrisation turns an extremal clique-free graph into a complete multipartite graph without losing edges).

[F3]

Among complete r-partite graphs on n vertices, Tn,r has maximum edge count, with equality exactly for balanced part sizes (The exact edge count of Tn,r and the unique balancing maximum among complete r-partite graphs).

Proof

technique · symmetrise for the bound, then use degree induction for rigidity
1.1

The graph Tn,r is Kr+1-free. Zykov symmetrisation sends an extremal graph to a complete k-partite graph with k≤r and the same edge count; adding empty parts makes it complete r-partite, so balancing bounds its edges by e(Tn,r). Hence the displayed extremal number is exact.

givenF1F2F3
1.2

For uniqueness, induct on r. At r=1, a K2-free graph is edgeless and equals Tn,1. The case n=0 is also immediate. Assume r≥2, n≥1, and rigidity for r−1, and let G attain e(Tn,r). Choose a vertex v of maximum degree d, put A=N(v) and B=V(G)∖A. Then G[A] is Kr-free and e(G)≤e(G[A])+∑b∈Bd(b)≤e(Td,r−1)+(n−d)d. The last expression is the edge count of a complete r-partite graph whose one part has size n−d and whose remaining parts are balanced on d vertices, so balancing makes it at most e(Tn,r).

givenF3
2.1

Equality for G forces equality throughout step 1.2. The first inequality forces G[B] to have no edge, the degree inequality forces every b∈B to have degree d, and ∣A∣=d then forces every vertex of B to be adjacent to every vertex of A. Inductive rigidity gives G[A]≅Td,r−1, and balancing equality makes the resulting r part sizes differ by at most 1. Thus G≅Tn,r.

step 1.2givenF3
3.1

Conversely Tn,r is Kr+1-free and has the extremal edge count by step 1.1. The induction therefore proves both directions of the equality characterization.

step 1.1step 2.1
4.1

Steps 1.1-3.1 prove the exact formula and uniqueness for every n, including n<r and n=0.

step 1.1step 1.2step 2.1step 3.1∎

Depends on

Used by

Dependency tree · two levels

12 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources