TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-07

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.

A special-vertex comb in a co- $E$ -free graph admits the ${H_{5}, c o - E}$ structural partition

Statement

Let $G$ be co- $E$ -free and let it contain an $(ℓ, w)$ -comb $((a_{i}, B_{i}) : i \in [ℓ])$ and an outside vertex $v$ complete to all blocks and anticomplete to all teeth. For every $i$ , there is a partition $B_{i} = X_{i} \dot{\cup} Y_{i}$ such that $Y_{i}$ is ${H_{5}, c o - E}$ -free, and $X_{i}$ has a nonempty-block pure blockade partition whose pattern is ${H_{5}, c o - E}$ -free and whose every block is pure to every vertex of $⋃_{k \neq i} B_{k}$ .

Facts & Assumptions

Given: The co- $E$ -free special-vertex comb of the Statement.

[F1]

The terminal overlap quotient is pure and has ${H_{5}, c o - E}$ -free pattern (Iterated mixed quotients of an $H_{5}$ -overlap blockade terminate at a pure blockade, The pattern of the terminal $H_{5}$ -overlap quotient is ${H_{5}, c o - E}$ -free).

[F2]

Every external comb-block vertex is pure to every terminal overlap quotient block (In a special-vertex comb of a co- $E$ -free graph, vertices in other comb blocks remain pure to every $H_{5}$ -overlap quotient block).

[F3]

A singleton sequence is a pure blockade with one-vertex pattern, and induced subgraphs of a co- $E$ -free graph are co- $E$ -free (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs, $H$ -free and $F$ -free graphs under the induced-subgraph convention).

Proof

technique · cases

1.1

Fix $i$ . Let $X_{i}^{0}$ be the vertices of $B_{i}$ contained in an induced $H_{5}$ , and put $Y_{i} = B_{i} ∖ X_{i}^{0}$ . Then $Y_{i}$ is $H_{5}$ -free by definition and co- $E$ -free as an induced subgraph, hence it is ${H_{5}, c o - E}$ -free.

1.2

Assume-case nonempty: if $X_{i}^{0} \neq \emptyset$ , set $X_{i} = X_{i}^{0}$ and take its terminal overlap quotient as the partition. Its pure-blockade and pattern clauses are [F1], and its cross-block purity clause is [F2].

F1F2assume-case nonempty

1.3

Assume-case empty: if $X_{i}^{0} = \emptyset$ , choose $x_{i} \in B_{i}$ , set $X_{i} = {x_{i}}$ and $Y_{i} = B_{i} ∖ {x_{i}}$ . The singleton blockade on $X_{i}$ is pure, its pattern has one vertex and is forbidden-family-free, and every outside vertex is pure to it; $Y_{i}$ is $H_{5}$ -free because $B_{i}$ was.

F3chooseassume-case empty

2.1

The two cases produce the required partition for this arbitrary $i$ , and therefore for every comb block.

step 1.1step 1.2step 1.3cases-exhaustive∎

Depends on

Used by

The singleton family {E} has property (*) Corollary
A bipartite four-tooth comb has the co-E structural partition Example

Dependency tree · two levels

31 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

Huang, Ju, and Zhou, Erdős-Hajnal beyond the five-vertex path, Lemma 6.4 (standard reference, not scraped)

A special-vertex comb in a co-EE-free graph admits the {H5,co-E}{H5​,co-E} structural partition