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.
In a basic bull-free graph, an odd hole with an anticomplete outside vertex forbids consecutive neighbors
Statement
Let be a basic bull-free graph, let be an odd hole in with , let be anticomplete to , and let be adjacent to . Then has no two consecutive neighbors on . In particular, has at least nonneighbors in .
Facts & Assumptions
Given: A basic bull-free graph , an odd hole with vertices in cyclic order and , a vertex anticomplete to , and a vertex adjacent to .
A basic bull-free graph is not composite (Basic and composite bull-free graphs).
A hole is an induced cycle (Holes, antiholes, and odd holes).
Proof
Because is basic, cannot be complete to : together with the anticomplete outside vertex , that would make the odd hole a composite witness, contrary to [F1]. So has a nonneighbor on . Suppose had two consecutive neighbors, say and . Let be minimal with nonadjacent to ; then , and minimality gives adjacent to and . Since is anticomplete to , the five vertices induce a bull, contradicting bull-freeness. Therefore has no two consecutive neighbors on .
On a cycle of length , any vertex subset with no two consecutive vertices has size at most . Step 1.1 therefore bounds the number of neighbors of on by , so the number of nonneighbors is at least .
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
- Maria Chudnovsky and Shmuel Safra, The Erdős-Hajnal conjecture for bull-free graphs, Lemma 4.2 (standard reference, not scraped)