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

$ex (n, H) / (\binom{n}{2})$ is nonincreasing for $n \geq 2$

Statement

Let $H$ be a finite graph with at least one edge. For every $n \geq 3$ ,

$\frac{ex (n, H)}{(\binom{n}{2})} \leq \frac{ex (n - 1, H)}{(\binom{n - 1}{2})} .$

Hence the sequence indexed by $n \geq 2$ is nonincreasing.

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

For $n \geq 2$ , the normalized extremal number is $ex (n, H) / (\binom{n}{2})$ (Edge density and the asymptotic notations $O$ , $o$ , $Ω$ , and $Θ$ for extremal functions).

[F2]

The induced subgraph $G [W]$ retains exactly the edges of $G$ with both endpoints in $W$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F3]

For a finite incidence relation, the sum of its row-fibre sizes equals the sum of its column-fibre sizes (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets).

Proof

technique · double-count an edge and a deleted vertex

1.1

Let $G$ be an $n$ -vertex $H$ -free graph with $e (G) = ex (n, H)$ . Every induced graph $G - v$ is still $H$ -free, so $e (G - v) \leq ex (n - 1, H)$ .

givenF2

2.1

Count pairs $(e, v)$ with $e \in E (G)$ and $v$ not incident with $e$ . Each edge has $n - 2$ choices of $v$ , while for fixed $v$ there are $e (G - v)$ choices. Double counting gives $(n - 2) e (G) = \sum_{v} e (G - v) \leq n ex (n - 1, H)$ .

step 1.1givenF3

3.1

Substituting $e (G) = ex (n, H)$ and using $(\binom{n}{2}) = n (n - 1) / 2$ and $(\binom{n - 1}{2}) = (n - 1) (n - 2) / 2$ turns step 2.1 into the displayed inequality. There is no comparison before $n = 3$ , so the sequence begins at $n = 2$ .

step 2.1algebraF1∎

Depends on

Used by

Every finite graph with an edge has a Turán density π(H)=lim_n→∞ex(n,H)/C(n, 2) Theorem

Dependency tree · two levels

11 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)

ex⁡(n,H)/(n2)ex(n,H)/(2n​) is nonincreasing for n≥2n≥2