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.
All E neighbourhood patterns under a complete nonedge pair
Example
Let be a finite simple co-Bird-free graph. Let be distinct vertices outside the indicated induced subgraph, with , and , and with complete to that subgraph. Let induce , with edges exactly . The 64 subsets , encoded by six adjacency bits, reduce to the empty and full subsets after imposing the two local obstruction tests. The table gives a witness for each of the 62 mixed subsets.
Facts & Assumptions
The edge-plus-isolate co-Bird obstruction supplies the following statement: Let be a finite simple co-Bird-free graph. Let be distinct vertices outside the indicated induced subgraph, with , and , and with complete to that subgraph. If induces just the edge , then cannot be mixed on and nonadjacent to .
The path-plus-isolate co-Bird obstruction supplies the following statement: Let be a finite simple co-Bird-free graph. Let be distinct vertices outside the indicated induced subgraph, with , and , and with complete to that subgraph. If induces the path and isolated vertex , then cannot be adjacent to and two consecutive vertices of the path and nonadjacent to the remaining endpoint.
Complete nonedge pairs force purity on induced E graphs supplies the following statement: Let be a finite simple co-Bird-free graph. Let be distinct vertices outside the indicated induced subgraph, with , and , and with complete to that subgraph. Let induce , with edges exactly . Then is pure to . In particular, in an -comb with an outside vertex complete to all blocks and anticomplete to all teeth, each , , is pure to every induced in .
The -graph and co- supplies the following definition: The -graph is the graph on vertices with edge set Thus is a five-vertex path and is a leaf attached to its middle vertex . The co- graph is the complement of this graph.
Verification
Given: The graph, vertices, sets and hypotheses in the example.
For any row of type I the five-edge list verifies an induced edge-plus-isolate with adjacency bits ; type II verifies an induced path-plus-isolate with bits . The respective obstruction forbids that row under the common complete-nonedge-pair hypotheses. All witness vertices lie in , so the required outside vertices remain outside.
The symbolic proof of induced- purity also groups these possibilities exhaustively: constant adjacency on the five-vertex path forces the matching value at ; mixing on either terminal edge is impossible; equal terminal-pair values force the middle value; opposite terminal-pair values give the final contradiction. Consequently every mixed six-bit assignment is excluded without relying on a smoke test. The table supplies one direct witness for each such assignment.
For mask , type I lacks its required neighbour and type II lacks three required neighbours. For mask , type I lacks its two required nonneighbours and type II lacks its required nonneighbour. Hence neither local test rejects either constant mask, and exactly these two of the 64 subsets survive the tests. This is a statement about the two tests, not a sufficiency assertion for freeness of an arbitrary ambient graph.
Adjacency table
Each mask is in order . Type I lists : edge , isolate , adjacency bits . Type II lists : path , isolate , bits . Thus every row is an explicit prohibited induced configuration, checkable against the five-edge list.
| Mask | Type | Ordered witness |
|---|---|---|
| 1 | I | |
| 2 | I | |
| 3 | I | |
| 4 | I | |
| 5 | I | |
| 6 | I | |
| 7 | I | |
| 8 | I | |
| 9 | I | |
| 10 | I | |
| 11 | I | |
| 12 | I | |
| 13 | I | |
| 14 | I | |
| 15 | I | |
| 16 | I | |
| 17 | I | |
| 18 | I | |
| 19 | I | |
| 20 | I | |
| 21 | I | |
| 22 | I | |
| 23 | I | |
| 24 | I | |
| 25 | I | |
| 26 | I | |
| 27 | II | |
| 28 | I | |
| 29 | I | |
| 30 | I | |
| 31 | II | |
| 32 | I | |
| 33 | I | |
| 34 | I | |
| 35 | I | |
| 36 | I | |
| 37 | I | |
| 38 | I | |
| 39 | II | |
| 40 | I | |
| 41 | I | |
| 42 | I | |
| 43 | I | |
| 44 | I | |
| 45 | I | |
| 46 | I | |
| 47 | II | |
| 48 | I | |
| 49 | I | |
| 50 | I | |
| 51 | II | |
| 52 | I | |
| 53 | I | |
| 54 | I | |
| 55 | II | |
| 56 | I | |
| 57 | II | |
| 58 | I | |
| 59 | II | |
| 60 | II | |
| 61 | II | |
| 62 | II |
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
9 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
- Huang–Ju–Zhou, Erdős–Hajnal beyond the five-vertex path, §6.2, Claim 6.5.2, explicit finite expansion (standard reference, not scraped)