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 with at least two vertices, each vertex lies in a largest proper module, and two such modules are equal or disjoint
Statement
Let be a connected and anticonnected finite simple graph with . For write for the set of proper modules of containing . Then has a member that contains every member of ; it is the largest proper module containing . Moreover, for either or ; and every vertex lies in , so the sets cover .
Facts & Assumptions
Given: A connected and anticonnected finite simple graph with , and a vertex .
is a module of when the pair is pure for every ; the singletons are modules, and is proper when (Modules of a graph, and the trivial modules).
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).
Every subset of a finite set is finite, has cardinality at most that of the set, and has that cardinality only if it is the whole set (A subset of a finite set is finite, with , and equality holds if and only if ).
Every nonempty subset of has a least element (The well-ordering principle).
The cardinality of a finite set is a natural number (The cardinality of a finite set).
Proof
The singleton is a module of , and because , so and is nonempty.
Every member of is a subset of the finite set , so its cardinality is a natural number at most .
The set is a nonempty subset of by steps 1.1 and 1.2, so it has a least element; a member attaining it has for every .
Let . Both and are proper modules containing , so they meet, and [L1] makes a proper module; it contains , so it lies in and step 2.1 gives .
Since and the two have equal cardinality by step 3.1 and [L2], they are equal, so . Writing , this is a proper module containing and containing every proper module that contains .
If then is a proper module by [L1]; it contains , so step 4.1 gives and hence , and by symmetry , so . Otherwise the two are disjoint, and every vertex lies in .
Depends on
- In a connected and anticonnected graph, the union of two proper modules that meet is again a proper module
- Modules of a graph, and the trivial modules
- The cardinality $\lvert A\rvert$ of a finite set
- A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$
- The well-ordering principle
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
- Maximal proper modules need not be disjoint when the graph or its complement is disconnected Counterexample
- 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
32 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)