ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-09

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 labelled blowup and its good copies

Example

Label $P_{3}$ by $1, 2, 3$ , with edges $12, 23$ . Let $A_{i} = {(i, 1), (i, 2), (i, 3)}$ . Make each $A_{i}$ independent, put all edges between $A_{1}, A_{2}$ and between $A_{2}, A_{3}$ , and no edges between $A_{1}, A_{3}$ . This blowup has 27 good copies, 9 good copies extending any prescribed middle vertex, and 126 total labelled induced embeddings of $P_{3}$ .

Facts & Assumptions

Given: The three explicit blocks and edges specified in the example, with $P_{3}$ labelled $1, 2, 3$ .

[F1]

From Labelled blowup and good induced copy: For $I \subseteq V (J)$ , a good embedding of $J [I]$ is an induced embedding $ϕ$ satisfying $ϕ (i) \in A_{i}$ for every $i \in I$ .

[F2]

From Good copy extension count: Every good embedding of $J [I]$ , $I \subseteq V (J)$ , has at least $(t / j)^{j - ∣ I ∣}$ good extensions to $J$ .

[F3]

From The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ : $∣ A \times B ∣ = ∣ A ∣ \cdot ∣ B ∣$

Verification

1.1F1F3

The prescribed pairs have zero wrong adjacencies in either direction, so the displayed sets form a $(3, 0)$ -blowup and also a $(3, 1 / 3)$ -blowup. By [F1], each choice of one vertex from its assigned block gives a good embedding; conversely such an embedding has exactly those three choices. Thus [F3] counts $3 \cdot 3 \cdot 3 = 27$ .

2.1F2F3step 1.1

If the middle image is fixed, the endpoint choices are independently the three vertices of $A_{1}$ and of $A_{3}$ , giving $3 \cdot 3 = 9$ by [F3]. The lower bound [F2] at $t = j = 3$ , $∣ I ∣ = 1$ , is $(3 / 3)^{2} = 1$ , so this instance exceeds that bound. For the empty partial embedding it is $(3 / 3)^{3} = 1$ , also below the exact 27.

3.1step 1.1step 2.1algebra∎

The full host is $K_{3, 6}$ with parts $A_{2}$ and $A_{1} \cup A_{3}$ . An induced $P_{3}$ has its center in one part and two distinct ordered endpoints in the other. Centers in $A_{2}$ give $3 \cdot 6 \cdot 5 = 90$ embeddings; centers in the other part give $6 \cdot 3 \cdot 2 = 36$ . Both counts follow by successive choices, and the two cases partition all embeddings. The total is $90 + 36 = 126$ , including choices whose endpoints lie in the same original block.

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, 4.2, explicit specialization.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

18 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

Bucic, Nguyen, Scott and Seymour, Induced subgraph density I (standard reference, not scraped)