Alphabeta Math
LemmaStatement: 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 and Bird singleton families are leaf-reducible

Statement

The singleton forbidden families {E} and {Bird} are leaf-reducible. In E, deleting the leaf q attached to the middle vertex gives P5. In Bird, deleting the added leaf w gives the bull. Both reduced singleton families have the Erdős-Hajnal property.

Facts & Assumptions

Given: The E-graph on {p1,…,p5,q}, the Bird graph on {x1,x2,x3,y,z,w}, and the bull on {x1,x2,x3,y,z}.

[L1]

The E-graph has edge set {p1p2,p2p3,p3p4,p4p5,p3q} and co-E is its complement (The E-graph and co-E).

[L2]

The Bird graph has edge set {x1x2,x2x3,x1x3,x1y,x2z,yw} and co-Bird is its complement (The Bird graph and co-Bird).

[L3]

The bull has vertex set {x1,x2,x3,y,z} and edge set {x1x2,x2x3,x1x3,x1y,x2z} (The bull graph).

[L4]

The path graph P5 has vertices 0,1,2,3,4 and edges {i,i+1} for 0≤i<4, and no others (Empty and complete graphs, complete bipartite graphs, and the convention that Pn and Cn have n vertices).

[L5]

A finite family F is leaf-reducible when some H∈F has a leaf v and the modified family {H∖{v}}∪(F∖{H}) has the Erdős-Hajnal property in the family sense (Leaf-reducible finite graph families).

[L6]

A vertex of degree one is a leaf; deletion H∖{v} is the subgraph induced by V(H)∖{v} (Trees, forests, leaves and isolated vertices, Subgraphs, induced subgraphs and spanning subgraphs).

[L7]

A graph isomorphism is a bijection preserving adjacency and nonadjacency, and an induced embedding of H in G is an injection preserving adjacency and nonadjacency on distinct pairs (Graph isomorphisms, automorphisms and graph complements, Induced embeddings and induced copies of a graph).

[L8]

A graph is H-free when it has no induced copy of H, and F-free means H-free for every H∈F (H-free and F-free graphs under the induced-subgraph convention).

[L9]

The graph P5 has the Erdős-Hajnal property (The five-vertex path and its complement have the Erdős-Hajnal property).

[L10]

The bull graph has the Erdős-Hajnal property (The bull graph has the Erdős-Hajnal property).

[L11]

A graph H has the Erdős-Hajnal property when the hereditary class of H-free graphs has an Erdős-Hajnal constant, and the same terminology applies to a finite family through its class of family-free graphs (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).

Proof

technique · direct finite check of the two deletions, followed by the published Erdős-Hajnal inputs for the reduced graphs
1.1

In E the only edge incident with q is p3q, by [L1]. Hence q has degree one and is a leaf, and E∖{q} is the induced subgraph on {p1,p2,p3,p4,p5} with exactly the four edges p1p2,p2p3,p3p4,p4p5.

L1L6given
1.2

In Bird the only edge incident with w is yw, by [L2]. Hence w has degree one and is a leaf, and Bird∖{w} is the induced subgraph on {x1,x2,x3,y,z} with edge set {x1x2,x2x3,x1x3,x1y,x2z}, which is exactly the bull of [L3].

L2L3L6given
2.1

Take F={Bird} and the member Bird with the leaf w of step 1.2. Then Bird∖{w} is the bull by step 1.2, so the modified family of [L5] is the singleton {bull}, whose Erdős-Hajnal property is [L10] read through the family terminology of [L11]; both phrases describe the same class of bull-free graphs. Hence {Bird} is leaf-reducible.

step 1.2L10L11L5
2.2

The map φ(i):=pi+1 for i=0,1,2,3,4 is a bijection from V(P5) onto {p1,…,p5} whose four edges {i,i+1} of [L4] correspond to the four edges pi+1pi+2 listed in step 1.1, and no other pairs are edges on either side. A bijection matching adjacency and nonadjacency is an isomorphism by [L7], so E∖{q}≅P5.

L4step 1.1L7
3.1

Consequently a finite graph G is (E∖{q})-free if and only if it is P5-free: composing an induced embedding of P5 in G with the inverse of the isomorphism of step 2.2 yields an induced embedding of E∖{q} in G, and composing an induced embedding of E∖{q} with that isomorphism yields an induced embedding of P5.

step 2.2L7L8
4.1

By [L9] the class of P5-free graphs has an Erdős-Hajnal constant; step 3.1 identifies it with the class of (E∖{q})-free graphs, so that class also has a constant, and [L11] makes the singleton family {E∖{q}} a family with the Erdős-Hajnal property.

step 3.1L9L11
5.1

Take F={E} and the member H=E with the leaf q of step 1.1. Then H∖{q}=E∖{q}, so the modified family of [L5] is {E∖{q}}∪({E}∖{E})={E∖{q}}, which has the Erdős-Hajnal property by step 4.1. Hence {E} is leaf-reducible.

step 1.1step 4.1L5
6.1

The two singleton families are leaf-reducible, the deleted graph is P5 in the E case and the bull in the Bird case, and the reduced singleton families {E∖{q}} and {Bird∖{w}} have the Erdős-Hajnal property by steps 2.1 and 4.1. These are all the assertions of the statement.

step 5.1step 2.1∎

Remarks

  • The two deletions are exactly the source's Section 2.1 observation that E and Bird are leaf-reducible: q is the pendant vertex of E at the middle of the P5, and w is the extra pendant vertex attached at the horn y of the bull inside Bird.
  • No Choice. Every object here is finite and every step is a finite adjacency check or a citation of a published finite result; no selection from a family of nonempty sets occurs.

Depends on

Used by

Dependency tree · two levels

29 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