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 a complete outside vertex has tightly constrained neighbors
Statement
Let be a basic bull-free graph, let be an odd hole in with , let be complete to , and let be nonadjacent to . Then either:
- is complete to ; or
- and has at least three neighbors in .
Facts & Assumptions
Given: A basic bull-free graph , an odd hole with vertices in cyclic order and , a vertex complete to , and a vertex nonadjacent to .
A basic bull-free graph is a bull-free graph that 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 anticomplete to : otherwise the odd hole would have the complete outside vertex and the anticomplete outside vertex , making composite and contradicting [F1]. Assume neither outcome of the Statement holds. By cyclic symmetry choose adjacent to . Suppose that is adjacent to . Since is not a bull, is adjacent to at least one of ; after reversing and shifting the cyclic labels in the second case, we may assume that is adjacent to . Since neither outcome holds, and is not complete to . Since is not a bull, is adjacent to at least one of ; reflecting the cyclic labels through if necessary, we may assume that is adjacent to . Let be minimal with nonadjacent to . Minimality makes adjacent to , while is adjacent to . If , then is a bull, so . But then is a bull, a contradiction. Thus is not adjacent to ; applying the same argument to any putative consecutive pair shows that has no two consecutive neighbors on .
Since is adjacent to but to no consecutive pair on , the vertices with would induce a bull unless were adjacent to every such . Reflecting the cycle through gives the same conclusion for . In particular is adjacent to both and , a consecutive pair, contradicting step 1.1. Therefore our assumption that neither outcome holds was impossible.
One of the two stated outcomes must hold.
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.1 (standard reference, not scraped)