Alphabeta Math
CorollaryStatement: Literature-sourcedProof: AI-generatedverified 2026-09-24 (gpt-6-sol)
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 bull graph has the Erdős-Hajnal property

Statement

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

Facts & Assumptions

Given: The bull B on {x1,x2,x3,y,z} with edges x1x2,x2x3,x1x3,x1y,x2z (The bull graph).

[L1]

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

[L2]

For a single graph, the Erdős-Hajnal property is equivalent to virality of its singleton family (For a single graph, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent).

[L3]

A viral leaf-deleted singleton and a viral co-leaf-deleted singleton make the original singleton viral (Deleting a leaf and a co-leaf preserves virality of a finite forbidden family).

Proof

technique · direct
1.1givenalgebra

The vertex y is a leaf of B, with sole neighbor x1. The vertex x1 has degree 3=∣B∣−2, so it is a co-leaf. Deleting y leaves a triangle x1x2x3 with pendant vertex z at x2; deleting x1 leaves the path x3−x2−z and isolated vertex y. Both resulting graphs have four vertices.

2.1step 1.1L1L2L3∎

By [L1] the two deleted graphs have the Erdős-Hajnal property, so [L2] makes their singleton families viral. Applying [L3] to {B} with leaf y and co-leaf x1 proves that {B} is viral. A second application of [L2] proves the statement.

Depends on

Used by

Dependency tree · two levels

23 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