ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-09-01

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 four-tooth comb with an external complete vertex

Example

Let $a_{1}, a_{2}, a_{3}, a_{4}, v$ be five vertices and let $B_{i} = {b_{i}}$ for $i = 1, 2, 3, 4$ . If the only edges among these nine vertices are $a_{i} b_{i}$ for $1 \leq i \leq 4$ and $v b_{i}$ for $1 \leq i \leq 4$ , then $((a_{i}, B_{i}) : i \in [4])$ is a four-tooth comb and the outside vertex $v$ is complete to the tooth blocks and anticomplete to the teeth.

Facts & Assumptions

Given: The nine labelled vertices above with exactly the displayed edges.

[L1]

A comb is given by distinct teeth $a_{i}$ , disjoint blocks $B_{i}$ , each tooth complete to its own block and anticomplete to the other blocks (Combs in a graph).

Verification

technique · direct finite check

1.1

For each $i \in [4]$ , the tooth $a_{i}$ is adjacent to the unique vertex of its own block $B_{i} = {b_{i}}$ and to no vertex of the other three blocks. Therefore $((a_{i}, B_{i}) : i \in [4])$ satisfies [L1].

L1given

2.1

By construction the vertex $v$ is adjacent to every $b_{i}$ and to none of the teeth $a_{i}$ . So $v$ has exactly the extra adjacency pattern singled out in the comb outcome of the lemma.

step 1.1given∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

10 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, Lemma 2.10 (standard reference, not scraped)