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.
A split set with both a complete and an anticomplete outside vertex yields a nontrivial module
Statement
Let be a bull-free graph and let be a split set. Suppose there are vertices such that is complete to and is anticomplete to . Then has a nontrivial module.
Facts & Assumptions
Given: A bull-free graph , a split set , and vertices with complete to and anticomplete to .
A set is split exactly when every outside vertex mixed on it has one of the two witnesses from the definition: either an induced 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 module is a vertex set to which every outside vertex is complete or anticomplete (Modules of a graph, and the trivial modules).
Bull-freeness is preserved by complementation (A graph is bull-free if and only if its complement is bull-free).
Proof
First claim: if is neither complete nor anticomplete to , then either is adjacent to and is adjacent to , or is nonadjacent to and is nonadjacent to . Indeed, let be the neighbors of in and ; both are nonempty. By [F1], either there are and with -- an induced path, or there are and with while . In the first case bull-freeness rules out both - and simultaneously, because otherwise and then would be bulls. In the second case bull-freeness similarly rules out both and -, because otherwise and then would be bulls.
Let be the set of vertices complete to , let be the set of vertices anticomplete to , and let . Either every vertex of has a neighbor in , or every vertex of has a nonneighbor in : otherwise a vertex of anticomplete to and a vertex of complete to would contradict each other. Replacing by if necessary preserves bull-freeness, splitness, and modules by [L1], [F1], and [F2], so assume that every vertex of has a neighbor in . Step 1.1 then makes complete to . Let be the set of vertices of lying on an induced path --- with and all . We prove by induction on that is complete to . For , if were a nonedge for some , step 1.1 applied to would force to be a nonedge, a contradiction. For , put and assume the result through . Choose nonadjacent to when , which is possible because is mixed on ; for any works because . If some were nonadjacent to , then would be a bull: form its triangle, while and are pendant at and . Hence is complete to .
Put . Every vertex of is anticomplete to : it is anticomplete to by definition, and any path from it to through has a shortest, hence induced, subpath that would put it in . Every vertex of is complete to by step 2.1 and the definition of . Thus every outside vertex is complete or anticomplete to , so is a module by [F2]. The set is nontrivial because and , while , so .
Depends on
Used by
Dependency tree · two levels
15 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 3.1 (standard reference, not scraped)