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.

✓ 4 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Iterative Restriction and Comb-Extraction Lemmas — Examples

1 · Prerequisites

2 · Summary

These examples keep the Section 2 lemmas concrete. They show leaf-reducibility for $P_{5}$ , unpack the nearly covered sparse-pair inequalities numerically, run a sample iteration for the multiplicative sparsity-drop lemma, and spell out the finite adjacency pattern of the comb outcome together with its external complete vertex.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

The five-vertex path is leaf-reducible

Example

The singleton family ${P_{5}}$ is leaf-reducible.

Facts & Assumptions

Given: The path graph $P_{5}$ .

[L1]

A family is leaf-reducible if deleting one leaf from one member leaves a modified family with the Erdős-Hajnal property (Leaf-reducible finite graph families).

[L2]

Every $P_{4}$ -free graph has a clique or stable set of size at least the square root of its order (Every $P_{4}$ -free graph has a clique or stable set of size at least the square root of its order).

[L3]

A graph has the Erdős-Hajnal property when its forbidden induced-subgraph class has some positive exponent (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).

Verification

technique · direct

1.1

An endpoint of $P_{5}$ is a leaf, and deleting it leaves the four-vertex path $P_{4}$ .

givenL1

2.1

By [L2], the class of $P_{4}$ -free graphs has the positive exponent $1 / 2$ , so [L3] says that $P_{4}$ has the Erdős-Hajnal property. Therefore the modified singleton family ${P_{4}}$ satisfies the condition in [L1].

step 1.1L2L3

3.1

Hence the singleton family ${P_{5}}$ is leaf-reducible.

step 2.1L1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

A nearly covered sparse pair at small parameters

Example

For $y = 2^{- 8}$ and $x = 2^{- 9}$ , suppose a graph $G$ of order $2^{40}$ satisfies the sparse-graph, non- $2 y^{4}$ -sparsity, and no-large-sparse-pair hypotheses of the nearly covered sparse-pair lemma. Its conclusion asks for a set $B$ of size at least $2^{8}$ and a set $A$ of size at least $(1 - 3 \cdot 2^{- 8}) 2^{40}$ such that $A$ is $2^{- 16}$ -sparse to $B$ and every vertex of $B$ has at least $2^{- 18} ∣ A ∣$ neighbours in $A$ .

Facts & Assumptions

Given: The parameters $y = 2^{- 8}$ , $x = 2^{- 9}$ , a graph $G$ with $∣ V (G) ∣ = 2^{40}$ , and all hypotheses of the cited lemma.

[L1]

Under those hypotheses, the lemma produces disjoint sets $A, B$ with $∣ B ∣ \geq y^{4} ∣ V (G) ∣$ , $∣ A ∣ \geq (1 - 3 y) ∣ V (G) ∣$ , $A$ $y^{2}$ -sparse to $B$ , and every vertex of $B$ having at least $x^{2} ∣ A ∣$ neighbours in $A$ (A sparse graph without a large sparse pair has a large nearly covered sparse pair).

Verification

technique · arithmetic unpacking

1.1

Substituting $y = 2^{- 8}$ and $∣ V (G) ∣ = 2^{40}$ into [L1] gives $y^{4} ∣ V (G) ∣ = 2^{- 32} \cdot 2^{40} = 2^{8}$ and $(1 - 3 y) ∣ V (G) ∣ = (1 - 3 \cdot 2^{- 8}) 2^{40}$ .

L1algebra

2.1

The same substitution gives $y^{2} = 2^{- 16}$ and $x^{2} = 2^{- 18}$ , so the sparsity and neighbourhood conclusions in [L1] become exactly the numerical conditions stated above.

step 1.1L1algebra∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

A numeric run of the multiplicative iteration in Lemma 2.9

Example

Take $c = 2^{- 4}, x = 2^{- 8}, b_{1} = 2, b_{2} = 3, b_{3} = 3.$ Then $b_{1} b_{2} = 6 = b_{2} + b_{3}$ , so the iteration lemma predicts an $x$ -sparse induced subgraph of size at least $x^{6} ∣ V (G) ∣ = 2^{- 48} ∣ V (G) ∣$ .

Facts & Assumptions

Given: The numerical parameters displayed above.

[L1]

Under the lemma's hypotheses, the output size is at least $x^{b_{1} b_{2}} ∣ V (G) ∣$ (Iterated sparse restriction reaches the target sparsity threshold).

Verification

technique · arithmetic unpacking

1.1

The equality $b_{1} b_{2} = 2 \cdot 3 = 6$ and $b_{2} + b_{3} = 3 + 3 = 6$ shows that the required inequality $b_{1} b_{2} \geq b_{2} + b_{3}$ is tight in this example.

givenalgebra

2.1

Applying [L1] gives a final induced subgraph of size at least $x^{b_{1} b_{2}} ∣ V (G) ∣ = (2^{- 8})^{6} ∣ V (G) ∣ = 2^{- 48} ∣ V (G) ∣$ . This makes the multiplicative exponent bookkeeping explicit in one concrete case.

step 1.1L1algebra∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-09-01Open item page →

A four-tooth comb with an external complete vertex

Example

Let $a_{1}, a_{2}, a_{3}, a_{4}, v$ be five vertices and let $B_{i} = {b_{i}}$ for $i = 1, 2, 3, 4$ . If the only edges among these nine vertices are $a_{i} b_{i}$ for $1 \leq i \leq 4$ and $v b_{i}$ for $1 \leq i \leq 4$ , then $((a_{i}, B_{i}) : i \in [4])$ is a four-tooth comb and the outside vertex $v$ is complete to the tooth blocks and anticomplete to the teeth.

Facts & Assumptions

Given: The nine labelled vertices above with exactly the displayed edges.

[L1]

A comb is given by distinct teeth $a_{i}$ , disjoint blocks $B_{i}$ , each tooth complete to its own block and anticomplete to the other blocks (Combs in a graph).

Verification

technique · direct finite check

1.1

For each $i \in [4]$ , the tooth $a_{i}$ is adjacent to the unique vertex of its own block $B_{i} = {b_{i}}$ and to no vertex of the other three blocks. Therefore $((a_{i}, B_{i}) : i \in [4])$ satisfies [L1].

L1given

2.1

By construction the vertex $v$ is adjacent to every $b_{i}$ and to none of the teeth $a_{i}$ . So $v$ has exactly the extra adjacency pattern singled out in the comb outcome of the lemma.

step 1.1given∎

Iterative Restriction and Comb-Extraction Lemmas — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The five-vertex path is leaf-reducible

Example

Facts & Assumptions

Verification

A nearly covered sparse pair at small parameters

Example

Facts & Assumptions

Verification

A numeric run of the multiplicative iteration in Lemma 2.9

Example

Facts & Assumptions

Verification

A four-tooth comb with an external complete vertex

Example

Facts & Assumptions

Verification

Sources