Alphabeta Math
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 Bird graph has the Erdős-Hajnal property

Statement

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

Facts & Assumptions

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

[L1]

The singleton family {Bird} is generalized nice (The singleton Bird family is generalized nice).

[L2]

The singleton family {Bird} is leaf-reducible; deleting the added leaf w gives the bull, 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 {Bird} 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∈C satisfies hom⁡(G)≥∣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 Bird graph has vertex set {x1,x2,x3,y,z,w} and edge set {x1x2,x2x3,x1x3,x1y,x2z,yw} (The Bird graph and co-Bird).

Proof

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

The family {Bird} 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 {Bird} has the Erdős-Hajnal property: the hereditary class of Bird-free graphs has an Erdős-Hajnal constant ϵB>0.

step 1.1L4
3.1

Unwinding [L5] and using that the class of Bird-free graphs is hereditary by [L6], the constant ϵB satisfies hom⁡(G)≥∣V(G)∣ϵB for every nonempty Bird-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)∣ϵB.

step 2.1L5L6
4.1

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

step 3.1L5L6L7∎

Remarks

  • This is Theorem 1.11 of the source. The E theorem of the companion A-page item is used only through the preceding property-(∗) corollary for Bird, never as forward input; the dependency order is E before Bird.
  • As for the E-graph, no numerical value of ϵB is claimed: the generic reduction yields 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

Dependency tree · two levels

41 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