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

If two modules overlap, then each difference and their symmetric difference are modules

Statement

Let $M$ and $N$ be modules of a finite simple graph $G$ that overlap, that is, $M \cap N$ , $M ∖ N$ and $N ∖ M$ are all nonempty. Then $M ∖ N$ , $N ∖ M$ and $M △ N = (M ∖ N) \cup (N ∖ M)$ are modules of $G$ .

The overlap hypothesis cannot be weakened to $M \cap N \neq \emptyset$ : for nested modules the difference need not be a module.

Facts & Assumptions

Given: Overlapping modules $M, N$ of a finite simple graph $G$ ; the sets $A = M ∖ N$ , $B = N ∖ M$ and $C = M \cap N$ , all nonempty.

[F1]

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

[L1]

For a module $M$ of $G$ : 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)$ (Three equivalent descriptions of a module: purity of every outside vertex, equality of outside neighbourhoods, and indistinguishability of the members).

[L2]

The union of two modules with a common vertex is a module (The union of two modules with a common vertex is a module).

[F2]

The pair $(A, B)$ of disjoint sets 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).

Proof

technique · cases

1.1L1givenchoose

Fix $w \in B$ and note $w \notin M$ . For $x, x^{'} \in A$ the vertices $x, x^{'}$ lie in $M$ , so [L1] applied to $M$ gives that $w x \in E (G)$ if and only if $w x^{'} \in E (G)$ .

1.2L1given

For $x \in A$ we have $x \notin N$ , so [L1] applied to $N$ gives, for all $p, q \in N$ , that $x p \in E (G)$ if and only if $x q \in E (G)$ ; in particular this holds for $p \in C$ and $q = w$ , both of which lie in $N$ .

1.3assume-case outMF1F2

First case for $A$ : a vertex $v \notin M$ . Then $({v}, M)$ is pure, and since $A \subseteq M$ the pair $({v}, A)$ is pure as well.

1.4assume-case inCgiven

Second case for $A$ : a vertex $v \in C$ . Then $v \in N$ , and $v \notin A$ .

1.5L2F1F2given

Turning to the symmetric difference, let $v \notin A \cup B$ and take first the subcase $v \notin M \cup N$ . The set $M \cup N$ is a module by [L2], since $C \neq \emptyset$ , so $({v}, M \cup N)$ is pure and hence $({v}, A \cup B)$ is pure, as $A \cup B \subseteq M \cup N$ .

2.1step 1.1step 1.2step 1.4F2

In the second case for $A$ , let $x, x^{'} \in A$ . By step 1.2 applied to $x$ with $p = v$ and $q = w$ , $v x \in E (G)$ if and only if $w x \in E (G)$ ; by step 1.1, $w x \in E (G)$ if and only if $w x^{'} \in E (G)$ ; and by step 1.2 applied to $x^{'}$ , $w x^{'} \in E (G)$ if and only if $v x^{'} \in E (G)$ . Hence $v x \in E (G)$ if and only if $v x^{'} \in E (G)$ , so $({v}, A)$ is complete or anticomplete.

2.2step 1.3step 1.4givencases-exhaustive

A vertex $v \notin A$ satisfies $v \notin M$ , or else $v \in M$ and then $v \notin A$ forces $v \in N$ , so $v \in C$ ; the two cases of steps 1.3 and 1.4 are therefore exhaustive.

3.1step 1.3step 2.1step 2.2F1

Steps 1.3, 2.1 and 2.2 make $({v}, A)$ pure for every $v \notin A$ , so $A = M ∖ N$ is a module; exchanging the roles of $M$ and $N$ , which the overlap hypothesis leaves unchanged, shows that $B = N ∖ M$ is a module.

3.2step 1.2step 2.1L1F2

Still for the symmetric difference, take the remaining subcase $v \in M \cup N$ with $v \notin A \cup B$ , so that $v \in C$ . Step 2.1 makes $({v}, A)$ pure and its mirror image makes $({v}, B)$ pure, while step 1.2 applied to some $x \in A$ with $p = v$ and $q \in B$ gives $v x \in E (G)$ if and only if $q x \in E (G)$ , and [L1] applied to $M$ with $q \notin M$ and $x, v \in M$ gives $q x \in E (G)$ if and only if $q v \in E (G)$ . So the adjacency of $v$ to $A$ and its adjacency to $B$ agree, and $({v}, A \cup B)$ is pure.

4.1step 3.1step 1.5step 3.2F1∎

Combining steps 1.5 and 3.2, every vertex outside $A \cup B$ has $({v}, A \cup B)$ pure, so $M △ N$ is a module of $G$ .

Depends on

Used by

A difference of two nested modules that is not a module Counterexample

Dependency tree · two levels

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