LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-07

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 family consisting of $H_{5}$ and co- $E$ has the Erdős–Hajnal property

Statement

The finite forbidden family ${H_{5}, c o - E}$ has the Erdős–Hajnal property.

Facts & Assumptions

Given: The graphs $H_{0}, \dots, H_{5}$ and the graph co- $E$ .

[F1]

The graph $H_{0}$ has the Erdős–Hajnal property (The graph $H_{0}$ has the Erdős-Hajnal property).

[F2]

The graph $\overline{P_{5}}$ has the Erdős–Hajnal property (The five-vertex path and its complement have the Erdős-Hajnal property).

[F3]

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

[F4]

Huang--Ju--Zhou, Corollary 1.8, states the following leaf/co-leaf transfer. Let $F$ be a finite family, let $H_{1} \in F$ have a leaf $v$ , and let $H_{2} \in F$ have a co-leaf $w$ . If both families obtained from $F$ by replacing, respectively, $H_{1}$ by $H_{1} ∖ {v}$ and $H_{2}$ by $H_{2} ∖ {w}$ have the Erdős--Hajnal property, then $F$ has the Erdős--Hajnal property.

Proof

technique · induction

1.1

The class of ${H_{0}, c o - E}$ -free graphs is a hereditary subclass of the class of $H_{0}$ -free graphs, and the class of ${H_{i}, \overline{P_{5}}}$ -free graphs is a hereditary subclass of the class of $\overline{P_{5}}$ -free graphs. Thus [F1]--[F3] give the Erdős–Hajnal property for both families, for every $i \in [5]$ .

F1F2F3base

1.2

Fix $i \in [5]$ and suppose that ${H_{i - 1}, c o - E}$ has the property. In $F = {H_{i}, c o - E}$ , deleting the leaf $v_{i}^{'}$ of $H_{i}$ gives $H_{i - 1}$ . The vertex $q$ is a leaf of $E$ , so it is a co-leaf of co- $E$ , and deleting it from co- $E$ leaves $\overline{P_{5}}$ . Hence the two modified families in [F4] are exactly ${H_{i - 1}, c o - E}$ and ${H_{i}, \overline{P_{5}}}$ .

F4ih

2.1

Step 1.2, the induction hypothesis, and the second base family from step 1.1 let [F4] yield the property for ${H_{i}, c o - E}$ .

step 1.1step 1.2F4

3.1

Starting with $i = 1$ and repeating step 2.1 through $i = 5$ proves the property for ${H_{5}, c o - E}$ .

step 1.1step 2.1discharge-induction∎

Depends on

Used by

Dependency tree · two levels

19 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

Huang, Ju, and Zhou, Erdős-Hajnal beyond the five-vertex path, Lemma 6.3 (standard reference, not scraped)
Huang, Ju, and Zhou, Erdős-Hajnal beyond the five-vertex path, Corollary 1.8 (standard reference, not scraped)

The family consisting of H5H5​ and co-EE has the Erdős–Hajnal property