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

The empty forbidden family is not Erdős–Hajnal

Statement refuted

The empty forbidden family has the Erdős–Hajnal property.

Facts & Assumptions

Given: The empty family $\emptyset$ of graphs.

[L1]

A graph is $\emptyset$ -free exactly when it is $H$ -free for every $H \in \emptyset$ , which is vacuous ( $H$ -free and $F$ -free graphs under the induced-subgraph convention).

[L2]

The hereditary class of all finite graphs does not have the Erdős–Hajnal property (The hereditary class of all finite graphs does not have the Erdős–Hajnal property).

[L3]

On a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent (For a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent).

Counterexample

technique · direct

1.1

By [L1], every finite graph is $\emptyset$ -free. So the class of $\emptyset$ -free graphs is exactly the class of all finite graphs.

2.1

Applying [L2] to the class identified in step 1.1 shows that the empty family does not have the Erdős–Hajnal property.

step 1.1L2

3.1

Therefore the claim is false. By [L3], the empty family also has neither of the other two equivalent properties from the A page.

step 2.1L3∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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