LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-09-01

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 sparse graph either sparsifies further or yields a comb or a large sparse pair

Statement

Let $0 < x \leq y \leq 2^{- 8}$ , and let $G$ be a $y^{3}$ -sparse graph with $∣ V (G) ∣ \geq y^{- 4}$ . Then at least one of the following holds:

there are disjoint sets $X, Y \subseteq V (G)$ such that $∣ X ∣ \geq y^{4} ∣ V (G) ∣, ∣ Y ∣ \geq (1 - 4 y) ∣ V (G) ∣,$ and $Y$ is $x$ -sparse to $X$ ;
$G$ is $2 y^{4}$ -sparse; or
for some integer $ℓ \in [y^{- 1}, ⌈ x^{- 2} ⌉]$ , there is an $(ℓ, y^{4} ∣ V (G) ∣ / ℓ^{2})$ -comb $((a_{i}, B_{i}) : i \in [ℓ])$ in $G$ , and there is a vertex $v \in V (G) ∖ ({a_{i} : i \in [ℓ]} \cup ⋃_{i = 1}^{ℓ} B_{i})$ that is complete to $⋃_{i = 1}^{ℓ} B_{i}$ and anticomplete to ${a_{i} : i \in [ℓ]}$ .

Facts & Assumptions

Given: Parameters $x, y$ and a graph $G$ satisfying the displayed hypotheses.

[L1]

If outcomes 1 and 2 fail, then there exist a vertex $v \in V (G)$ and disjoint sets $A, B \subseteq V (G) ∖ {v}$ with $A \subseteq V (G) ∖ N_{G} [v]$ , $B \subseteq N_{G} (v)$ , $∣ A ∣ \geq (1 - 3 y) ∣ V (G) ∣$ , $∣ B ∣ \geq y^{4} ∣ 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).

[L2]

If every vertex of a nonempty set $B$ has at least $ξ ∣ A ∣$ neighbours in a nonempty set $A$ , then some set $S \subseteq A$ with $∣ S ∣ \leq ⌈ 1 / ξ ⌉$ meets the neighbourhood in $A$ of at least half of the vertices of $B$ (A dense bipartite side has a small hitting set).

[L3]

In a bipartite graph $(A, B)$ where every vertex of $B$ has a neighbour in $A$ and every vertex of $A$ has at most $Δ$ neighbours in $B$ , either there is a $(t, Γ t^{- 2})$ -comb for some integer $t \geq 1$ , or $∣ B ∣ \leq \frac{3^{3 / 2}}{3 / 2 - \sqrt{3 / 2}} Γ^{1 / 2} Δ^{1 / 2}$ (A bipartite graph with bounded A-degree has a large comb or a small B-side).

[L4]

An $(ℓ, w)$ -comb in a graph is a sequence of distinct teeth $a_{i}$ and pairwise disjoint blocks $B_{i}$ such that $a_{i}$ is complete to $B_{i}$ and anticomplete to every other block (Combs in a graph).

Proof

technique · cases

1.1givencases

[assume-case pair] If outcome 1 already holds, there is nothing to prove.

1.2givencases

[assume-case sparser] If outcome 2 already holds, there is nothing to prove.

1.3L1given

[assume-case comb] Assume now that outcomes 1 and 2 both fail. Then [L1] gives a vertex $v \in V (G)$ and disjoint sets $A, B \subseteq V (G) ∖ {v}$ with $A \subseteq V (G) ∖ N_{G} [v]$ , $B \subseteq N_{G} (v)$ , and the displayed nearly covered sparse pair properties. In particular $A$ and $B$ are nonempty.

2.1step 1.3L2choosealgebra

Apply [L2] with $ξ = x^{2}$ to the sets $A, B$ . We obtain a set $S \subseteq A$ with $∣ S ∣ \leq ⌈ x^{- 2} ⌉$ such that at least half of the vertices of $B$ have a neighbour in $S$ . Let $B^{'} \subseteq B$ be the set of vertices with a neighbour in $S$ ; then $∣ B^{'} ∣ \geq ∣ B ∣ / 2 \geq \frac{1}{2} y^{4} ∣ V (G) ∣$ .

3.1step 1.3step 2.1L3algebra

Consider the bipartite graph between $S$ and $B^{'}$ . Every vertex of $B^{'}$ has a neighbour in $S$ by definition. Since $A$ is $y^{2}$ -sparse to $B$ and $S \subseteq A$ , every vertex of $S$ has at most $y^{2} ∣ B ∣$ neighbours in $B^{'}$ . Apply [L3] with $d : = 1 / 2$ , $Δ : = y^{2} ∣ B ∣$ , and $Γ : = ∣ B ∣$ .

4.1step 2.1step 3.1L3algebra

The second alternative of [L3] is impossible for these parameters, because it would give $∣ B^{'} ∣ \leq \frac{3^{3 / 2}}{3 / 2 - \sqrt{3 / 2}} ∣ B ∣^{1 / 2} (y^{2} ∣ B ∣)^{1 / 2} = \frac{3^{3 / 2}}{3 / 2 - \sqrt{3 / 2}} y ∣ B ∣$ . The constant in front of $y ∣ B ∣$ is less than $20$ , while $∣ B^{'} ∣ \geq ∣ B ∣ / 2 > 20 y ∣ B ∣$ since $y \leq 2^{- 8} < 1 / 40$ . Hence [L3] yields a $(ℓ, ∣ B ∣ / ℓ^{2})$ -comb $((a_{i}, B_{i}) : i \in [ℓ])$ with each $a_{i} \in S$ and each $B_{i} \subseteq B^{'}$ .

5.1step 1.3step 2.1step 4.1L4algebra

Because the teeth $a_{i}$ are distinct members of $S$ , we have $ℓ \leq ∣ S ∣ \leq ⌈ x^{- 2} ⌉$ . Also [L4] gives $∣ B_{i} ∣ \geq ∣ B ∣ / ℓ^{2}$ for each tooth block, while every $a_{i} \in S \subseteq A$ has at most $y^{2} ∣ B ∣$ neighbours in $B$ . Since $a_{i}$ is complete to $B_{i}$ by [L4], this forces $∣ B ∣ / ℓ^{2} \leq ∣ B_{i} ∣ \leq y^{2} ∣ B ∣$ , and therefore $ℓ \geq y^{- 1}$ . Finally $∣ B ∣ \geq y^{4} ∣ V (G) ∣$ from step 1.3, so each block has size at least $y^{4} ∣ V (G) ∣ / ℓ^{2}$ .

6.1step 1.3step 5.1

By step 1.3, we already have a vertex $v$ with $B \subseteq N_{G} (v)$ and $A \subseteq V (G) ∖ N_{G} [v]$ . Since each $a_{i} \in A$ and each $B_{i} \subseteq B$ , the vertex $v$ is complete to $⋃_{i} B_{i}$ and anticomplete to ${a_{i} : i \in [ℓ]}$ . Together with step 5.1, this is exactly outcome 3.

7.1step 1.1step 1.2step 6.1cases-exhaustive∎

The three cases 1.1, 1.2, and 1.3 exhaust the possibilities, so one of the stated outcomes always holds.

Depends on

Used by

Dependency tree · two levels

16 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

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Lemma 2.10 (standard reference, not scraped)
Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. VII. The five-vertex path, Lemma 5.2 (standard reference, not scraped)