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.
Every composite bull-free graph has a nontrivial module
Statement
Every composite bull-free graph has a nontrivial module.
Facts & Assumptions
Given: A composite bull-free graph .
In a composite bull-free graph there is an odd hole or odd antihole with one outside vertex complete to and another outside vertex anticomplete to (Basic and composite bull-free graphs).
A set is split when every mixed outside vertex has one of the two witnesses from the definition: either a three-vertex path, or a three-vertex configuration with exactly one edge among the three vertices (A split set in a bull-free graph).
A split set with both a complete and an anticomplete outside witness yields a nontrivial module (A split set with both a complete and an anticomplete outside vertex yields a nontrivial module).
Bull-freeness is complement-invariant (A graph is bull-free if and only if its complement is bull-free).
Proof
By [F1] and [L2], after passing to the complement if needed we may assume that is an odd hole with vertices in cyclic order, together with a vertex complete to and a vertex anticomplete to . To apply [L1], it is enough to show that is split.
Let be neither complete nor anticomplete to . By cyclic symmetry, assume is adjacent to and nonadjacent to . If is adjacent to , then the path -- gives the first split alternative from [F2]. So assume is nonadjacent to . If is also nonadjacent to , then while , so the triple gives the second split alternative. Otherwise is adjacent to , and then while , so the triple gives the second split alternative. Hence every mixed outside vertex satisfies [F2], so is split.
Step 1.2 shows that the odd hole is a split set, and step 1.1 supplies a complete and an anticomplete outside vertex for it. Therefore [L1] gives a nontrivial module in .
Depends on
Used by
- Every prime bull-free graph is basic Corollary
- Every bull-free graph is 2-narrow Theorem
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
- Maria Chudnovsky and Shmuel Safra, The Erdős-Hajnal conjecture for bull-free graphs, Theorem 1.4 (standard reference, not scraped)