Alphabeta Math
CorollaryStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26
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 G be a connected and anticonnected finite simple graph with ∣V(G)∣≥2, and let P be a modular partition of G with at least two parts whose quotient G/P is prime. Then every part of P is a maximal proper module M(v), and P is the partition of G into its maximal proper modules. In particular G 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 G with ∣V(G)∣≥2, and a modular partition P of G with at least two parts and G/P prime.

[F1]

A modular partition of G is a set of nonempty, pairwise disjoint modules of G whose union is V(G); the quotient has vertex set P (Modular partitions and the quotient graph they define).

[F2]

M is a module of G when the pair ({v},M) is pure for every v∈V(G)∖M, and M is proper when M≠V(G) (Modules of a graph, and the trivial modules).

[F3]

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).

[L1]

For a modular partition P and X⊆P, the set X is a module of G/P if and only if ⋃M∈XM is a module of G (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).

[L2]

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).

[L3]

In a connected and anticonnected graph with at least two vertices, each vertex v lies in a largest proper module M(v), any two of these are equal or disjoint, and they cover V(G) (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).

Proof

technique · direct
1.1F1F2given

Every part N∈P is a nonempty module of G, and N≠V(G) because P has another part, which is nonempty and disjoint from N; so every part is a proper module.

2.1step 1.1L3choose

Fix M0∈P and x∈M0, and let M(x) be the largest proper module of G containing x. Then M0⊆M(x) by step 1.1 and the maximality in [L3].

3.1step 1.1step 2.1L2L3

Let X={N∈P:N∩M(x)≠∅} and let N∈X. Both N and M(x) are proper modules and they meet, so N∪M(x) is a proper module by [L2]; it contains x, so [L3] gives N∪M(x)⊆M(x) and hence N⊆M(x).

4.1step 3.1F1

Every vertex of M(x) lies in a part, and that part meets M(x) and so lies in X; with step 3.1 this gives M(x)=⋃N∈XN.

5.1step 2.1step 4.1L1F1F3

By [L1] the set X is therefore a module of G/P, hence trivial by [F3]. It is not empty, since M0∈X by step 2.1; and it is not all of P, since that would give M(x)=V(G), contradicting properness. So X is a singleton, and by step 2.1 its unique member is M0, whence M(x)=M0.

6.1step 5.1L3L4∎

So each part of P equals M(x) for each of its vertices x, and conversely each M(v) is the part containing v by the same computation; hence P 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 G with at least two parts has a prime quotient.

Depends on

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