Alphabeta MathHow 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.
The right six-vertex prime -graph is the complement of the left one, and is prime
Example
The right six-vertex prime -graph is the complement of the left one, and is prime. On the common labels , its edge set is .
Facts & Assumptions
Given: The left and right six-vertex prime -graphs on the common label set .
The right graph is defined as the complement of the left graph (The right six-vertex prime -graph, The left six-vertex prime -graph, Graph isomorphisms, automorphisms and graph complements).
The left six-vertex prime -graph is prime (The left six-vertex prime -graph: primeness and leaf/co-leaf deletions).
A graph is prime exactly when it has no nontrivial module (Prime graphs: those whose only modules are the trivial ones, Modules of a graph, and the trivial modules).
A vertex set is a module of a graph if and only if it is a module of the complement, because outside vertices swap complete and anticomplete behaviour.
Verification
The left graph has edges . The remaining eight of the fifteen unordered vertex pairs are exactly , the right graph's edges. Thus the identity on the common label set is an isomorphism from the right graph to the complement of the left graph.
Since the left graph is prime by [L2], [L3] says it has no nontrivial module. By [F1], its complement also has no nontrivial module. Therefore the right graph is prime by [L3].
Thus the right six-vertex prime -graph is the complement of the left one and is prime.
Remarks
For comparison with Nguyen–Scott–Seymour Figure 1, label the right drawing's top row and bottom row . The bijection sends the eight edges above to , exactly the edges of that drawing. The former labels and complement-of-net interpretation are superseded; the complement argument now applies to the corrected seven-edge left graph.
Depends on
- The right six-vertex prime $\mathcal H$-graph
- The left six-vertex prime $\mathcal H$-graph
- Prime graphs: those whose only modules are the trivial ones
- Modules of a graph, and the trivial modules
- Graph isomorphisms, automorphisms and graph complements
- The left six-vertex prime $\mathcal H$-graph: primeness and leaf/co-leaf deletions
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
14 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
- Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. IV. New graphs with the Erdős-Hajnal property, Figure 1 (standard reference, not scraped)
- Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Figure 2 (standard reference, not scraped)