ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-09-26 (gpt-6-sol)

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 forest pure-pair theorem specialized to $P_{4}$

Example

Every finite $P_{4}$ -free graph with at least two vertices has a pure pair whose two sides both have linear size.

Facts & Assumptions

Given: The standard path $P_{4}$ .

[L1]

For every forest $H$ , every graph with no induced $H$ and no induced $\overline{H}$ has a linear pure pair (For every forest $H$ , graphs excluding $H$ and $\overline{H}$ have a linear pure pair).

Verification

technique · direct

1.1

The graph $P_{4}$ is a tree, hence a forest. Its complement has edges ${1, 3}$ , ${1, 4}$ , and ${2, 4}$ , which form the path $3 - 1 - 4 - 2$ . So $\overline{P_{4}} ≅ P_{4}$ .

givenalgebra

2.1

Applying [L1] with $H = P_{4}$ therefore gives a linear pure pair in every graph with no induced $P_{4}$ and no induced $\overline{P_{4}}$ . By step 1.1, that is exactly the class of $P_{4}$ -free graphs.

step 1.1L1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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

The forest pure-pair theorem specialized to P4P4​