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.
For a vertex in a basic bull-free graph, either its neighborhood or its antineighborhood is perfect
Statement
Let be a basic bull-free graph and let . Let be the set of neighbors of , and let be the set of nonneighbors of . Then at least one of the induced graphs and is perfect.
Facts & Assumptions
Given: A basic bull-free graph , a vertex , its neighborhood , and its antineighborhood .
In a basic bull-free graph, a vertex outside a hole that is nonadjacent to a complete outside witness is either complete to the hole or is in the exceptional five-hole case; in particular it has at least neighbors on that hole (In a basic bull-free graph, an odd hole with a complete outside vertex has tightly constrained neighbors).
In a basic bull-free graph, a vertex adjacent to an anticomplete outside witness has at least nonneighbors on the hole (In a basic bull-free graph, an odd hole with an anticomplete outside vertex forbids consecutive neighbors).
A finite graph is perfect exactly when it contains no odd hole and no odd antihole (Strong Perfect Graph Theorem ‡).
Bull-freeness, and therefore basicness, is preserved by complementation (A graph is bull-free if and only if its complement is bull-free, Basic and composite bull-free graphs).
Proof
Suppose neither nor is perfect. First they cannot both contain odd holes. Indeed, let and be odd holes of lengths and . Every vertex of is nonadjacent to , while is complete to , so [L1] gives each vertex of at least neighbors in . Thus there are at least cross edges. On the other hand every vertex of is adjacent to , while is anticomplete to , so [L2] gives each vertex of at least nonneighbors in . Hence there are at least cross nonedges. Since there are only cross pairs altogether, we obtain , equivalently , impossible because make the left-hand side at least .
By [L4], the same argument in shows that and cannot both contain odd antiholes. If contained an odd hole, then step 1.1 would force to contain no odd hole, so [L3] would give an odd antihole in . Because a -antihole is also a -hole, step 1.1 excludes the case , and the same complement argument excludes ; hence both have length at least . Now every vertex of is nonadjacent to , so [L1] applied to the odd hole with complete outside vertex makes each vertex of complete to . Applying the same lemma in reverses the roles of hole and antihole and shows that each vertex of is anticomplete to , contradiction. Therefore has no odd hole, and by [L3] it must contain an odd antihole. Symmetrically, contains an odd hole.
Take the odd antihole and the odd hole from step 2.1, with lengths and . By [L2], each vertex of has at least nonneighbors in . Applying [L2] in the complement graph, where becomes an odd hole and is anticomplete to it, shows that each vertex of has at least neighbors in . Hence the number of cross nonedges is at least and the number of cross edges is at least . Their sum is at least , impossible. This contradiction proves that at least one of and is perfect.
Depends on
- A perfect graph
- In a basic bull-free graph, an odd hole with a complete outside vertex has tightly constrained neighbors
- In a basic bull-free graph, an odd hole with an anticomplete outside vertex forbids consecutive neighbors
- Strong Perfect Graph Theorem
- A graph is bull-free if and only if its complement is bull-free
- Basic and composite bull-free graphs
Used by
Dependency tree · two levels
13 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 4.3 (standard reference, not scraped)