CorollaryStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)verified 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.

Deleting a leaf and a co-leaf preserves the Erdős-Hajnal property of a finite forbidden family

Statement

Let $F$ be a finite family of finite graphs. Let $H_{1} \in F$ have a leaf $v$ , and let $H_{2} \in F$ have a co-leaf $w$ . Write $H_{1}^{'} : = H_{1} ∖ {v}$ and $H_{2}^{'} : = H_{2} ∖ {w}$ . If

$F_{1} : = {H_{1}^{'}} \cup (F ∖ {H_{1}})$

and

$F_{2} : = {H_{2}^{'}} \cup (F ∖ {H_{2}})$

have the Erdős-Hajnal property, then $F$ has the Erdős-Hajnal property.

Facts & Assumptions

Given: A finite family $F$ of finite graphs, a member $H_{1} \in F$ with leaf $v$ , and a member $H_{2} \in F$ with co-leaf $w$ .

[L1]

If the two modified families are viral, then $F$ is viral (Deleting a leaf and a co-leaf preserves virality of a finite forbidden family).

[L2]

For finite families, the Erdős-Hajnal property is equivalent to virality (For a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent).

Proof

technique · direct

1.1

By [L2], the hypothesis that $F_{1}$ and $F_{2}$ have the Erdős-Hajnal property implies that both families are viral.

2.1

Applying [L1] gives that $F$ is viral.

step 1.1L1

3.1

A second application of [L2] turns virality of $F$ back into the Erdős-Hajnal property.

step 2.1L2∎

Depends on

Used by

Dependency tree · two levels

15 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

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Corollary 1.8 (standard reference, not scraped)