ExampleConstruction: AI-adaptedVerification: 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.

In a disjoint union of cliques of order $k$ the whole vertex set is $(k / n)$ -sparse

Example

Let $G$ be a nonempty disjoint union of cliques, each of order at most $k$ , on a total of $n \geq 1$ vertices. Then $V (G)$ is $(k / n)$ -sparse.

Facts & Assumptions

Given: A nonempty graph $G$ on $n \geq 1$ vertices whose connected components are cliques of order at most $k$ .

[L1]

In a disjoint union of cliques, each vertex is adjacent exactly to the other vertices in its own clique component (The connected components of a graph partition its vertex set and are its maximal connected subgraphs, Connected graphs and connected components defined by the existence of vertex paths).

[L2]

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

Verification

technique · direct

1.1L1

By [L1], every vertex of $G$ lies in a clique component of size at most $k$ , so it has at most $k - 1 \leq k$ neighbours in the whole vertex set.

2.1step 1.1L2algebra∎

Since the whole set has size $n$ , the bound of step 1.1 reads $∣ N_{G} (v) ∣ \leq (k / n) n$ for every vertex $v$ . Therefore [L2] makes $V (G)$ $(k / n)$ -sparse.

Depends on

Used by

Every c-sparse set of size m contains a stable set of size at least m/2 False statement

Dependency tree · two levels

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

In a disjoint union of cliques of order kk the whole vertex set is (k/n)(k/n)-sparse