ExampleConstruction: AI-adaptedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck 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.

The $0$ -sparse sets are exactly the stable sets and the $0$ -dense sets exactly the cliques

Example

For a nonempty set $X$ , the condition of being $0$ -sparse is exactly that $G [X]$ have no edges, and the condition of being $0$ -dense is exactly that $G [X]$ be complete.

Facts & Assumptions

Given: A finite simple graph $G$ and a nonempty set $X \subseteq V (G)$ .

[L1]

A set is $0$ -sparse when every vertex of it has at most $0 \cdot ∣ X ∣ = 0$ neighbours inside it ( $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

[L2]

Stable sets and cliques are the edgeless and complete induced subgraphs, respectively (Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[L3]

Complementation exchanges sparse and dense sets (A set is $c$ -sparse in $G$ exactly when it is $c$ -dense in $\overline{G}$ , so $c$ -restrictedness is complement-invariant).

Verification

technique · direct

1.1

By [L1], $X$ is $0$ -sparse exactly when every vertex of $X$ has no neighbour in $X$ , which is exactly the statement that $G [X]$ has no edges.

L1L2

2.1

Therefore [L2] identifies the $0$ -sparse sets with the stable sets.

step 1.1L2

3.1

Applying [L3] to step 2.1 shows that the $0$ -dense sets are exactly the cliques.

step 2.1L3∎

Depends on

Used by

Dependency tree · two levels

12 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. 1.1 (standard reference, not scraped)

The 00-sparse sets are exactly the stable sets and the 00-dense sets exactly the cliques