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.
The five-cycle is 2-narrow but not 1-narrow
Example
The cycle graph is two-narrow but not one-narrow.
Facts & Assumptions
Given: The cycle graph .
If every vertex deletion of a graph with at least three vertices is perfect, then the graph is two-narrow (Perfect vertex deletions imply 2-narrowness).
The graph is not perfect (The five-cycle is bull-free but not perfect).
A graph is one-narrow when every good function has total weight at most (An -narrow graph).
A good function is a nonnegative weighting whose total on every perfect induced subgraph is at most (A good function on a graph).
The graph is the five-vertex cycle (Empty and complete graphs, complete bipartite graphs, and the convention that and have vertices). A graph is perfect when each of its induced subgraphs has chromatic number equal to clique number (A perfect graph).
Verification
Deleting any vertex of leaves a four-vertex path. Every induced subgraph of that path is a disjoint union of paths. If it has an edge, alternating colours on each path give chromatic number at most , and the edge gives clique number at least , so both numbers are ; if it is nonempty and has no edge, both are ; and if it is empty, both are . Thus every vertex deletion is perfect by [F3]. Since has five vertices, [L1] proves that is two-narrow.
Define for every vertex of . Every proper induced subgraph lies in some vertex deletion, so it is perfect by step 1.1. Since [L2] says the whole is not perfect, every perfect induced subgraph is proper and has at most four vertices. Thus [F2] makes a good function: its total on each perfect induced subgraph is at most . But , so [F1] shows that is not one-narrow.
Thus is two-narrow by step 1.1 but not one-narrow by step 2.1.
Depends on
Used by
- FALSE: every 2-narrow graph is 1-narrow False statement
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 and Shmuel Safra, The Erdős-Hajnal conjecture for bull-free graphs, Sections 1-2 (standard reference, not scraped)