CorollaryStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-08-31

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.

Few induced copies force a linearly large induced subgraph with bounded maximum degree

Statement

Let $H$ be a finite graph and let $ϵ \in (0, \frac{1}{2})$ . Then there exists $δ > 0$ such that every nonempty finite graph $G$ with

${ind}_{H} (G) < (δ ∣ V (G) ∣)^{∣ V (H) ∣}$

has a set $X \subseteq V (G)$ with $∣ X ∣ \geq δ ∣ V (G) ∣$ for which one of $G [X]$ or $\overline{G} [X]$ has maximum degree at most $ϵ ∣ X ∣$ .

Facts & Assumptions

Given: A finite graph $H$ , a real $ϵ \in (0, \frac{1}{2})$ , and a nonempty finite graph $G$ with ${ind}_{H} (G) < (δ ∣ V (G) ∣)^{∣ V (H) ∣}$ .

[L1]

Nikiforov's theorem yields $δ_{0} > 0$ such that the induced-copy bound forces an $ϵ / 4$ -restricted set of size at least $δ_{0} ∣ V (G) ∣$ (Nikiforov: for every $H$ and every $ϵ \in (0, \frac{1}{2})$ there is $δ > 0$ such that every graph $G$ with ${ind}_{H} (G) < (δ ∣ V (G) ∣)^{∣ V (H) ∣}$ has an $ϵ$ -restricted vertex set of size at least $δ ∣ V (G) ∣$ ).

[L2]

In a sparse graph, any prescribed size up to half the order can be chosen so that the induced subgraph has proportionally bounded maximum degree (A sparse graph has a prescribed-size induced subgraph of bounded maximum degree).

Proof

technique · direct

1.1L1choosegiven

Apply [L1] with parameter $ϵ / 4$ and let $δ : = δ_{0} / 2$ . Then there is a set $Z \subseteq V (G)$ with $∣ Z ∣ \geq 2 δ ∣ V (G) ∣$ such that either $G [Z]$ or $\overline{G} [Z]$ is $(ϵ / 4)$ -sparse.

2.1step 1.1L2algebra

Let $m : = ⌈ δ ∣ V (G) ∣ ⌉$ . Since $∣ Z ∣ \geq 2 δ ∣ V (G) ∣$ , we have $m \leq (∣ Z ∣ + 1) / 2$ . Applying [L2] inside the sparse side on $Z$ gives $X \subseteq Z$ with $∣ X ∣ = m \geq δ ∣ V (G) ∣$ such that the same side has maximum degree at most $4 (ϵ / 4) (m - 1) \leq ϵ ∣ X ∣$ .

3.1step 2.1∎

Thus one of $G [X]$ or $\overline{G} [X]$ has maximum degree at most $ϵ ∣ X ∣$ , as required.

Depends on

Used by

A long blockade without a large pure pair contains a rainbow forest or its complement Theorem

Dependency tree · two levels

20 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

Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdős-Hajnal for graphs with no 5-hole, Theorem 6.5 (standard reference, not scraped)
Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Theorem 1.2 (standard reference, not scraped)