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.

✓ 4 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Pure Pairs, Forests and Path–Antipath Classes — Examples

1 · Prerequisites

2 · Summary

These examples illustrate the path–antipath and forest results and the leaf–co-leaf extension construction.

The forest and leaf-deletion proof chains are undergoing repair; publication status does not certify that those outstanding proof obligations are closed.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28Open item page →

The path-antipath theorem specialized to $P_{5}$ and $\overline{P_{5}}$

Example

Graphs with no induced $P_{5}$ and no induced $\overline{P_{5}}$ have the Erdős–Hajnal property.

Facts & Assumptions

Given: The standard five-vertex path $P_{5}$ .

[L1]

For every integer $k \geq 2$ , the class forbidding $P_{k}$ and $\overline{P_{k}}$ has the Erdős–Hajnal property (For every $k$ , the class forbidding $P_{k}$ and $\overline{P_{k}}$ has the Erdős–Hajnal property).

[L2]

The graph $P_{5}$ is the standard path on five vertices (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · direct

1.1L1L2

By [L2], the parameter choice $k = 5$ in [L1] is exactly the class forbidding $P_{5}$ and $\overline{P_{5}}$ .

2.1step 1.1∎

Therefore graphs with no induced $P_{5}$ and no induced $\overline{P_{5}}$ have the Erdős–Hajnal property.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-09-26 (gpt-6-sol)Open item page →

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.1givenalgebra

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}$ .

2.1step 1.1L1∎

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.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28Open item page →

A co-leaf of $\overline{P_{5}}$ is exactly a leaf of $P_{5}$

Example

Let $P_{5}$ have vertices $1, 2, 3, 4, 5$ in path order. In $\overline{P_{5}}$ the vertices $1$ and $5$ are co-leaves, and no other vertex is.

Facts & Assumptions

Given: The five-vertex path $P_{5}$ with edges $12, 23, 34, 45$ .

[L1]

A co-leaf of a graph is a vertex that is a leaf in the complement, equivalently a vertex of degree $∣ V (G) ∣ - 2$ (Co-leaves of a finite graph).

[L2]

The complement contains exactly the nonedges of the original graph (Graph isomorphisms, automorphisms and graph complements).

Verification

technique · direct

1.1givenL2algebra

By [L2], the complement $\overline{P_{5}}$ has edges $13, 14, 15, 24, 25, 35$ . So vertices $1$ and $5$ each have degree $3 = 5 - 2$ in $\overline{P_{5}}$ , while vertices $2, 3, 4$ each have degree $2$ .

2.1step 1.1L1∎

Step 1.1 and [L1] show that $1$ and $5$ are co-leaves of $\overline{P_{5}}$ , and that $2, 3, 4$ are not. Since $1$ and $5$ are exactly the leaves of the path $P_{5}$ , the co-leaves of $\overline{P_{5}}$ are precisely the leaves of $P_{5}$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-09-26 (gpt-6-sol)Open item page →

The leaf/co-leaf corollary recovers the $P_{5}$ case from the $P_{4}$ case

Example

Graphs with no induced $P_{5}$ and no induced $\overline{P_{5}}$ have the Erdős-Hajnal property, and this follows from the $P_{4}$ case via the leaf/co-leaf corollary.

Facts & Assumptions

Given: The family $F : = {P_{5}, \overline{P_{5}}}$ .

[L1]

If deleting a leaf from one member of a finite forbidden family and a co-leaf from another member produces two smaller families with the Erdős-Hajnal property, then the original family has the Erdős-Hajnal property (Deleting a leaf and a co-leaf preserves the Erdős-Hajnal property of a finite forbidden family).

[L2]

The Erdős-Hajnal property passes from a hereditary class to each hereditary subclass (The Erdős–Hajnal property and each of its constants pass to hereditary subclasses).

[L3]

For every forest $H$ , graphs with no induced $H$ and no induced $\overline{H}$ have the Erdős-Hajnal property (For every forest $H$ , graphs excluding $H$ and $\overline{H}$ have the Erdős-Hajnal property).

[L4]

A co-leaf of a graph is a vertex that is a leaf of the complement, equivalently a vertex of degree $∣ V (G) ∣ - 2$ (Co-leaves of a finite graph).

[L5]

The complement contains exactly the nonedges of the original graph (Graph isomorphisms, automorphisms and graph complements).

[L6]

Every class defined by forbidden induced subgraphs is hereditary (Every class defined by forbidden induced subgraphs is hereditary).

Verification

technique · direct

1.1givenL4L5algebra

The graph $P_{5}$ has leaf $1$ . By [L5], the complement $\overline{P_{5}}$ has edges $13$ , $14$ , $15$ , $24$ , $25$ , and $35$ , so vertex $1$ has degree $3 = 5 - 2$ . By [L4], vertex $1$ is therefore a co-leaf of $\overline{P_{5}}$ . Delete that leaf of $P_{5}$ and that co-leaf of $\overline{P_{5}}$ . The resulting smaller families are $F_{1} = {P_{4}, \overline{P_{5}}} and F_{2} = {P_{5}, \overline{P_{4}}} .$ From the path edges $12$ , $23$ , and $34$ , [L5] gives complement edges $13$ , $14$ , and $24$ , which form the path $3$ - $1$ - $4$ - $2$ . Thus $\overline{P_{4}} ≅ P_{4}$ .

2.1step 1.1L2L3L6

The path $P_{4}$ is a forest, and step 1.1 shows that $\overline{P_{4}} ≅ P_{4}$ . Therefore [L3] applied with $H = P_{4}$ gives the Erdős-Hajnal property for the hereditary class of $P_{4}$ -free graphs. By [L6], the classes defined by forbidding ${P_{4}, \overline{P_{5}}}$ and ${P_{5}, \overline{P_{4}}}$ are hereditary. Each is a subclass of the $P_{4}$ -free class, using step 1.1 for the second family. Hence [L2] gives the Erdős-Hajnal property for both $F_{1}$ and $F_{2}$ .

3.1step 1.1step 2.1L1∎

Applying [L1] to the family $F = {P_{5}, \overline{P_{5}}}$ and the two smaller families from steps 1.1 and 2.1 yields the Erdős-Hajnal property for graphs with no induced $P_{5}$ and no induced $\overline{P_{5}}$ .

Pure Pairs, Forests and Path–Antipath Classes — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The path-antipath theorem specialized to P5P5​ and P5‾P5​​

Example

Facts & Assumptions

Verification

The forest pure-pair theorem specialized to P4P4​

Example

Facts & Assumptions

Verification

A co-leaf of P5‾P5​​ is exactly a leaf of P5P5​

Example

Facts & Assumptions

Verification

The leaf/co-leaf corollary recovers the P5P5​ case from the P4P4​ case

Example

Facts & Assumptions

Verification

The path-antipath theorem specialized to $P_{5}$ and $\overline{P_{5}}$

The forest pure-pair theorem specialized to $P_{4}$

A co-leaf of $\overline{P_{5}}$ is exactly a leaf of $P_{5}$

The leaf/co-leaf corollary recovers the $P_{5}$ case from the $P_{4}$ case