LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 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.

For disjoint nonempty vertex sets, weak $c$ -sparsity says exactly that the edge density is at most $c$

Statement

Let $G$ be a finite simple graph, let $c \geq 0$ , and let $X, Y \subseteq V (G)$ be disjoint nonempty sets. Then $(X, Y)$ is weakly $c$ -sparse if and only if $d_{G} (X, Y) \leq c$ .

Facts & Assumptions

Given: A finite simple graph $G$ , a real $c \geq 0$ , and disjoint nonempty sets $X, Y \subseteq V (G)$ .

[L1]

Weak $c$ -sparsity means $∣ E_{G} (X, Y) ∣ \leq c ∣ X ∣ ∣ Y ∣$ (Sparsity of one vertex set to another, and weak sparsity of a pair).

[L2]

The edge density is $d_{G} (X, Y) = e_{G} (X, Y) / (∣ X ∣ ∣ Y ∣)$ , where $e_{G} (X, Y)$ counts ordered pairs $(x, y) \in X \times Y$ that form an edge (Edge counts and densities between nonempty vertex sets).

[L3]

Because $X$ and $Y$ are disjoint, each edge between them contributes exactly one such ordered pair, so $e_{G} (X, Y) = ∣ E_{G} (X, Y) ∣$ (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

Proof

technique · direct

1.1L1L3

By [L3], the inequality of [L1] is the same as $e_{G} (X, Y) \leq c ∣ X ∣ ∣ Y ∣$ .

2.1step 1.1L2algebra

Since $X$ and $Y$ are nonempty, dividing by $∣ X ∣ ∣ Y ∣$ is legitimate, and [L2] turns the inequality of step 1.1 into $d_{G} (X, Y) \leq c$ .

3.1step 2.1∎

Reversing the same algebra shows the converse implication, so the two conditions are equivalent.

Depends on

Used by

Dependency tree · two levels

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

For disjoint nonempty vertex sets, weak cc-sparsity says exactly that the edge density is at most cc