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.
Prime graphs: those whose only modules are the trivial ones
Definition
A finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets) is prime when every module of is trivial, that is, when the only modules of are , the singletons and (Modules of a graph, and the trivial modules). Equivalently, is prime when it has no module with and (The cardinality of a finite set).
Under this convention the null graph, every graph on one vertex and every graph on two vertices is prime, since such a graph has no vertex set at all whose cardinality lies between and . Which small graphs a source counts as prime is not uniform in the literature, and the alternatives are recorded in Which small graphs count as prime on this page.
Depends on
Used by
- Every graph has the Erdős–Hajnal property if and only if every prime graph does Corollary
- In a connected and anticonnected graph, a modular partition with at least two parts whose quotient is prime consists of the maximal proper modules Corollary
- The prime quotient produced by the modular decomposition of a connected and anticonnected graph has at least four vertices Corollary
- An induced subgraph of a prime graph need not be prime Counterexample
- Maximal proper modules need not be disjoint when the graph or its complement is disconnected Counterexample
- Every vertex set is a module of a complete graph and of an edgeless graph Example
- Pₙ is prime for every n≥4 Example
- The five-cycle is prime Example
- The four-vertex path has only trivial modules Example
- Up to isomorphism the four-vertex path is the only prime graph on four vertices Example
- Every graph with at least four vertices has a nontrivial module False statement
- No graph on exactly three vertices is prime Lemma
- Which small graphs count as prime on this page Remark
- A graph with at least two vertices is prime exactly when it is not obtained by substituting one graph on at least two vertices for a vertex of another graph on at least two vertices Theorem
- Gallai's modular decomposition theorem: a graph on at least two vertices is disconnected, or has a disconnected complement, or has a modular partition into its maximal proper modules whose quotient is prime Theorem
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
- M. Habib and C. Paul, A Survey on Algorithmic Aspects of Modular Decomposition, sec. 2.4 (standard reference, not scraped)
- T. Harju, Lecture Notes on Combinatorial Structures in Graph Theory, sec. 5 (standard reference, not scraped)