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.
Modular partitions and the quotient graph they define
Definition
Let be a finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets). A modular partition of is a set of nonempty modules of (Modules of a graph, and the trivial modules) that are pairwise disjoint and whose union is . Its members are its parts. Since the parts are nonempty and pairwise disjoint subsets of the finite set , there are finitely many of them (The cardinality of a finite set).
The quotient graph has vertex set , and for distinct parts ,
(Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).
Why this is a definition and not a wish. Two distinct parts are disjoint nonempty modules, so the pair they form is complete or anticomplete and not both (Two disjoint nonempty modules form a complete or an anticomplete pair). The displayed condition is therefore a genuine dichotomy: for each unordered pair of distinct parts exactly one of "complete" and "anticomplete" holds, and is a well-defined set of two-element subsets of . Hence is a finite simple graph.
The partition of into singletons is modular, and its quotient is itself up to the renaming ; when the partition is modular too, and its quotient is the one-vertex graph. The induced subgraphs on the parts (Subgraphs, induced subgraphs and spanning subgraphs) carry the information the quotient discards.
Depends on
- Modules of a graph, and the trivial modules
- Two disjoint nonempty modules form a complete or an anticomplete pair
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Subgraphs, induced subgraphs and spanning subgraphs
- Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs
- The cardinality $\lvert A\rvert$ of a finite set
Used by
- 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
- Maximal proper modules need not be disjoint when the graph or its complement is disconnected Counterexample
- The modular decomposition of a five-cycle with each vertex blown up into an edgeless graph Example
- 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 Lemma
- The quotient by a modular partition is isomorphic to the subgraph induced by any set meeting each part exactly once Lemma
- A graph is recovered from any modular partition by the induced subgraphs on the parts together with the quotient graph 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
16 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.3 (standard reference, not scraped)
- T. Harju, Lecture Notes on Combinatorial Structures in Graph Theory, sec. 3 (standard reference, not scraped)