CorollaryStatement: 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.

The asymptotic extremal density is determined exactly by chromatic number: $π (H) = 1 - 1 / (χ (H) - 1)$

Statement

For every finite graph $H$ with at least one edge,

$π (H) = 1 - \frac{1}{χ (H) - 1} .$

In particular, two such graphs have the same Turán density exactly when they have the same chromatic number, and every bipartite $H$ has density $0$ .

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

If $H$ is a finite graph with an edge and $r = χ (H)$ , then $ex (n, H) = (1 - 1 / (r - 1) + o (1)) (\binom{n}{2})$ (Erdős–Stone–Simonovits: $ex (n, H) = (1 - 1 / (χ (H) - 1) + o (1)) (\binom{n}{2})$ for every graph with an edge).

[F2]

For every finite graph $H$ with an edge, the normalized extremal numbers converge to $π (H)$ , their infimum over $n \geq 2$ (Every finite graph with an edge has a Turán density $π (H) = \lim_{n \to \infty} ex (n, H) / (\binom{n}{2})$ ).

[F3]

Every finite bipartite graph with an edge has Turán density zero (Every bipartite graph with at least one edge has Turán density zero).

Proof

technique · identify the existing limit

1.1

Erdős–Stone–Simonovits states that the normalized extremal number tends to $1 - 1 / (χ (H) - 1)$ , while the definition of $π (H)$ is that same existing limit. This proves the formula.

givenF1F2

2.1

For integers $r \geq 2$ , the function $1 - 1 / (r - 1)$ is strictly increasing, so equal values are equivalent to equal chromatic numbers. At $r = 2$ it is $0$ , agreeing with the KST-derived bipartite corollary.

step 1.1givenF3

3.1

Steps 1.1-2.1 prove the exact density statement and both consequences.

step 1.1step 2.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

Yufei Zhao, Graph Theory and Additive Combinatorics (standard reference, not scraped)
Reinhard Diestel, Graph Theory, Chapter 7 (standard reference, not scraped)

The asymptotic extremal density is determined exactly by chromatic number: π(H)=1−1/(χ(H)−1)π(H)=1−1/(χ(H)−1)