Alphabeta Math
ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-09-26 (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 leaf/co-leaf corollary recovers the P5 case from the P4 case

Example

Graphs with no induced P5 and no induced P5‾ have the Erdős-Hajnal property, and this follows from the P4 case via the leaf/co-leaf corollary.

Facts & Assumptions

Given: The family F:={P5,P5‾}.

[L1]

If deleting a leaf from one member of a finite forbidden family and a co-leaf from another member produces two smaller families with the Erdős-Hajnal property, then the original family has the Erdős-Hajnal property (Deleting a leaf and a co-leaf preserves the Erdős-Hajnal property of a finite forbidden family).

[L2]

The Erdős-Hajnal property passes from a hereditary class to each hereditary subclass (The Erdős–Hajnal property and each of its constants pass to hereditary subclasses).

[L3]

For every forest H, graphs with no induced H and no induced H‾ have the Erdős-Hajnal property (For every forest H, graphs excluding H and H‾ have the Erdős-Hajnal property).

[L4]

A co-leaf of a graph is a vertex that is a leaf of the complement, equivalently a vertex of degree ∣V(G)∣−2 (Co-leaves of a finite graph).

[L5]

The complement contains exactly the nonedges of the original graph (Graph isomorphisms, automorphisms and graph complements).

[L6]

Every class defined by forbidden induced subgraphs is hereditary (Every class defined by forbidden induced subgraphs is hereditary).

Verification

technique · direct
1.1

The graph P5 has leaf 1. By [L5], the complement P5‾ has edges 13, 14, 15, 24, 25, and 35, so vertex 1 has degree 3=5−2. By [L4], vertex 1 is therefore a co-leaf of P5‾. Delete that leaf of P5 and that co-leaf of P5‾. The resulting smaller families are F1={P4,P5‾}andF2={P5,P4‾}. From the path edges 12, 23, and 34, [L5] gives complement edges 13, 14, and 24, which form the path 3-1-4-2. Thus P4‾≅P4.

givenL4L5algebra
2.1

The path P4 is a forest, and step 1.1 shows that P4‾≅P4. Therefore [L3] applied with H=P4 gives the Erdős-Hajnal property for the hereditary class of P4-free graphs. By [L6], the classes defined by forbidding {P4,P5‾} and {P5,P4‾} are hereditary. Each is a subclass of the P4-free class, using step 1.1 for the second family. Hence [L2] gives the Erdős-Hajnal property for both F1 and F2.

step 1.1L2L3L6
3.1

Applying [L1] to the family F={P5,P5‾} and the two smaller families from steps 1.1 and 2.1 yields the Erdős-Hajnal property for graphs with no induced P5 and no induced P5‾.

step 1.1step 2.1L1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

22 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.