Alphabeta Math
CorollaryStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck 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 vV(G)M, and M is proper when MV(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 XP, the set X is a module of G/P if and only if MXM 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.1

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

F1F2given
2.1

Fix M0P and xM0, and let M(x) be the largest proper module of G containing x. Then M0M(x) by step 1.1 and the maximality in [L3].

step 1.1L3choose
3.1

Let X={NP:NM(x)} and let NX. Both N and M(x) are proper modules and they meet, so NM(x) is a proper module by [L2]; it contains x, so [L3] gives NM(x)M(x) and hence NM(x).

step 1.1step 2.1L2L3
4.1

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

step 3.1F1
5.1

By [L1] the set X is therefore a module of G/P, hence trivial by [F3]. It is not empty, since M0X 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.

step 2.1step 4.1L1F1F3
6.1

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.

step 5.1L3L4

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