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.
Purity propagates through E overlap chains
Statement
Fix a comb block and an overlap class . If is pure to every induced contained in , then is pure to . In particular, any pure to every induced in is pure to every overlap class.
Facts & Assumptions
E overlap chains inside one comb block supplies the following definition: Fix a block of a finite graph comb (def-comb-in-a-graph). Let consist of all six-vertex subsets of inducing the graph in def-e-graph-and-co-e-graph. Put and . For , define if there exist and vertices in such that each consecutive pair is contained in some . A zero-length chain is allowed. If is empty then and the relation are empty. We call this the overlap chain relation.
Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs supplies the following definition: Let be a finite simple graph and let be disjoint. An edge between and is an edge with and . The pair is: - complete when every is adjacent to every ; - anticomplete when no is adjacent to any ; - pure when it is complete or anticomplete; and - mixed when it is neither complete nor anticomplete. Adjacency is the symmetric edge relation of (def-finite-simple-graph, def-graph-adjacency-incidence-neighbourhood-and-degree). If or , the pair is both complete and anticomplete, hence pure and not mixed.
Proof
Given: The graph, vertices, sets and hypotheses in the statement.
Every induced meeting lies in , because any two of its vertices have a length-one overlap chain. On each such six-vertex copy, purity means that all six adjacency values to are equal. If two copies share a vertex, their values coincide at that vertex and therefore agree everywhere.
For any two vertices of a class choose a defining finite chain. Each consecutive pair has equal adjacency to because it lies in a common copy. Equality propagates along the chain, including a zero-length chain. Thus every vertex in the class has the same adjacency value. This is exactly purity. If there are no classes the assertion is vacuous.
Depends on
Used by
Dependency tree · two levels
6 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–Zhou, Erdős–Hajnal beyond the five-vertex path, §6.2, Claim 6.5.3, overlap propagation (standard reference, not scraped)