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.

The prime quotient produced by the modular decomposition of a connected and anticonnected graph has at least four vertices

Statement

Let $G$ be a connected and anticonnected finite simple graph with $∣ V (G) ∣ \geq 2$ , and let $R$ be the modular partition of $G$ into its maximal proper modules, whose quotient is prime (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). Then $∣ R ∣ \geq 4$ , so the prime quotient $G / R$ has at least four vertices.

Facts & Assumptions

Given: A connected and anticonnected finite simple graph $G$ with $∣ V (G) ∣ \geq 2$ , and its partition $R$ into maximal proper modules, with $G / R$ prime and $∣ R ∣ \geq 2$ .

[L1]

For a connected and anticonnected graph with at least two vertices, the maximal proper modules form a modular partition with at least two parts whose quotient is prime (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).

[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 $R$ (Modular partitions and the quotient graph they define, The cardinality $∣ A ∣$ of a finite set).

[F2]

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

[L2]

In a connected graph, if $M$ is a module with $\emptyset \neq M \neq V (G)$ , then some vertex outside $M$ is complete to $M$ (In a connected graph, some vertex outside a nonempty proper module is complete to it).

[L3]

A vertex set is a module of $G$ if and only if it is a module of $\overline{G}$ (A vertex set is a module of $G$ exactly when it is a module of $\overline{G}$ ).

[L4]

Every finite simple graph on exactly three vertices has a nontrivial module, and is therefore not prime (No graph on exactly three vertices is prime).

[F3]

$G$ is prime when every module of $G$ is trivial (Prime graphs: those whose only modules are the trivial ones).

[F4]

$G$ is anticonnected when $\overline{G}$ is connected, and $\overline{G}$ has the same vertex set as $G$ ; distinct vertices are adjacent in $\overline{G}$ exactly when they are not adjacent in $G$ (Anticonnected graphs and anticonnected components, Connected graphs and connected components defined by the existence of vertex paths, Graph isomorphisms, automorphisms and graph complements).

[F5]

A disjoint pair is complete when every cross pair is an edge and anticomplete when no cross pair is an edge (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

Proof

technique · cases

1.1L1F1

By [L1] the partition $R$ has at least two parts, so $∣ R ∣ \geq 2$ and it remains to exclude $∣ R ∣ = 2$ and $∣ R ∣ = 3$ .

1.2assume-case twoF1F2

First case: $∣ R ∣ = 2$ , say $R = {M_{1}, M_{2}}$ . Then $M_{1}$ is a nonempty module of $G$ and $M_{1} \neq V (G)$ , since $M_{2}$ is nonempty and disjoint from it, so $V (G) ∖ M_{1} = M_{2}$ .

1.3assume-case threeF1L4

Second case: $∣ R ∣ = 3$ . Then $G / R$ is a finite simple graph on exactly three vertices, so it has a nontrivial module and is not prime.

2.1step 1.2L2L3F4F5

In the first case, $G$ is connected, so [L2] gives a vertex $v \in M_{2}$ complete to $M_{1}$ ; and $M_{1}$ is a module of $\overline{G}$ by [L3], with $\overline{G}$ connected because $G$ is anticonnected, so [L2] applied in $\overline{G}$ gives a vertex $v^{'} \in M_{2}$ complete to $M_{1}$ in $\overline{G}$ , that is, adjacent in $G$ to no vertex of $M_{1}$ .

3.1step 1.2step 2.1F2F5choose

Still in the first case, $M_{2}$ is a module of $G$ and $M_{1}$ is nonempty, so picking $x \in M_{1}$ , which lies outside $M_{2}$ , the two vertices $v, v^{'} \in M_{2}$ satisfy $x v \in E (G)$ if and only if $x v^{'} \in E (G)$ ; but step 2.1 makes $x v$ an edge and $x v^{'}$ a non-edge. So $∣ R ∣ = 2$ is impossible.

4.1step 1.1step 1.3step 3.1L1F3cases-exhaustive∎

The second case contradicts the primality of $G / R$ supplied by [L1], so $∣ R ∣ = 3$ is impossible as well; the two excluded cases together with step 1.1 leave $∣ R ∣ \geq 4$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

36 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.4 (standard reference, not scraped)