LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-26

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.

A subset occupying at least a $λ$ fraction of a $c$ -sparse set is $(c / λ)$ -sparse

Statement

Let $G$ be a finite simple graph, let $c \geq 0$ , let $λ > 0$ , and let $X^{'} \subseteq X \subseteq V (G)$ be nonempty. If $X$ is $c$ -sparse and $∣ X^{'} ∣ \geq λ ∣ X ∣$ , then $X^{'}$ is $(c / λ)$ -sparse.

Facts & Assumptions

Given: A finite simple graph $G$ , reals $c \geq 0$ and $λ > 0$ , and nonempty sets $X^{'} \subseteq X \subseteq V (G)$ such that $X$ is $c$ -sparse and $∣ X^{'} ∣ \geq λ ∣ X ∣$ .

[L1]

In the induced subgraph on a set, sparsity is exactly a maximum-degree bound (A set is $c$ -sparse exactly when the maximum degree of the graph it induces is at most $c$ times its size, $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

Proof

technique · direct

1.1L1

For every $x \in X^{'}$ , the degree of $x$ in $G [X^{'}]$ is at most its degree in $G [X]$ .

2.1step 1.1L1algebra

Since $X$ is $c$ -sparse, [L1] gives $\deg_{G [X]} (x) \leq c ∣ X ∣$ ; and because $∣ X^{'} ∣ \geq λ ∣ X ∣$ , one has $∣ X ∣ \leq ∣ X^{'} ∣ / λ$ . Hence $\deg_{G [X^{'}]} (x) \leq (c / λ) ∣ X^{'} ∣$ for every $x \in X^{'}$ .

3.1step 2.1L1∎

Applying [L1] again shows that $X^{'}$ is $(c / λ)$ -sparse.

Depends on

Used by

A subset of a c-sparse set that is not c-sparse Counterexample

Dependency tree · two levels

7 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

Y. Huang, Q. Ju, and X. Zhou, Erdős-Hajnal beyond the five-vertex path, sec. 2 (standard reference, not scraped)

A subset occupying at least a λλ fraction of a cc-sparse set is (c/λ)(c/λ)-sparse