Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01
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 the Bird graph are wonderful

Statement

The singleton families {E} and {Bird} are wonderful. Equivalently, the E-graph and the Bird graph are wonderful.

Facts & Assumptions

Given: The E-graph, the Bird graph, and the wonderfulness criterion.

[L1]

A finite family is wonderful if it satisfies either the star-subdivision obstruction or the special-vertex obstruction from the previous criterion (Star and special-vertex obstructions force wonderfulness).

[L2]

Every graph on at most five vertices has the Erdős-Hajnal property (Every graph on at most five vertices has the Erdős-Hajnal property).

[L4]

The Bird graph and co-Bird are complements of one another, and H+ is the graph obtained by adding a new vertex adjacent exactly to the two distinguished vertices (The Bird graph and co-Bird, The graphs H+ and H− for two distinguished vertices).

[A1]

Let H be the graph on vertices v1,…,v6 with edge set {v1v2,v1v3,v1v5,v1v6,v2v3,v2v4,v2v5,v3v5,v4v5,v4v6}. Its distinguished vertices are v1 and v2.

Proof

technique · verify the two criterion inputs explicitly
1.1L1givenconstruct

For the E-graph, take the 1-subdivision of K1,3 with center c, subdivision vertices s1,s2,s3, and leaves t1,t2,t3. On the six-vertex subset {t1,s1,c,s2,t2,s3}, the induced edges are t1s1, s1c, cs2, s2t2, and cs3, which is exactly the edge set of the E-graph from The E-graph and co-E. Thus E is an induced subgraph of the 1-subdivision of K1,3, so [L1] makes {E} wonderful.

1.2A1L2L3

In the graph H from [A1], the vertices v2 and v5 are adjacent to each other and both have the same neighbourhood outside {v2,v5}, namely {v1,v3,v4}. Hence {v2,v5} is a homogeneous clique. Let Q be the five-vertex graph on {x,v1,v3,v4,v6} with edge set {xv1,xv3,xv4,v1v3,v1v6,v4v6}. Then H is obtained from Q by substituting K2 for the vertex x. By [L2], both Q and K2 have the Erdős-Hajnal property, so [L3] gives the Erdős-Hajnal property for H.

1.3A1L4algebra

Form H+ from [A1] by adjoining a new vertex v adjacent to v1 and v2, and delete v3. On the remaining six vertices {v,v1,v2,v4,v5,v6} the edge set is {vv1,vv2,v1v2,v1v5,v1v6,v2v4,v2v5,v4v5,v4v6}. Under the relabelling x1=v, x2=v6, x3=v5, y=v4, z=v2, and w=v1, the six missing edges are exactly x1x2, x1x3, x2x3, x1y, x2z, and yw, which are precisely the Bird edges. Therefore H+−v3 is co-Bird, so H+ is not co-Bird-free.

2.1L1step 1.1step 1.2step 1.3∎

Step 1.2 shows that {H}∪{co-Bird} has the Erdős-Hajnal property, and step 1.3 shows that H+ is not co-Bird-free. Therefore [L1] applies to the singleton family {Bird} and proves that Bird is wonderful. Together with step 1.1, this proves the statement.

Depends on

Used by

Dependency tree · two levels

36 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