Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck 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 nN and r1,

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 kr 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 kr 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 r2, n1, and rigidity for r1, 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])+bBd(b)e(Td,r1)+(nd)d. The last expression is the edge count of a complete r-partite graph whose one part has size nd 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 bB 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,r1, and balancing equality makes the resulting r part sizes differ by at most 1. Thus GTn,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 · next 3 levels

Direct dependencies and their dependencies through the next three levels: 26 results over 13 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources