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

A subset of a $c$ -sparse set that is not $c$ -sparse

Statement refuted

Every subset of a $c$ -sparse set is again $c$ -sparse.

Facts & Assumptions

Given: An even integer $2 m \geq 4$ , a perfect matching on $2 m$ vertices, its whole vertex set $X$ , and one matched edge ${u, v} \subseteq X$ .

[L1]

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

Counterexample

technique · constructive

1.1

Every vertex of the matching has exactly one neighbour, so the whole set $X$ is $(1 / (2 m))$ -sparse by [L1].

L1givenconstruct

2.1

The subset ${u, v}$ has size $2$ , and each of its vertices still has one neighbour inside it. So it is not $(1 / (2 m))$ -sparse whenever $m \geq 2$ .

step 1.1L1algebra

3.1

Therefore sparsity does not pass to arbitrary subsets, which is exactly why A subset occupying at least a $λ$ fraction of a $c$ -sparse set is $(c / λ)$ -sparse pays a factor of $1 / λ$ .

step 2.1discharge-construct∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 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.

A subset of a cc-sparse set that is not cc-sparse