LemmaStatement: 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.

Three equivalent descriptions of a module: purity of every outside vertex, equality of outside neighbourhoods, and indistinguishability of the members

Statement

Let $G$ be a finite simple graph and let $M \subseteq V (G)$ . The following three conditions are equivalent.

$M$ is a module of $G$ (Modules of a graph, and the trivial modules).
$N_{G} (x) ∖ M = N_{G} (y) ∖ M$ for all $x, y \in M$ .
For all $x, y \in M$ and all $v \in V (G) ∖ M$ : $v x \in E (G)$ if and only if $v y \in E (G)$ .

Facts & Assumptions

Given: A finite simple graph $G$ and a set $M \subseteq V (G)$ .

[F1]

$M$ is a module of $G$ when every vertex $v \in V (G) ∖ M$ is adjacent to every vertex of $M$ or to no vertex of $M$ ; equivalently, the pair $({v}, M)$ is pure for every such $v$ (Modules of a graph, and the trivial modules).

[F2]

A disjoint pair $(A, B)$ is complete when every $a \in A$ is adjacent to every $b \in B$ , anticomplete when no $a \in A$ is adjacent to any $b \in B$ , and pure when it is complete or anticomplete (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

[F3]

$N_{G} (v) = {u \in V : {u, v} \in E}$ (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

Proof

technique · direct

1.1F1F2F3

For the implication from 1 to 2, assume $M$ is a module, and let $x, y \in M$ and $v \in N_{G} (x) ∖ M$ . Then $v \notin M$ , so $({v}, M)$ is pure, and it is not anticomplete because $v$ is adjacent to $x \in M$ ; hence it is complete, so $v$ is adjacent to $y$ and $v \in N_{G} (y) ∖ M$ .

1.2F3

For the implication from 2 to 3, assume condition 2 and let $x, y \in M$ and $v \in V (G) ∖ M$ with $v x \in E (G)$ . Then $v \in N_{G} (x) ∖ M = N_{G} (y) ∖ M$ , so $v y \in E (G)$ ; exchanging the roles of $x$ and $y$ gives the reverse implication, which is condition 3.

1.3F2F3

For the implication from 3 to 1, assume condition 3 and let $v \in V (G) ∖ M$ . If $v$ is adjacent to some $x \in M$ , then condition 3 makes $v$ adjacent to every $y \in M$ , so $({v}, M)$ is complete; if $v$ is adjacent to no vertex of $M$ , then $({v}, M)$ is anticomplete. In both cases the pair is pure.

2.1step 1.1

Step 1.1 applies to both orders of $x$ and $y$ , giving $N_{G} (x) ∖ M \subseteq N_{G} (y) ∖ M$ and $N_{G} (y) ∖ M \subseteq N_{G} (x) ∖ M$ , so condition 1 implies condition 2.

2.2step 1.3F1

Step 1.3 verifies the condition of [F1] at every vertex outside $M$ , so condition 3 implies condition 1.

3.1step 2.1step 1.2step 2.2∎

The implications of steps 2.1, 1.2 and 2.2 form the cycle from 1 to 2 to 3 and back to 1, so the three conditions are equivalent.

Depends on

Used by

Dependency tree · two levels

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