ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01

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 $E$ -graph sits inside a one-subdivided star and deletes to the five-vertex path

Example

The $E$ -graph occurs as an induced subgraph of the $1$ -subdivision of $K_{1, 3}$ , and deleting the remaining pendant leaf recovers the five-vertex path.

Facts & Assumptions

Given: The $1$ -subdivision of $K_{1, 3}$ with center $c$ , subdivision vertices $s_{1}, s_{2}, s_{3}$ , and leaves $t_{1}, t_{2}, t_{3}$ .

[L1]

The $E$ -graph has edge set

{p_{1} p_{2}, p_{2} p_{3}, p_{3} p_{4}, p_{4} p_{5}, p_{3} q}

(The $E$ -graph and co- $E$ ).

[L2]

The path $P_{5}$ has five vertices in one chain and no other edges (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · direct finite check

1.1

On the six-vertex subset ${t_{1}, s_{1}, c, s_{2}, t_{2}, s_{3}}$ , the induced edges are $t_{1} s_{1}$ , $s_{1} c$ , $c s_{2}$ , $s_{2} t_{2}$ , and $c s_{3}$ . Relabelling $p_{1} = t_{1}$ , $p_{2} = s_{1}$ , $p_{3} = c$ , $p_{4} = s_{2}$ , $p_{5} = t_{2}$ , and $q = s_{3}$ turns this induced subgraph into the edge set from [L1]. Hence the selected subset is an induced copy of the $E$ -graph.

L1givenconstruct

2.1

Deleting the vertex $q = s_{3}$ from that induced copy leaves the five vertices $p_{1}, p_{2}, p_{3}, p_{4}, p_{5}$ with exactly the four path edges $p_{1} p_{2}, p_{2} p_{3}, p_{3} p_{4}, p_{4} p_{5}$ . By [L2], this is $P_{5}$ .

step 1.1L2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Lemma 2.2 (standard reference, not scraped)

The EE-graph sits inside a one-subdivided star and deletes to the five-vertex path