Alphabeta Math
PropositionStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16
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.

If H is an induced subgraph of H′ and H′ has the Erdős–Hajnal property, then H has it with every constant of H′

Statement

Suppose H has an induced embedding into H′. Then every Erdős–Hajnal constant for H′ is one for H. Consequently, if H′ has the Erdős–Hajnal property, then so does H.

Facts & Assumptions

Given: Finite graphs H,H′ and an induced embedding H↪indH′.

[L1]

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

[L2]

A graph is F-free when it has no induced embedding of F (H-free and F-free graphs under the induced-subgraph convention).

[L3]

Induced embeddings compose, so induced-subgraph containment is transitive (Induced embeddings compose, and the induced-subgraph relation is transitive up to isomorphism).

[L4]

Every fixed-pattern-free graph class is hereditary (Every class defined by forbidden induced subgraphs is hereditary).

Proof

technique · direct
1.1

If G is H-free, then it is H′-free: an induced embedding H′↪indG would compose with the Given embedding to put H inducedly in G.

givenL2L3
2.1

Hence the H-free class is a subclass of the H′-free class, and both are hereditary by [L4].

step 1.1L4
3.1

Applying [L1] proves that every constant of H′ is a constant of H, and therefore proves the property implication.

step 2.1L1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 20 results over 10 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources