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.
In a connected and anticonnected graph, a modular partition with at least two parts whose quotient is prime consists of the maximal proper modules
Statement
Let be a connected and anticonnected finite simple graph with , and let be a modular partition of with at least two parts whose quotient is prime. Then every part of is a maximal proper module , and is the partition of into its maximal proper modules. In particular has exactly one modular partition with at least two parts and a prime quotient, namely the one produced by 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.
Facts & Assumptions
Given: A connected and anticonnected finite simple graph with , and a modular partition of with at least two parts and prime.
A modular partition of is a set of nonempty, pairwise disjoint modules of whose union is ; the quotient has vertex set (Modular partitions and the quotient graph they define).
is a module of when the pair is pure for every , and is proper when (Modules of a graph, and the trivial modules).
A graph is prime when every module of it is trivial, the trivial modules being the empty set, the singletons and the whole vertex set (Prime graphs: those whose only modules are the trivial ones).
For a modular partition and , the set is a module of if and only if is a module of (For a modular partition, a set of parts is a module of the quotient exactly when the union of those parts is a module of the graph).
In a connected and anticonnected graph, the union of two proper modules that meet is again a proper module (In a connected and anticonnected graph, the union of two proper modules that meet is again a proper module).
In a connected and anticonnected graph with at least two vertices, each vertex lies in a largest proper module , any two of these are equal or disjoint, and they cover (In a connected and anticonnected graph with at least two vertices, each vertex lies in a largest proper module, and two such modules are equal or disjoint).
The maximal proper modules of such a graph form a modular partition with at least two parts whose quotient is prime (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).
Proof
Every part is a nonempty module of , and because has another part, which is nonempty and disjoint from ; so every part is a proper module.
Fix and , and let be the largest proper module of containing . Then by step 1.1 and the maximality in [L3].
Let and let . Both and are proper modules and they meet, so is a proper module by [L2]; it contains , so [L3] gives and hence .
Every vertex of lies in a part, and that part meets and so lies in ; with step 3.1 this gives .
By [L1] the set is therefore a module of , hence trivial by [F3]. It is not empty, since by step 2.1; and it is not all of , since that would give , contradicting properness. So is a singleton, and by step 2.1 its unique member is , whence .
So each part of equals for each of its vertices , and conversely each is the part containing by the same computation; hence is exactly the set of maximal proper modules, which by [L4] is a modular partition with at least two parts and a prime quotient, and no other modular partition of with at least two parts has a prime quotient.
Depends on
- Modular partitions and the quotient graph they define
- Prime graphs: those whose only modules are the trivial ones
- Modules of a graph, and the trivial modules
- For a modular partition, a set of parts is a module of the quotient exactly when the union of those parts is a module of the graph
- In a connected and anticonnected graph, the union of two proper modules that meet is again a proper module
- In a connected and anticonnected graph with at least two vertices, each vertex lies in a largest proper module, and two such modules are equal or disjoint
- 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
Used by
Dependency tree · two levels
27 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
- T. Harju, Lecture Notes on Combinatorial Structures in Graph Theory, secs. 3 and 4 (standard reference, not scraped)