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: , and is the unique extremal graph
Statement
For and ,
Moreover, an -vertex -free graph has this many edges if and only if it is isomorphic to .
Facts & Assumptions
Given: The hypotheses and notation of the statement above.
is the maximum edge count of an -vertex graph with no ordinary copy of (Ordinary-subgraph extremal number , Turán graph , and balanced blowup ).
Zykov symmetrisation takes an extremal -free graph to a complete -partite graph with and the same edge count (Zykov symmetrisation turns an extremal clique-free graph into a complete multipartite graph without losing edges).
Among complete -partite graphs on vertices, has maximum edge count, with equality exactly for balanced part sizes (The exact edge count of and the unique balancing maximum among complete -partite graphs).
Proof
The graph is -free. Zykov symmetrisation sends an extremal graph to a complete -partite graph with and the same edge count; adding empty parts makes it complete -partite, so balancing bounds its edges by . Hence the displayed extremal number is exact.
For uniqueness, induct on . At , a -free graph is edgeless and equals . The case is also immediate. Assume , , and rigidity for , and let attain . Choose a vertex of maximum degree , put and . Then is -free and . The last expression is the edge count of a complete -partite graph whose one part has size and whose remaining parts are balanced on vertices, so balancing makes it at most .
Equality for forces equality throughout step 1.2. The first inequality forces to have no edge, the degree inequality forces every to have degree , and then forces every vertex of to be adjacent to every vertex of . Inductive rigidity gives , and balancing equality makes the resulting part sizes differ by at most . Thus .
Conversely is -free and has the extremal edge count by step 1.1. The induction therefore proves both directions of the equality characterization.
Steps 1.1-3.1 prove the exact formula and uniqueness for every , including and .
Depends on
- Ordinary-subgraph extremal number $\operatorname{ex}(n,H)$, Turán graph $T_{n,r}$, and balanced blowup $H[s]$
- The exact edge count of $T_{n,r}$ and the unique balancing maximum among complete $r$-partite graphs
- Zykov symmetrisation turns an extremal clique-free graph into a complete multipartite graph without losing edges
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
- Yufei Zhao, Graph Theory and Additive Combinatorics (standard reference, not scraped)
- Reinhard Diestel, Graph Theory, Chapter 7 (standard reference, not scraped)