TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-sol)audited 2026-09-27

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 has the Erdős-Hajnal property

Statement

There exists $ϵ_{E} > 0$ such that every nonempty finite simple graph $G$ with no induced copy of the $E$ -graph has a clique or stable set of size at least $∣ V (G) ∣^{ϵ_{E}}$ . Equivalently the singleton family ${E}$ has the Erdős-Hajnal property.

Facts & Assumptions

Given: The singleton family ${E}$ and its class of $E$ -free finite graphs.

[L1]

The singleton family ${E}$ is generalized nice (The singleton $E$ -graph family is generalized nice).

[L2]

The singleton family ${E}$ is leaf-reducible; deleting the leaf $q$ from $E$ gives $P_{5}$ , and the reduced singleton family has the Erdős-Hajnal property (The $E$ -graph and Bird singleton families are leaf-reducible).

[L3]

The singleton family ${E}$ is wonderful (The $E$ -graph and the Bird graph are wonderful).

[L4]

Every generalized nice, leaf-reducible, wonderful finite family has the Erdős-Hajnal property (Leaf-reducible wonderful generalized nice finite families have the Erdős-Hajnal property).

[L5]

A positive real $ϵ$ is an Erdős-Hajnal constant for a hereditary class $C$ when every nonempty $G \in C$ satisfies $hom (G) \geq ∣ V (G) ∣^{ϵ}$ ; a graph $H$ has the Erdős-Hajnal property when its class of $H$ -free graphs has such a constant, and $hom (G) = \max {ω (G), α (G)}$ is the size of the largest clique or stable set of $G$ (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class, Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

[L6]

Graph $G$ is $H$ -free when it has no induced copy of $H$ ( $H$ -free and $F$ -free graphs under the induced-subgraph convention), and the class of $H$ -free graphs is hereditary for every finite graph $H$ (Every class defined by forbidden induced subgraphs is hereditary).

[L7]

The $E$ -graph is the six-vertex graph with 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$ ).

Proof

technique · direct application of the published reduction to the singleton family $\{E\}$, then unwinding the definition of the Erdős-Hajnal constant

1.1

The family ${E}$ satisfies the three hypotheses of [L4]: it is generalized nice by [L1], leaf-reducible by [L2], and wonderful by [L3].

L1L2L3given

2.1

By [L4], the family ${E}$ has the Erdős-Hajnal property: the hereditary class of $E$ -free graphs has an Erdős-Hajnal constant $ϵ_{E} > 0$ .

step 1.1L4

3.1

Unwinding [L5] and using that the class of $E$ -free graphs is hereditary by [L6], the constant $ϵ_{E}$ satisfies $hom (G) \geq ∣ V (G) ∣^{ϵ_{E}}$ for every nonempty $E$ -free graph $G$ ; since $hom (G) = \max {ω (G), α (G)}$ , this says exactly that $G$ has a clique or stable set of size at least $∣ V (G) ∣^{ϵ_{E}}$ .

step 2.1L5L6

4.1

The first assertion of the statement is step 3.1; the equivalence with the singleton family ${E}$ having the Erdős-Hajnal property is the definitional reading [L5] of the class of $E$ -free graphs, which by [L6] and [L7] is the class in which absence of an induced copy of the $E$ -graph is required.

step 3.1L5L6L7∎

Remarks

This is Theorem 1.10 of the source, deduced there from its Lemma 6.3, Lemma 6.4 and the local criterion of Lemma 5.1, exactly as generalized niceness for ${E}$ is recorded on the preceding corollary. No numerical value of $ϵ_{E}$ is claimed; the source does not give one and the generic reduction produces only an unspecified positive exponent.
No Choice. The proof composes published finite reductions and makes no selection from a family of nonempty sets.

Depends on

Used by

The singleton Bird family has property (*) Corollary
The E theorem reaches an induced P₅ witness Example

Dependency tree · two levels

47 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, Theorem 1.10 and Section 6 (standard reference, not scraped)
Nguyen, Notes on Recent Work on the Erdős-Hajnal Conjecture, Section 5, restricted-set/blockade exponent mechanism (standard reference, not scraped)

The EE-graph has the Erdős-Hajnal property