LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-31

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 hatted-five-cycle-free rooted stable-tooth comb yields a large pure blockade of components

Statement

Let $(v, ((a_{i}, B_{i}) : 1 \leq i \leq t))$ be a rooted stable-tooth comb in a graph $G$ . Assume that $G$ contains no induced hatted five-cycle. Then for each $i \in [t]$ there is a connected component $D_{i}$ of $G [B_{i}]$ such that the blockade $(D_{1}, \dots, D_{t})$ is pure.

Facts & Assumptions

Given: A rooted stable-tooth comb $(v, ((a_{i}, B_{i}) : 1 \leq i \leq t))$ in a graph with no induced hatted five-cycle.

[L1]

In a rooted stable-tooth comb, each tooth $a_{i}$ is complete to $B_{i}$ , anticomplete to every other block, the teeth are stable, and the root $v$ is complete to the teeth and anticomplete to all blocks (A rooted stable-tooth comb).

Proof

technique · direct

1.1

For each $i$ , choose a connected component $D_{i}$ of $G [B_{i}]$ . Since $D_{i} \subseteq B_{i}$ and the comb blocks are pairwise disjoint, the sequence $(D_{1}, \dots, D_{t})$ is again a blockade after deleting any empty choices, and we may choose every $D_{i}$ nonempty.

L1choose

2.1

Fix distinct indices $i, j$ . Suppose some vertex $u \in D_{j}$ is mixed on $D_{i}$ . Since $G [D_{i}]$ is connected, there is an edge $x y$ of $G [D_{i}]$ such that $u$ is adjacent to $x$ and not to $y$ . By [L1], among the six vertices $v, a_{i}, a_{j}, x, y, u$ the edges $v a_{i}, v a_{j}, a_{i} x, a_{i} y, u x, u a_{j}, x y$ are present, while $v u, v y, x a_{j}, y a_{j}, u a_{i}, u y, a_{i} a_{j}$ are absent. Hence $v - a_{j} - u - x - a_{i} - v$ is a five-cycle, and $y$ is adjacent exactly to the adjacent cycle vertices $x, a_{i}$ . Therefore these six vertices induce a hatted five-cycle, contradicting the hypothesis. So no vertex of $D_{j}$ is mixed on $D_{i}$ ; swapping $i$ and $j$ gives the converse direction, and therefore each pair $(D_{i}, D_{j})$ is either complete or anticomplete.

step 1.1L1choose

3.1

Since every pair of distinct chosen components is pure, $(D_{1}, \dots, D_{t})$ is a pure blockade.

step 2.1∎

Depends on

Used by

The hatted five-cycle and its complement have the Erdős-Hajnal property Theorem

Dependency tree · two levels

16 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

Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdős-Hajnal for graphs with no 5-hole, proof of Theorem 8.1 (standard reference, not scraped)