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

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.

Complementation sends a disjoint $ϵ$ -regular pair of density $d$ to one of density $1 - d$

Statement

Let $X, Y$ be disjoint nonempty vertex sets. If $(X, Y)$ is $ϵ$ -regular of density $d$ in $G$ , then it is $ϵ$ -regular of density $1 - d$ in $\overline{G}$ .

Facts & Assumptions

Given: Disjoint nonempty sets $X, Y$ forming an $ϵ$ -regular pair of density $d$ in $G$ .

[L1]

Regularity means that every sufficiently large subpair $(A, B)$ has density within $ϵ$ of $d (X, Y)$ ( $ϵ$ -regular pairs and self-regular vertex sets).

[L2]

In the complement, exactly the missing pairs of distinct vertices are edges (Graph isomorphisms, automorphisms and graph complements).

Proof

technique · direct

1.1givenL2

Because $X$ and $Y$ are disjoint, every ordered pair in $A \times B$ consists of distinct vertices and is an edge in exactly one of $G, \overline{G}$ ; hence $d_{\overline{G}} (A, B) = 1 - d_{G} (A, B)$ for every nonempty $A \subseteq X$ , $B \subseteq Y$ .

2.1step 1.1

Taking $A = X, B = Y$ gives $d_{\overline{G}} (X, Y) = 1 - d$ .

3.1step 1.1step 2.1L1∎

For every subpair meeting the thresholds in [L1], $∣ d_{\overline{G}} (A, B) - (1 - d) ∣ = ∣ d_{G} (A, B) - d ∣ \leq ϵ$ , so the complemented pair is $ϵ$ -regular.

Disjointness is essential for the exact density formula. When $X$ and $Y$ overlap, diagonal pairs are edges in neither graph and contribute a correction of $∣ X \cap Y ∣ / (∣ X ∣ ∣ Y ∣)$ .

Depends on

Used by

Induced counting lemma: regular edge and nonedge pairs force many induced copies Theorem

Dependency tree · two levels

5 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

D. Conlon and J. Fox, Graph removal lemmas, sec. 3.1 (standard reference, not scraped)

Complementation sends a disjoint ϵϵ-regular pair of density dd to one of density 1−d1−d