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, the union of two proper modules that meet is again a proper module
Statement
Let be a finite simple graph that is both connected and anticonnected, and let be proper modules of with . Then is a proper module of .
Facts & Assumptions
Given: A connected and anticonnected finite simple graph , and proper modules of with .
is a module of when the pair is pure for every , and is proper when (Modules of a graph, and the trivial modules).
The union of two modules with a common vertex is a module (The union of two modules with a common vertex is a module).
In a connected graph, if is a module with , then some vertex outside is complete to (In a connected graph, some vertex outside a nonempty proper module is complete to it).
A vertex set is a module of if and only if it is a module of (A vertex set is a module of exactly when it is a module of ).
For a module of : for all and all , if and only if (Three equivalent descriptions of a module: purity of every outside vertex, equality of outside neighbourhoods, and indistinguishability of the members).
is anticonnected when is connected, and has the same vertex set as (Anticonnected graphs and anticonnected components, Connected graphs and connected components defined by the existence of vertex paths, Graph isomorphisms, automorphisms and graph complements).
A disjoint pair is complete when every cross pair is an edge and anticomplete when no cross pair is an edge; distinct vertices are adjacent in exactly when they are not adjacent in (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs, Graph isomorphisms, automorphisms and graph complements).
Proof
The set is a module of by [L1], since . Suppose for contradiction that .
The set is nonempty, since it contains a vertex of , and because is proper.
If were empty then , so by step 1.1, which is false because is proper; hence , and , again by step 1.1.
Since is connected and is a module with , some vertex is complete to .
The set is a module of as well, and is connected with the same vertex set as , so some vertex is complete to in ; that is, is adjacent in to no vertex of .
Choose . Then , while and both lie in , so [L4] applied to the module gives that if and only if .
But is complete to and , so , while is adjacent to no vertex of , so ; this contradicts step 3.1. Hence , and being a module it is a proper module.
Depends on
- Modules of a graph, and the trivial modules
- The union of two modules with a common vertex is a module
- In a connected graph, some vertex outside a nonempty proper module is complete to it
- A vertex set is a module of $G$ exactly when it is a module of $\overline G$
- Three equivalent descriptions of a module: purity of every outside vertex, equality of outside neighbourhoods, and indistinguishability of the members
- Connected graphs and connected components defined by the existence of vertex paths
- Anticonnected graphs and anticonnected components
- Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs
- Graph isomorphisms, automorphisms and graph complements
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
- 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 Lemma
Dependency tree · two levels
20 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)