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.

✓ 30 results · all verified · 26 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Modules, Substitution and Prime Graphs

1 · Prerequisites

2 · Summary

Modules record when a vertex set is indistinguishable from outside the set. The page uses the already-built homogeneous number and Erdős–Hajnal property, together with the graph-theoretic language of components, anticomponents, pure pairs, induced copies, and substitution. Those ingredients split the subject into two linked directions: structural lemmas about how modules behave under intersection, union, complementation, and quotients, and extremal lemmas that measure how substitution interacts with homogeneous sets and induced patterns.

The page defines modules, prime graphs, substitution, modular partitions, and quotient graphs. It proves the module-closure lemmas needed to make quotients well defined, then proves Gallai's modular decomposition theorem and the uniqueness of the prime quotient in the connected anticonnected case. The second half proves that substitution preserves the Erdős–Hajnal property, derives the reduction of the conjecture to prime graphs, and records the basic blow-up corollary that later hereditary-class pages use.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

Modules of a graph, and the trivial modules

Definition

Let $G$ be a finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets). A vertex set $M \subseteq V (G)$ 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 disjoint pair $({v}, M)$ is pure for every $v \in V (G) ∖ M$ (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs, Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

The condition constrains only the edges between $M$ and $V (G) ∖ M$ : no condition whatever is placed on the induced subgraph $G [M]$ (Subgraphs, induced subgraphs and spanning subgraphs).

The trivial modules of $G$ are $\emptyset$ , the singletons ${v}$ for $v \in V (G)$ , and $V (G)$ itself. Each of the three really is a module: for $M = \emptyset$ every pair $({v}, \emptyset)$ is both complete and anticomplete, hence pure; for $M = {u}$ the pair $({v}, {u})$ is complete when $u v \in E (G)$ and anticomplete otherwise; and for $M = V (G)$ there is no vertex outside $M$ , so the condition is vacuous. A module that is not one of these is nontrivial. Since $V (G)$ is finite, a module $M$ is nontrivial exactly when $2 \leq ∣ M ∣$ and $∣ M ∣ \leq ∣ V (G) ∣ - 1$ , the second bound because a subset of a finite set has the full cardinality only if it is the whole set (The cardinality $∣ A ∣$ of a finite set, A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ).

A module $M$ is proper when $M \neq V (G)$ . Thus $\emptyset$ is a proper module exactly when $V (G) \neq \emptyset$ , every singleton of a graph with at least two vertices is a proper module, and every nontrivial module is proper.

Remarks

The word module is Habib and Paul's. The same object is called a clan by Harju, a closed set by Gallai, and an autonomous, partitive, externally related or homogeneous set elsewhere; the clash between the last of these and the published meaning of homogeneous set is the subject of Why this page says module where some sources say homogeneous set.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

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.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

A vertex set is a module of $G$ exactly when it is a module of $\overline{G}$

Statement

For every finite simple graph $G$ and every $M \subseteq V (G)$ , the set $M$ is a module of $G$ if and only if it is a module of $\overline{G}$ .

Facts & Assumptions

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

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

[F2]

The complement of $G = (V, E)$ is $\overline{G} = (V, [V]^{2} ∖ E)$ , and $\overline{\overline{G}} = G$ (Graph isomorphisms, automorphisms and graph complements).

[L1]

For disjoint vertex sets $A, B$ in a graph, complementation swaps complete pairs with anticomplete pairs and preserves pure pairs and mixed pairs (Purity is symmetric; complementation swaps complete and anticomplete pairs and preserves mixed pairs).

[F3]

A disjoint pair is pure when it is complete or anticomplete (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

Proof

technique · direct

1.1L1F3

For $v \in V (G) ∖ M$ the sets ${v}$ and $M$ are disjoint, so the pair $({v}, M)$ is pure in $G$ exactly when it is pure in $\overline{G}$ .

1.2F2

The graphs $G$ and $\overline{G}$ have the same vertex set, so a vertex lies outside $M$ in one exactly when it lies outside $M$ in the other.

2.1step 1.1step 1.2F1

If $M$ is a module of $G$ , then $({v}, M)$ is pure in $G$ for every vertex $v$ outside $M$ , hence pure in $\overline{G}$ for every such vertex, so $M$ is a module of $\overline{G}$ .

3.1step 2.1F2∎

Applying step 2.1 to the graph $\overline{G}$ and using $\overline{\overline{G}} = G$ gives the converse implication, so $M$ is a module of $G$ exactly when it is a module of $\overline{G}$ .

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

Every union of connected components is a module, and so is every union of anticonnected components

Statement

Let $G$ be a finite simple graph. If $M$ is a union of vertex sets of connected components of $G$ , then $M$ is a module of $G$ , and every vertex outside $M$ is anticomplete to $M$ . If $M$ is a union of anticomponents of $G$ , then $M$ is a module of $G$ , and every vertex outside $M$ is complete to $M$ .

Facts & Assumptions

Given: A finite simple graph $G$ .

[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]

The vertex sets $C_{G} (v)$ of the connected components of $G$ are nonempty, cover $V (G)$ , and any two are equal or disjoint (The connected components of a graph partition its vertex set and are its maximal connected subgraphs, Connected graphs and connected components defined by the existence of vertex paths).

[L2]

Distinct connected components of a graph are anticomplete to one another, and distinct anticomponents are complete to one another (Distinct connected components are anticomplete, and distinct anticonnected components are complete).

[F2]

The anticomponents of $G$ are exactly the connected components of $\overline{G}$ ; consequently their vertex sets are nonempty, cover $V (G)$ , and any two are equal or disjoint (The anticonnected components of $G$ are exactly the connected components of $\overline{G}$ , The connected components of a graph partition its vertex set and are its maximal connected subgraphs).

[F3]

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

Proof

technique · direct

1.1L1

Let $M$ be a union of component vertex sets and let $v \in V (G) ∖ M$ . The component $C_{G} (v)$ meets no component contained in $M$ , since $v \notin M$ and distinct components are disjoint, so $C_{G} (v)$ is distinct from every component inside $M$ .

1.2F2

Let $M$ be a union of anticomponents and let $v \in V (G) ∖ M$ . The anticomponent containing $v$ is disjoint from every anticomponent inside $M$ and hence distinct from each of them.

2.1step 1.1L2F3

In the component case of step 1.1, $v$ has no neighbour in any component inside $M$ , so $v$ has no neighbour in $M$ and $({v}, M)$ is anticomplete, hence pure.

2.2step 1.2L2F3

In the anticomponent case of step 1.2, $v$ is adjacent to every vertex of every anticomponent inside $M$ , so $v$ is adjacent to every vertex of $M$ and $({v}, M)$ is complete, hence pure.

3.1step 2.1step 2.2F1∎

Steps 2.1 and 2.2 verify the condition of [F1] at every vertex outside $M$ in the two cases, so both kinds of union are modules, with the stated purity.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

Two disjoint nonempty modules form a complete or an anticomplete pair

Statement

Let $M$ and $N$ be disjoint nonempty modules (Modules of a graph, and the trivial modules) of a finite simple graph $G$ . Then the pair $(M, N)$ is complete or anticomplete, and it is not both.

Facts & Assumptions

Given: Disjoint nonempty modules $M, N$ of a finite simple graph $G$ .

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

[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 · direct

1.1givenchoose

Fix $x_{0} \in M$ and $y_{0} \in N$ , which exist because both sets are nonempty.

1.2L1given

Let $x \in M$ and $y \in N$ . Since $y \notin M$ and $x, x_{0} \in M$ , applying [L1] to the module $M$ gives that $x y \in E (G)$ if and only if $x_{0} y \in E (G)$ .

1.3L1given

Since $x_{0} \notin N$ and $y, y_{0} \in N$ , applying [L1] to the module $N$ gives that $x_{0} y \in E (G)$ if and only if $x_{0} y_{0} \in E (G)$ .

2.1step 1.1step 1.2step 1.3

Combining steps 1.2 and 1.3, every $x \in M$ and $y \in N$ satisfy: $x y \in E (G)$ if and only if $x_{0} y_{0} \in E (G)$ .

3.1step 2.1F2∎

If $x_{0} y_{0} \in E (G)$ then step 2.1 makes every cross pair an edge, so $(M, N)$ is complete; otherwise step 2.1 makes no cross pair an edge, so $(M, N)$ is anticomplete. The two cannot both hold, since the single pair $x_{0} y_{0}$ would then be both an edge and not an edge.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The intersection of two modules is a module

Statement

If $M$ and $N$ are modules of a finite simple graph $G$ , then $M \cap N$ is a module of $G$ . No hypothesis relating $M$ and $N$ is needed, and the case $M \cap N = \emptyset$ is included.

Facts & Assumptions

Given: Modules $M, N$ of a finite simple graph $G$ , and a vertex $v \in V (G) ∖ (M \cap N)$ .

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

[F2]

Proof

technique · cases

1.1F2

If $v$ is complete to a set $S$ then $v$ is complete to every subset of $S$ , and if $v$ is anticomplete to $S$ then $v$ is anticomplete to every subset of $S$ ; so purity of $({v}, S)$ passes to every subset of $S$ .

1.2assume-case outMF1

First case: $v \notin M$ . Then $({v}, M)$ is pure because $M$ is a module.

1.3assume-case inMF1given

Second case: $v \in M$ . Since $v \notin M \cap N$ , this forces $v \notin N$ , and then $({v}, N)$ is pure because $N$ is a module.

2.1step 1.1step 1.2step 1.3cases-exhaustive

In the first case step 1.1 applied to $S = M \supseteq M \cap N$ makes $({v}, M \cap N)$ pure, and in the second case step 1.1 applied to $S = N \supseteq M \cap N$ does the same. The two cases exhaust the possibilities for $v$ .

3.1step 2.1F1∎

Every vertex outside $M \cap N$ therefore has $({v}, M \cap N)$ pure, which is the module condition of [F1], so $M \cap N$ is a module of $G$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The union of two modules with a common vertex is a module

Statement

Let $M$ and $N$ be modules of a finite simple graph $G$ with $M \cap N \neq \emptyset$ . Then $M \cup N$ is a module of $G$ .

Facts & Assumptions

Given: Modules $M, N$ of a finite simple graph $G$ with $M \cap N \neq \emptyset$ , and a vertex $v \in V (G) ∖ (M \cup N)$ .

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

[F2]

Proof

technique · cases

1.1givenF1choose

Fix $u \in M \cap N$ . Since $v \notin M \cup N$ , the vertex $v$ lies outside $M$ and outside $N$ , so both $({v}, M)$ and $({v}, N)$ are pure.

1.2assume-case adjF2

First case: $u v \in E (G)$ . Then $({v}, M)$ is not anticomplete, since $u \in M$ , so it is complete; and likewise $({v}, N)$ is complete.

1.3assume-case nonadjF2

Second case: $u v \notin E (G)$ . Then $({v}, M)$ is not complete, since $u \in M$ , so it is anticomplete; and likewise $({v}, N)$ is anticomplete.

2.1step 1.1step 1.2step 1.3F2cases-exhaustive

In the first case $v$ is adjacent to every vertex of $M$ and to every vertex of $N$ , hence to every vertex of $M \cup N$ ; in the second case $v$ is adjacent to no vertex of $M$ and to no vertex of $N$ , hence to no vertex of $M \cup N$ . The two cases exhaust the possibilities.

3.1step 2.1F1∎

So $({v}, M \cup N)$ is pure for every vertex $v$ outside $M \cup N$ , which is the module condition of [F1].

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

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]

[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]

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

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

If $M$ is a module of $G$ and $W \subseteq V (G)$ , then $M \cap W$ is a module of $G [W]$

Statement

Let $M$ be a module of a finite simple graph $G$ and let $W \subseteq V (G)$ . Then $M \cap W$ is a module of the induced subgraph $G [W]$ .

Facts & Assumptions

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

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

[F2]

$G [W] = (W, E (G) \cap [W]^{2})$ , so two vertices of $W$ are adjacent in $G [W]$ exactly when they are adjacent in $G$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F3]

Proof

technique · direct

1.1F1given

Let $v \in W ∖ (M \cap W)$ . Since $v \in W$ , this gives $v \notin M$ , so $({v}, M)$ is pure in $G$ .

2.1F2

The vertex set of $G [W]$ is $W$ , so the vertices outside $M \cap W$ in $G [W]$ are exactly the vertices $v$ of step 1.1.

2.2step 1.1F3

If $({v}, M)$ is complete in $G$ then $v$ is adjacent in $G$ to every vertex of $M \cap W \subseteq M$ , and if it is anticomplete then $v$ is adjacent in $G$ to no vertex of $M \cap W$ .

3.1step 2.2F2F3

Both $v$ and the vertices of $M \cap W$ lie in $W$ , so those adjacencies are the same in $G [W]$ as in $G$ ; hence $({v}, M \cap W)$ is pure in $G [W]$ .

4.1step 2.1step 3.1F1∎

Every vertex of $G [W]$ outside $M \cap W$ therefore satisfies the module condition of [F1] in $G [W]$ , so $M \cap W$ is a module of $G [W]$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

A module of $G [M]$ is a module of $G$ whenever $M$ is a module of $G$

Statement

Let $M$ be a module of a finite simple graph $G$ and let $X \subseteq M$ be a module of the induced subgraph $G [M]$ . Then $X$ is a module of $G$ .

Facts & Assumptions

Given: A module $M$ of a finite simple graph $G$ , a module $X$ of $G [M]$ , and a vertex $v \in V (G) ∖ X$ .

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

[F2]

$G [M] = (M, E (G) \cap [M]^{2})$ , so two vertices of $M$ are adjacent in $G [M]$ exactly when they are adjacent in $G$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F3]

Proof

technique · cases

1.1assume-case inMF1F2F3

First case: $v \in M ∖ X$ . Since $X$ is a module of $G [M]$ and $v$ is a vertex of $G [M]$ outside $X$ , the pair $({v}, X)$ is pure in $G [M]$ ; as $v$ and the vertices of $X$ all lie in $M$ , the same adjacencies hold in $G$ , so $({v}, X)$ is pure in $G$ .

1.2assume-case outMF1F3

Second case: $v \notin M$ . Then $({v}, M)$ is pure in $G$ because $M$ is a module of $G$ , and $X \subseteq M$ , so $({v}, X)$ is pure in $G$ .

2.1step 1.1step 1.2givencases-exhaustive

A vertex $v \notin X$ lies in $M$ or outside $M$ , so the two cases are exhaustive and $({v}, X)$ is pure in $G$ for every $v \in V (G) ∖ X$ .

3.1step 2.1F1∎

That is the module condition of [F1] for $X$ in $G$ , so $X$ is a module of $G$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

In a connected graph, some vertex outside a nonempty proper module is complete to it

Statement

Let $G$ be a connected finite simple graph and let $M$ be a module of $G$ with $\emptyset \neq M \neq V (G)$ . Then some vertex $v \in V (G) ∖ M$ is complete to $M$ .

Facts & Assumptions

Given: A connected finite simple graph $G$ and a module $M$ of $G$ with $\emptyset \neq M \neq V (G)$ .

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

[F2]

A graph is connected when its vertex set is nonempty and every two of its vertices are joined by a path (Connected graphs and connected components defined by the existence of vertex paths).

[F3]

A walk of length $ℓ$ is a vertex list $(v_{0}, \dots, v_{ℓ})$ with ${v_{i - 1}, v_{i}} \in E$ for every $1 \leq i \leq ℓ$ , and a path is a walk whose vertices are distinct (Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges).

[F4]

[L1]

Every nonempty subset of $N$ has a least element (The well-ordering principle).

Proof

technique · direct

1.1givenchoose

Choose $u \in M$ and $w \in V (G) ∖ M$ ; both choices are possible because $M \neq \emptyset$ and $M \neq V (G)$ .

1.2F2F3given

Since $G$ is connected there is a path $(v_{0}, \dots, v_{ℓ})$ with $v_{0} = u$ and $v_{ℓ} = w$ .

2.1step 1.1step 1.2L1

The set ${i \leq ℓ : v_{i} \notin M}$ is a nonempty subset of $N$ , since it contains $ℓ$ , so it has a least element $k$ ; and $k \geq 1$ because $v_{0} = u \in M$ .

3.1step 2.1F3

By minimality $v_{k - 1} \in M$ , and ${v_{k - 1}, v_{k}}$ is an edge of $G$ because consecutive vertices of a path are adjacent.

4.1step 3.1F1F4∎

Put $v = v_{k}$ . Then $v \notin M$ , so $({v}, M)$ is pure, and it is not anticomplete because $v$ is adjacent to $v_{k - 1} \in M$ ; hence it is complete, that is, $v$ is complete to $M$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

Prime graphs: those whose only modules are the trivial ones

Definition

A finite simple graph $G$ (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets) is prime when every module of $G$ is trivial, that is, when the only modules of $G$ are $\emptyset$ , the singletons and $V (G)$ (Modules of a graph, and the trivial modules). Equivalently, $G$ is prime when it has no module $M$ with $2 \leq ∣ M ∣$ and $∣ M ∣ \leq ∣ V (G) ∣ - 1$ (The cardinality $∣ A ∣$ of a finite set).

Under this convention the null graph, every graph on one vertex and every graph on two vertices is prime, since such a graph has no vertex set at all whose cardinality lies between $2$ and $∣ V (G) ∣ - 1$ . Which small graphs a source counts as prime is not uniform in the literature, and the alternatives are recorded in Which small graphs count as prime on this page.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

No graph on exactly three vertices is prime

Statement

Every finite simple graph $G$ with $∣ V (G) ∣ = 3$ has a nontrivial module, and is therefore not prime.

Facts & Assumptions

Given: A finite simple graph $G$ with $V (G) = {x, y, z}$ , three distinct vertices.

[F1]

$M$ is a module of $G$ when the pair $({v}, M)$ is pure for every $v \in V (G) ∖ M$ , and $M$ is nontrivial when $2 \leq ∣ M ∣$ and $∣ M ∣ \leq ∣ V (G) ∣ - 1$ (Modules of a graph, and the trivial modules, The cardinality $∣ A ∣$ of a finite set).

[F2]

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

[F3]

The edge set of $G$ is a set of two-element subsets of $V (G)$ , and the two-element subsets of ${x, y, z}$ are exactly ${x, y}$ , ${x, z}$ and ${y, z}$ (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

[F4]

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

Proof

technique · cases

1.1F1F3

By [F3] the graph has at most three edges, so $∣ E (G) ∣$ is $0$ , $1$ , $2$ or $3$ , and any two-element $M \subseteq V (G)$ has $∣ M ∣ = 2 = ∣ V (G) ∣ - 1$ , hence is nontrivial once it is a module.

1.2assume-case noneF3F4

First case: $∣ E (G) ∣ = 0$ . Take $M = {x, y}$ ; the only vertex outside is $z$ , and it is adjacent to neither, so $({z}, M)$ is anticomplete.

1.3assume-case allF3F4

Second case: $∣ E (G) ∣ = 3$ . Take $M = {x, y}$ ; the only vertex outside is $z$ , and by [F3] both ${x, z}$ and ${y, z}$ are edges, so $({z}, M)$ is complete.

1.4assume-case oneF3F4

Third case: $∣ E (G) ∣ = 1$ , say the single edge is ${p, q}$ and $r$ is the remaining vertex. Take $M = {p, q}$ ; neither ${p, r}$ nor ${q, r}$ is an edge, since there is only one edge and it is ${p, q}$ , so $({r}, M)$ is anticomplete.

1.5assume-case twoF3F4

Fourth case: $∣ E (G) ∣ = 2$ . Each of the three possible edges listed in [F3] meets each of the other two, so the two edges of $G$ share a vertex $q$ ; write them as ${p, q}$ and ${q, r}$ with ${p, q, r} = V (G)$ . Take $M = {p, r}$ ; the only vertex outside is $q$ , which is adjacent to both, so $({q}, M)$ is complete.

2.1step 1.1step 1.2step 1.3step 1.4step 1.5F1cases-exhaustive

The four cases cover every value of $∣ E (G) ∣$ allowed by step 1.1, and in each of them the exhibited two-element set $M$ has $({v}, M)$ pure for the single vertex $v$ outside it, so $M$ is a module.

3.1step 2.1F1F2∎

That module is nontrivial by step 1.1, so $G$ is not prime.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

Substituting one graph for a vertex of another

Definition

Let $G_{1}$ and $G_{2}$ be finite simple graphs (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets), let $a \in V (G_{1})$ , and assume $V (G_{2}) \neq \emptyset$ and

$(V (G_{1}) ∖ {a}) \cap V (G_{2}) = \emptyset .$

The graph obtained by substituting $G_{2}$ for $a$ in $G_{1}$ , written $G_{1} [a \to G_{2}]$ , has vertex set

$V (G_{1} [a \to G_{2}]) : = (V (G_{1}) ∖ {a}) \cup V (G_{2}),$

a union of two disjoint sets, and for distinct vertices $p, q$ of that set the pair ${p, q}$ is an edge exactly in the following three situations (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree):

(S1) $p, q \in V (G_{1}) ∖ {a}$ and ${p, q} \in E (G_{1})$ ;
(S2) $p, q \in V (G_{2})$ and ${p, q} \in E (G_{2})$ ;
(S3) one of $p, q$ lies in $V (G_{1}) ∖ {a}$ , the other lies in $V (G_{2})$ , and the vertex in $V (G_{1}) ∖ {a}$ is adjacent to $a$ in $G_{1}$ .

Because the two parts of the vertex set are disjoint, every pair of distinct vertices falls under exactly one of the three situations, so the edge set is well defined and $G_{1} [a \to G_{2}]$ is again a finite simple graph. The construction replaces $a$ by a copy of $G_{2}$ whose members all inherit the adjacencies $a$ had, and the induced subgraphs on the two parts are $G_{1} - a$ and $G_{2}$ (Subgraphs, induced subgraphs and spanning subgraphs).

The disjointness required is only between $V (G_{1}) ∖ {a}$ and $V (G_{2})$ . The substituted vertex $a$ may itself belong to $V (G_{2})$ . This is what lets a graph be written as a substitution using two of its own induced subgraphs, with no renaming of vertices; the sources state the construction for graphs with disjoint vertex sets, which is the special case $a \notin V (G_{2})$ , and the two agree up to isomorphism (Graph isomorphisms, automorphisms and graph complements).

$G_{2}$ must be nonnull. If $V (G_{2})$ were empty the construction would delete $a$ rather than replace it, and the vertex sets of $G_{1}$ and $G_{1} [a \to G_{2}]$ would not correspond.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

In $G_{1}$ with $G_{2}$ substituted for $a$ , the vertex set of $G_{2}$ is a module, the two factors are recovered as induced subgraphs, and substituting a one-vertex graph changes nothing

Statement

Let $G = G_{1} [a \to G_{2}]$ be a substitution (Substituting one graph for a vertex of another), and write $U = V (G_{1}) ∖ {a}$ . Then:

$V (G_{2})$ is a module of $G$ ;
$G [U] = G_{1} [U]$ and $G [V (G_{2})] = G_{2}$ ;
for every $w \in V (G_{2})$ , the map $φ_{w} : V (G_{1}) \to V (G)$ that fixes every vertex of $U$ and sends $a$ to $w$ is an induced embedding of $G_{1}$ into $G$ ;
if $∣ V (G_{2}) ∣ = 1$ then $G ≅ G_{1}$ .

Facts & Assumptions

Given: A substitution $G = G_{1} [a \to G_{2}]$ with $U = V (G_{1}) ∖ {a}$ , so that $V (G) = U \cup V (G_{2})$ is a disjoint union.

[F1]

For distinct vertices of $G$ : two vertices of $U$ are adjacent in $G$ exactly when they are adjacent in $G_{1}$ ; two vertices of $V (G_{2})$ are adjacent in $G$ exactly when they are adjacent in $G_{2}$ ; and $u \in U$ is adjacent in $G$ to $x \in V (G_{2})$ exactly when $u$ is adjacent to $a$ in $G_{1}$ (Substituting one graph for a vertex of another).

[F2]

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

[F3]

$G [W] = (W, E (G) \cap [W]^{2})$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F4]

An induced embedding of $H$ in $G$ is an injection $φ : V (H) \to V (G)$ such that, for all distinct $x, y \in V (H)$ , $x y \in E (H)$ if and only if $φ (x) φ (y) \in E (G)$ ; its image induces a copy of $H$ , the restricted map being an isomorphism onto it (Induced embeddings and induced copies of a graph).

[F5]

A graph isomorphism is a bijection $φ : V \to W$ with ${u, v} \in E$ if and only if ${φ (u), φ (v)} \in F$ for all distinct $u, v$ (Graph isomorphisms, automorphisms and graph complements).

[F6]

Proof

technique · direct

1.1F1given

The vertices of $G$ outside $V (G_{2})$ are exactly those of $U$ , and for $u \in U$ the adjacency of $u$ to a vertex $x \in V (G_{2})$ is the condition that $u$ is adjacent to $a$ in $G_{1}$ , which does not mention $x$ .

1.2F1

For $p, q \in U$ distinct, ${p, q} \in E (G)$ if and only if ${p, q} \in E (G_{1})$ ; and for $p, q \in V (G_{2})$ distinct, ${p, q} \in E (G)$ if and only if ${p, q} \in E (G_{2})$ .

1.3F4givenconstruct

Fix $w \in V (G_{2})$ and let $φ_{w}$ fix $U$ pointwise and send $a$ to $w$ . It is injective: it is the identity on $U$ , and $w \notin U$ because $U$ and $V (G_{2})$ are disjoint, so no vertex of $U$ is sent to $w$ .

2.1step 1.1F2F6

By step 1.1, if $u$ is adjacent to $a$ in $G_{1}$ then $u$ is adjacent in $G$ to every vertex of $V (G_{2})$ , and otherwise to none, so $({u}, V (G_{2}))$ is pure for every $u \in U$ ; by [F2] this makes $V (G_{2})$ a module of $G$ , which is claim 1.

2.2step 1.2F3

By step 1.2 the edges of $G$ inside $U$ are the edges of $G_{1}$ inside $U$ , so $G [U] = G_{1} [U]$ ; and the edges of $G$ inside $V (G_{2})$ are the edges of $G_{2}$ , whose vertex set is $V (G_{2})$ , so $G [V (G_{2})] = G_{2}$ . This is claim 2.

2.3step 1.1step 1.2step 1.3F4

For distinct $p, q \in U$ , step 1.2 gives ${p, q} \in E (G_{1})$ if and only if ${φ_{w} (p), φ_{w} (q)} = {p, q} \in E (G)$ ; and for $u \in U$ , step 1.1 gives ${u, a} \in E (G_{1})$ if and only if ${u, w} = {φ_{w} (u), φ_{w} (a)} \in E (G)$ . Every pair of distinct vertices of $G_{1}$ is of one of these two shapes, so $φ_{w}$ is an induced embedding, which is claim 3.

3.1step 2.3F4F5∎

If $∣ V (G_{2}) ∣ = 1$ , say $V (G_{2}) = {w}$ , then the image of $φ_{w}$ is $U \cup {w} = V (G)$ , so $φ_{w}$ is a bijection onto $V (G)$ preserving and reflecting adjacency, that is, an isomorphism $G_{1} \to G$ ; this is claim 4.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The complement of $G_{1} [a \to G_{2}]$ is $\overline{G_{1}} [a \to \overline{G_{2}}]$

Statement

Let $G_{1} [a \to G_{2}]$ be a substitution. Then $\overline{G_{1}} [a \to \overline{G_{2}}]$ is also a substitution, and

$\overline{G_{1} [a \to G_{2}]} = \overline{G_{1}} [a \to \overline{G_{2}}] .$

Facts & Assumptions

Given: A substitution $G_{1} [a \to G_{2}]$ , with $U = V (G_{1}) ∖ {a}$ disjoint from $V (G_{2})$ and $V (G_{2}) \neq \emptyset$ .

[F1]

For distinct vertices of $G_{1} [a \to G_{2}]$ : two vertices of $U$ are adjacent exactly when they are adjacent in $G_{1}$ ; two vertices of $V (G_{2})$ are adjacent exactly when they are adjacent in $G_{2}$ ; and $u \in U$ is adjacent to $x \in V (G_{2})$ exactly when $u$ is adjacent to $a$ in $G_{1}$ . The vertex set is $U \cup V (G_{2})$ (Substituting one graph for a vertex of another).

[F2]

The complement of $G = (V, E)$ is $\overline{G} = (V, [V]^{2} ∖ E)$ , so distinct vertices are adjacent in $\overline{G}$ exactly when they are not adjacent in $G$ (Graph isomorphisms, automorphisms and graph complements).

Proof

technique · cases

1.1F1F2

The graphs $\overline{G_{1}}$ and $\overline{G_{2}}$ have the same vertex sets as $G_{1}$ and $G_{2}$ , and $a \in V (\overline{G_{1}})$ , so $\overline{G_{1}} [a \to \overline{G_{2}}]$ is a substitution with the same hypotheses and the same vertex set $U \cup V (G_{2})$ as $G_{1} [a \to G_{2}]$ ; hence both sides of the claimed identity are graphs on that set.

1.2assume-case hostF1F2

First case: distinct $p, q \in U$ . Then ${p, q}$ is an edge of $\overline{G_{1} [a \to G_{2}]}$ exactly when it is not an edge of $G_{1}$ , that is, exactly when it is an edge of $\overline{G_{1}}$ , which is exactly the condition for it to be an edge of $\overline{G_{1}} [a \to \overline{G_{2}}]$ .

1.3assume-case insertedF1F2

Second case: distinct $p, q \in V (G_{2})$ . Then ${p, q}$ is an edge of $\overline{G_{1} [a \to G_{2}]}$ exactly when it is not an edge of $G_{2}$ , that is, exactly when it is an edge of $\overline{G_{2}}$ , which is exactly the condition for it to be an edge of $\overline{G_{1}} [a \to \overline{G_{2}}]$ .

1.4assume-case crossF1F2

Third case: $u \in U$ and $x \in V (G_{2})$ . Then ${u, x}$ is an edge of $\overline{G_{1} [a \to G_{2}]}$ exactly when ${u, a} \notin E (G_{1})$ , that is, exactly when ${u, a} \in E (\overline{G_{1}})$ , which is exactly the condition for ${u, x}$ to be an edge of $\overline{G_{1}} [a \to \overline{G_{2}}]$ .

2.1step 1.2step 1.3step 1.4F1cases-exhaustive

Every pair of distinct vertices of $U \cup V (G_{2})$ falls under exactly one of the three cases, because the union is disjoint, so the three cases are exhaustive.

3.1step 1.1step 2.1∎

The two graphs of step 1.1 therefore have the same vertex set and the same edge set, so they are equal.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

A graph with at least two vertices is prime exactly when it is not obtained by substituting one graph on at least two vertices for a vertex of another graph on at least two vertices

Statement

Let $G$ be a finite simple graph with $∣ V (G) ∣ \geq 2$ . Then $G$ is prime (Prime graphs: those whose only modules are the trivial ones) if and only if there is no substitution $G_{1} [a \to G_{2}]$ (Substituting one graph for a vertex of another) with $∣ V (G_{1}) ∣ \geq 2$ and $∣ V (G_{2}) ∣ \geq 2$ such that $G ≅ G_{1} [a \to G_{2}]$ .

Facts & Assumptions

Given: A finite simple graph $G$ with $∣ V (G) ∣ \geq 2$ .

[F1]

$G$ is prime when every module of $G$ is trivial; equivalently, when $G$ has no module $M$ with $2 \leq ∣ M ∣$ and $∣ M ∣ \leq ∣ V (G) ∣ - 1$ (Prime graphs: those whose only modules are the trivial ones).

[F2]

$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]

In a substitution $G_{1} [a \to G_{2}]$ the set $V (G_{2})$ is a module of $G_{1} [a \to G_{2}]$ (In $G_{1}$ with $G_{2}$ substituted for $a$ , the vertex set of $G_{2}$ is a module, the two factors are recovered as induced subgraphs, and substituting a one-vertex graph changes nothing).

[F3]

The vertex set of $G_{1} [a \to G_{2}]$ is $(V (G_{1}) ∖ {a}) \cup V (G_{2})$ , a disjoint union; two vertices of $V (G_{1}) ∖ {a}$ are adjacent there exactly when they are adjacent in $G_{1}$ , two vertices of $V (G_{2})$ exactly when they are adjacent in $G_{2}$ , and $u \in V (G_{1}) ∖ {a}$ is adjacent to $x \in V (G_{2})$ exactly when $u$ is adjacent to $a$ in $G_{1}$ (Substituting one graph for a vertex of another).

[L2]

[F4]

$G [W] = (W, E (G) \cap [W]^{2})$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F5]

A graph isomorphism is a bijection $φ : V \to W$ such that, for all distinct $u, v \in V$ , ${u, v} \in E$ if and only if ${φ (u), φ (v)} \in F$ (Graph isomorphisms, automorphisms and graph complements).

[F6]

A bijection transports finiteness and cardinality: if $A$ is finite and $f : A \to B$ is a bijection then $∣ B ∣ = ∣ A ∣$ (The cardinality $∣ A ∣$ of a finite set).

Proof

technique · direct

1.1F2F5F6

Let $θ : V (H) \to V (G)$ be an isomorphism and let $M$ be a module of $H$ . For $v \in V (G) ∖ θ [M]$ the vertex $θ^{- 1} (v)$ lies outside $M$ , so it is adjacent in $H$ to every vertex of $M$ or to none; since $θ$ preserves and reflects adjacency, $v$ is adjacent in $G$ to every vertex of $θ [M]$ or to none. Hence $θ [M]$ is a module of $G$ , and $∣ θ [M] ∣ = ∣ M ∣$ , $∣ V (G) ∣ = ∣ V (H) ∣$ and $θ [M] = V (G)$ exactly when $M = V (H)$ .

1.2L1F3given

For the direction from a substitution to non-primality, suppose $G ≅ G_{1} [a \to G_{2}]$ with $∣ V (G_{1}) ∣ \geq 2$ and $∣ V (G_{2}) ∣ \geq 2$ , and write $H = G_{1} [a \to G_{2}]$ and $M = V (G_{2})$ . Then $M$ is a module of $H$ by [L1], $∣ M ∣ \geq 2$ , and $V (H) ∖ M = V (G_{1}) ∖ {a}$ is nonempty because $∣ V (G_{1}) ∣ \geq 2$ , so $M \neq V (H)$ .

1.3F1F4choose

For the converse direction, suppose $G$ is not prime, so by [F1] it has a module $M$ with $2 \leq ∣ M ∣$ and $∣ M ∣ \leq ∣ V (G) ∣ - 1$ ; fix $x \in M$ and put $G_{2} = G [M]$ and $G_{1} = G [(V (G) ∖ M) \cup {x}]$ .

2.1step 1.1step 1.2F1F6

In the first direction, step 1.1 applied to an isomorphism $H \to G$ turns $M$ into a module $M^{'}$ of $G$ with $∣ M^{'} ∣ = ∣ M ∣ \geq 2$ and $M^{'} \neq V (G)$ , so $∣ M^{'} ∣ \leq ∣ V (G) ∣ - 1$ and $G$ is not prime by [F1].

2.2step 1.3F3F6

In the converse direction, $V (G_{1}) ∖ {x} = V (G) ∖ M$ is disjoint from $V (G_{2}) = M$ and is nonempty because $∣ M ∣ \leq ∣ V (G) ∣ - 1$ , and $V (G_{2}) \neq \emptyset$ ; so $G_{1} [x \to G_{2}]$ is a substitution, its vertex set is $(V (G) ∖ M) \cup M = V (G)$ , and $∣ V (G_{2}) ∣ = ∣ M ∣ \geq 2$ while $∣ V (G_{1}) ∣ = ∣ V (G) ∖ M ∣ + 1 \geq 2$ .

3.1step 1.3step 2.2F3F4L2

Still in the converse direction, take distinct $p, q \in V (G)$ . If both lie in $V (G) ∖ M$ then ${p, q}$ is an edge of $G_{1} [x \to G_{2}]$ exactly when it is an edge of $G_{1}$ , hence exactly when it is an edge of $G$ ; if both lie in $M$ the same holds with $G_{2}$ in place of $G_{1}$ ; and if $p \in V (G) ∖ M$ and $q \in M$ then ${p, q}$ is an edge of $G_{1} [x \to G_{2}]$ exactly when ${p, x} \in E (G_{1})$ , that is exactly when ${p, x} \in E (G)$ , which by [L2] applied to the module $M$ with $x, q \in M$ and $p \notin M$ holds exactly when ${p, q} \in E (G)$ .

4.1step 2.2step 3.1

So in the converse direction $G_{1} [x \to G_{2}]$ and $G$ have the same vertex set and the same edges, hence $G = G_{1} [x \to G_{2}]$ is a substitution with both factors on at least two vertices.

5.1step 2.1step 4.1∎

Step 2.1 shows that a graph isomorphic to such a substitution is not prime, and step 4.1 shows that a graph that is not prime is such a substitution; these are the two directions of the stated equivalence.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

Modular partitions and the quotient graph they define

Definition

Let $G$ be a finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets). A modular partition of $G$ is a set $P$ of nonempty modules of $G$ (Modules of a graph, and the trivial modules) that are pairwise disjoint and whose union is $V (G)$ . Its members are its parts. Since the parts are nonempty and pairwise disjoint subsets of the finite set $V (G)$ , there are finitely many of them (The cardinality $∣ A ∣$ of a finite set).

The quotient graph $G / P$ has vertex set $P$ , and for distinct parts $M, N \in P$ ,

${M, N} \in E (G / P) : ⟺ (M, N) is a complete pair in G$

(Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

Why this is a definition and not a wish. Two distinct parts are disjoint nonempty modules, so the pair they form is complete or anticomplete and not both (Two disjoint nonempty modules form a complete or an anticomplete pair). The displayed condition is therefore a genuine dichotomy: for each unordered pair of distinct parts exactly one of "complete" and "anticomplete" holds, and $E (G / P)$ is a well-defined set of two-element subsets of $P$ . Hence $G / P$ is a finite simple graph.

The partition of $V (G)$ into singletons is modular, and its quotient is $G$ itself up to the renaming $v \mapsto {v}$ ; when $V (G) \neq \emptyset$ the partition ${V (G)}$ is modular too, and its quotient is the one-vertex graph. The induced subgraphs $G [M]$ on the parts (Subgraphs, induced subgraphs and spanning subgraphs) carry the information the quotient discards.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

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

Statement

Let $P$ be a modular partition of a finite simple graph $G$ , let $X \subseteq P$ , and let $U = ⋃_{M \in X} M$ . Then $X$ is a module of $G / P$ if and only if $U$ is a module of $G$ .

Facts & Assumptions

Given: A modular partition $P$ of a finite simple graph $G$ , a subset $X \subseteq P$ , and the union $U = ⋃_{M \in X} M$ .

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

[F2]

A modular partition of $G$ is a set of nonempty, pairwise disjoint modules of $G$ whose union is $V (G)$ ; the quotient $G / P$ has vertex set $P$ , with distinct parts $M, N$ adjacent exactly when $(M, N)$ is a complete pair in $G$ (Modular partitions and the quotient graph they define).

[L1]

Two disjoint nonempty modules of $G$ form a complete or an anticomplete pair, and not both (Two disjoint nonempty modules form a complete or an anticomplete pair).

[F3]

Proof

technique · direct

1.1F2

Since the parts are nonempty, pairwise disjoint and cover $V (G)$ , a vertex $v$ lies outside $U$ exactly when the unique part $N$ containing it lies outside $X$ ; and $N$ is then disjoint from every $M \in X$ .

1.2L1F3F2

For $N \in P ∖ X$ , $M \in X$ and $v \in N$ , the pair $(N, M)$ is complete or anticomplete by [L1]; it is complete exactly when $v$ is adjacent to every vertex of $M$ , and anticomplete exactly when $v$ is adjacent to no vertex of $M$ , because $M$ and $N$ are nonempty and the alternative is excluded.

2.1step 1.1step 1.2F1F2

For the forward direction, assume $X$ is a module of $G / P$ and let $v \in V (G) ∖ U$ , lying in the part $N \notin X$ of step 1.1. Then $N$ is adjacent in $G / P$ to every member of $X$ or to none. In the first case every $(N, M)$ with $M \in X$ is complete, so by step 1.2 the vertex $v$ is adjacent to every vertex of $U$ ; in the second case every such $(N, M)$ is anticomplete, so $v$ is adjacent to no vertex of $U$ .

2.2step 1.1step 1.2F1F2choose

For the converse direction, assume $U$ is a module of $G$ and let $N \in P ∖ X$ , which is a vertex of $G / P$ outside $X$ . Choose $v \in N$ ; then $v \notin U$ by step 1.1, so $v$ is adjacent to every vertex of $U$ or to no vertex of $U$ . In the first case step 1.2 makes every pair $(N, M)$ with $M \in X$ complete, so $N$ is adjacent in $G / P$ to every member of $X$ ; in the second case every such pair is anticomplete, so $N$ is adjacent to none of them.

3.1step 2.1step 2.2F1F3∎

Step 2.1 makes $({v}, U)$ pure for every $v \in V (G) ∖ U$ , so $U$ is a module of $G$ , and step 2.2 makes $({N}, X)$ pure in $G / P$ for every part $N$ outside $X$ , so $X$ is a module of $G / P$ ; together these are the two directions of the equivalence.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

A graph is recovered from any modular partition by the induced subgraphs on the parts together with the quotient graph

Statement

Let $P$ be a modular partition of a finite simple graph $G$ , and let $x, y$ be distinct vertices of $G$ , lying in the parts $M, N \in P$ respectively. Then

if $M \neq N$ : ${x, y} \in E (G)$ if and only if ${M, N} \in E (G / P)$ ;
if $M = N$ : ${x, y} \in E (G)$ if and only if ${x, y} \in E (G [M])$ .

Consequently $E (G)$ is determined by $G / P$ together with the induced subgraphs $G [M]$ for $M \in P$ . In particular, if $P = {M_{1}, M_{2}}$ has exactly the two parts $M_{1}, M_{2}$ and $t \in M_{2}$ , then $G = G [M_{1} \cup {t}] [t \to G [M_{2}]]$ .

Facts & Assumptions

Given: A modular partition $P$ of a finite simple graph $G$ , and distinct vertices $x \in M$ and $y \in N$ with $M, N \in P$ .

[F1]

[L1]

Two disjoint nonempty modules of $G$ form a complete or an anticomplete pair, and not both (Two disjoint nonempty modules form a complete or an anticomplete pair).

[F2]

[F3]

$G [W] = (W, E (G) \cap [W]^{2})$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F4]

[L2]

[F5]

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

Proof

technique · cases

1.1assume-case acrossF1L1F2

First case: $M \neq N$ . The parts are disjoint nonempty modules, so $(M, N)$ is complete or anticomplete and not both; if it is complete then ${x, y} \in E (G)$ , and if it is anticomplete then ${x, y} \notin E (G)$ . Since ${M, N} \in E (G / P)$ says exactly that $(M, N)$ is complete, the two conditions agree.

1.2assume-case insideF3

Second case: $M = N$ . Then $x, y$ are distinct vertices of $M$ , and the edges of $G [M]$ are the edges of $G$ with both ends in $M$ , so ${x, y} \in E (G)$ if and only if ${x, y} \in E (G [M])$ .

1.3F1F3F4choose

Suppose now that $P = {M_{1}, M_{2}}$ with $M_{1} \neq M_{2}$ , fix $t \in M_{2}$ and put $G_{1} = G [M_{1} \cup {t}]$ and $G_{2} = G [M_{2}]$ . Then $V (G_{1}) ∖ {t} = M_{1}$ is disjoint from $V (G_{2}) = M_{2}$ , and $M_{2} \neq \emptyset$ , so $G_{1} [t \to G_{2}]$ is a substitution with vertex set $M_{1} \cup M_{2} = V (G)$ .

2.1step 1.1step 1.2F1cases-exhaustive

Every pair of distinct vertices of $G$ falls into exactly one of the two cases, since each vertex lies in exactly one part, so the cases are exhaustive and steps 1.1 and 1.2 determine $E (G)$ from $G / P$ and the graphs $G [M]$ .

2.2step 1.3F3F4L2F5

In the two-part situation of step 1.3, take distinct $p, q \in V (G)$ . If $p, q \in M_{1}$ , then ${p, q}$ is an edge of $G_{1} [t \to G_{2}]$ exactly when it is an edge of $G_{1}$ , hence exactly when it is an edge of $G$ ; if $p, q \in M_{2}$ the same holds through $G_{2}$ ; and if $p \in M_{1}$ and $q \in M_{2}$ , then ${p, q}$ is an edge of $G_{1} [t \to G_{2}]$ exactly when ${p, t} \in E (G_{1})$ , that is exactly when ${p, t} \in E (G)$ , which by [L2] applied to the module $M_{2}$ with $t, q \in M_{2}$ and $p \notin M_{2}$ holds exactly when ${p, q} \in E (G)$ .

3.1step 2.1step 2.2∎

So in the two-part situation the graphs $G$ and $G [M_{1} \cup {t}] [t \to G [M_{2}]]$ have the same vertex set and the same edges, and are therefore equal; with step 2.1 this proves every clause of the Statement.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The quotient by a modular partition is isomorphic to the subgraph induced by any set meeting each part exactly once

Statement

Let $P$ be a modular partition of a finite simple graph $G$ and let $T \subseteq V (G)$ meet every part of $P$ in exactly one vertex. Then $G [T] ≅ G / P$ . Such a set $T$ exists, so the quotient is isomorphic to an induced subgraph of $G$ .

Facts & Assumptions

Given: A modular partition $P$ of a finite simple graph $G$ , and a set $T \subseteq V (G)$ with $∣ M \cap T ∣ = 1$ for every $M \in P$ .

[F1]

A modular partition of $G$ is a set of nonempty, pairwise disjoint modules of $G$ whose union is $V (G)$ ; the quotient $G / P$ has vertex set $P$ , with distinct parts $M, N$ adjacent exactly when $(M, N)$ is a complete pair in $G$ ; and $P$ is finite (Modular partitions and the quotient graph they define, A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

[L1]

Two disjoint nonempty modules of $G$ form a complete or an anticomplete pair, and not both (Two disjoint nonempty modules form a complete or an anticomplete pair).

[F2]

[F3]

$G [T] = (T, E (G) \cap [T]^{2})$ , so two vertices of $T$ are adjacent in $G [T]$ exactly when they are adjacent in $G$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F4]

[F5]

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

Proof

technique · direct

1.1F1givenconstruct

Define $φ : P \to T$ by letting $φ (M)$ be the unique vertex of $M \cap T$ . This is injective, because distinct parts are disjoint and $φ (M) \in M$ ; and it is surjective, because every $t \in T$ lies in exactly one part $M$ , and then $t \in M \cap T$ , so $t = φ (M)$ .

1.2L1F2F5given

Let $M, N \in P$ be distinct. The pair $(M, N)$ is complete or anticomplete and not both, so if it is complete then $φ (M) φ (N) \in E (G)$ , and if it is anticomplete then $φ (M) φ (N) \notin E (G)$ .

2.1step 1.2F1F3

By the definition of the quotient, ${M, N} \in E (G / P)$ says exactly that $(M, N)$ is complete, so step 1.2 gives ${M, N} \in E (G / P)$ if and only if ${φ (M), φ (N)} \in E (G)$ ; and since $φ (M), φ (N) \in T$ , that is the same as ${φ (M), φ (N)} \in E (G [T])$ .

3.1step 1.1step 2.1F4

So $φ$ is a bijection from $V (G / P) = P$ onto $T = V (G [T])$ that preserves and reflects adjacency, hence an isomorphism $G / P \to G [T]$ .

4.1step 3.1F1choose∎

A set $T$ as in the Statement exists: the parts are nonempty and there are finitely many of them, so selecting one vertex from each is a choice from a finite family of nonempty sets and needs no further principle. Hence the quotient is isomorphic to an induced subgraph of $G$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

In a connected and anticonnected graph, the union of two proper modules that meet is again a proper module

Statement

Let $G$ be a finite simple graph that is both connected and anticonnected, and let $M, N$ be proper modules of $G$ with $M \cap N \neq \emptyset$ . Then $M \cup N$ is a proper module of $G$ .

Facts & Assumptions

Given: A connected and anticonnected finite simple graph $G$ , and proper modules $M, N$ of $G$ with $M \cap N \neq \emptyset$ .

[F1]

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

[L1]

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

[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]

For a module $N$ of $G$ : for all $p, q \in N$ and all $x \in V (G) ∖ N$ , $x p \in E (G)$ if and only if $x q \in E (G)$ (Three equivalent descriptions of a module: purity of every outside vertex, equality of outside neighbourhoods, and indistinguishability of the members).

[F2]

$G$ is anticonnected when $\overline{G}$ is connected, and $\overline{G}$ has the same vertex set as $G$ (Anticonnected graphs and anticonnected components, Connected graphs and connected components defined by the existence of vertex paths, Graph isomorphisms, automorphisms and graph complements).

[F3]

A disjoint pair is complete when every cross pair is an edge and anticomplete when no cross pair is an edge; distinct vertices are adjacent in $\overline{G}$ exactly when they are not adjacent in $G$ (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs, Graph isomorphisms, automorphisms and graph complements).

Proof

technique · contradiction

1.1L1assume-contragiven

The set $M \cup N$ is a module of $G$ by [L1], since $M \cap N \neq \emptyset$ . Suppose for contradiction that $M \cup N = V (G)$ .

1.2F1given

The set $M$ is nonempty, since it contains a vertex of $M \cap N$ , and $M \neq V (G)$ because $M$ is proper.

2.1step 1.1F1

If $M ∖ N$ were empty then $M \subseteq N$ , so $N = M \cup N = V (G)$ by step 1.1, which is false because $N$ is proper; hence $M ∖ N \neq \emptyset$ , and $V (G) ∖ M = N ∖ M$ , again by step 1.1.

2.2step 1.2L2given

Since $G$ is connected and $M$ is a module with $\emptyset \neq M \neq V (G)$ , some vertex $v \in V (G) ∖ M$ is complete to $M$ .

2.3step 1.2L2L3F2F3

The set $M$ is a module of $\overline{G}$ as well, and $\overline{G}$ is connected with the same vertex set as $G$ , so some vertex $v^{'} \in V (G) ∖ M$ is complete to $M$ in $\overline{G}$ ; that is, $v^{'}$ is adjacent in $G$ to no vertex of $M$ .

3.1step 2.1step 2.2step 2.3L4choose

Choose $x \in M ∖ N$ . Then $x \notin N$ , while $v$ and $v^{'}$ both lie in $V (G) ∖ M = N ∖ M \subseteq N$ , so [L4] applied to the module $N$ gives that $x v \in E (G)$ if and only if $x v^{'} \in E (G)$ .

4.1step 1.1step 3.1F3discharge-contradiction∎

But $v$ is complete to $M$ and $x \in M$ , so $x v \in E (G)$ , while $v^{'}$ is adjacent to no vertex of $M$ , so $x v^{'} \notin E (G)$ ; this contradicts step 3.1. Hence $M \cup N \neq V (G)$ , and being a module it is a proper module.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

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

Statement

Let $G$ be a connected and anticonnected finite simple graph with $∣ V (G) ∣ \geq 2$ . For $v \in V (G)$ write $M (v)$ for the set of proper modules of $G$ containing $v$ . Then $M (v)$ has a member $M (v)$ that contains every member of $M (v)$ ; it is the largest proper module containing $v$ . Moreover, for $u, v \in V (G)$ either $M (u) = M (v)$ or $M (u) \cap M (v) = \emptyset$ ; and every vertex $v$ lies in $M (v)$ , so the sets $M (v)$ cover $V (G)$ .

Facts & Assumptions

Given: A connected and anticonnected finite simple graph $G$ with $∣ V (G) ∣ \geq 2$ , and a vertex $v \in V (G)$ .

[F1]

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

[L1]

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

[L2]

Every subset of a finite set is finite, has cardinality at most that of the set, and has that cardinality only if it is the whole set (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ).

[L3]

Every nonempty subset of $N$ has a least element (The well-ordering principle).

[F2]

The cardinality $∣ A ∣$ of a finite set is a natural number (The cardinality $∣ A ∣$ of a finite set).

Proof

technique · direct

1.1F1given

The singleton ${v}$ is a module of $G$ , and ${v} \neq V (G)$ because $∣ V (G) ∣ \geq 2$ , so ${v} \in M (v)$ and $M (v)$ is nonempty.

1.2L2F2

Every member of $M (v)$ is a subset of the finite set $V (G)$ , so its cardinality is a natural number at most $∣ V (G) ∣$ .

2.1step 1.1step 1.2L3choose

The set ${∣ V (G) ∣ - ∣ M ∣ : M \in M (v)}$ is a nonempty subset of $N$ by steps 1.1 and 1.2, so it has a least element; a member $M^{*} \in M (v)$ attaining it has $∣ M ∣ \leq ∣ M^{*} ∣$ for every $M \in M (v)$ .

3.1step 2.1L1F1

Let $M \in M (v)$ . Both $M$ and $M^{*}$ are proper modules containing $v$ , so they meet, and [L1] makes $M \cup M^{*}$ a proper module; it contains $v$ , so it lies in $M (v)$ and step 2.1 gives $∣ M \cup M^{*} ∣ \leq ∣ M^{*} ∣$ .

4.1step 3.1L2

Since $M^{*} \subseteq M \cup M^{*}$ and the two have equal cardinality by step 3.1 and [L2], they are equal, so $M \subseteq M^{*}$ . Writing $M (v) = M^{*}$ , this is a proper module containing $v$ and containing every proper module that contains $v$ .

5.1step 4.1L1∎

If $M (u) \cap M (v) \neq \emptyset$ then $M (u) \cup M (v)$ is a proper module by [L1]; it contains $u$ , so step 4.1 gives $M (u) \cup M (v) \subseteq M (u)$ and hence $M (v) \subseteq M (u)$ , and by symmetry $M (u) \subseteq M (v)$ , so $M (u) = M (v)$ . Otherwise the two are disjoint, and every vertex $v$ lies in $M (v)$ .

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

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

Statement

Let $G$ be a finite simple graph with $∣ V (G) ∣ \geq 2$ . Then exactly one of the following holds.

$G$ is disconnected. The vertex sets of its connected components form a modular partition of $G$ , and the quotient by that partition has no edge.
$\overline{G}$ is disconnected. The anticomponents of $G$ form a modular partition of $G$ , and the quotient by that partition has every pair of distinct vertices as an edge.
$G$ and $\overline{G}$ are both connected. The maximal proper modules $M (v)$ , $v \in V (G)$ , form a modular partition of $G$ with at least two parts, and the quotient by that partition is prime.

Facts & Assumptions

Given: A finite simple graph $G$ with $∣ V (G) ∣ \geq 2$ .

[L1]

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

[L2]

Every union of vertex sets of connected components is a module, with every outside vertex anticomplete to it, and every union of anticomponents is a module, with every outside vertex complete to it (Every union of connected components is a module, and so is every union of anticonnected components).

[L3]

Every finite graph with at least two vertices is connected or anticonnected (Every graph with at least two vertices is connected or anticonnected, Anticonnected graphs and anticonnected components).

[F1]

[L4]

For a modular partition $P$ and $X \subseteq P$ , the set $X$ is a module of $G / P$ if and only if $⋃_{M \in X} M$ 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).

[F2]

$G$ is prime when every module of $G$ is trivial, the trivial modules being $\emptyset$ , the singletons and the whole vertex set (Prime graphs: those whose only modules are the trivial ones, Modules of a graph, and the trivial modules).

[L5]

The vertex sets of the connected components are nonempty, cover $V (G)$ , and any two are equal or disjoint; a graph is disconnected when it has a vertex and two of its vertices are joined by no path, and then it has at least two components (The connected components of a graph partition its vertex set and are its maximal connected subgraphs, Connected graphs and connected components defined by the existence of vertex paths).

[L6]

The anticomponents of $G$ are exactly the vertex sets of the connected components of $\overline{G}$ , and they partition $V (G)$ (The anticonnected components of $G$ are exactly the connected components of $\overline{G}$ ).

[L7]

Distinct connected components are anticomplete to one another, and distinct anticomponents are complete to one another (Distinct connected components are anticomplete, and distinct anticonnected components are complete).

Proof

technique · cases

1.1L3

By [L3] the graph is connected or anticonnected, so it is not the case that both $G$ and $\overline{G}$ are disconnected; the three listed situations are therefore mutually exclusive, and they are exhaustive because $G$ is disconnected, or $\overline{G}$ is disconnected, or both are connected.

1.2assume-case discL2L5F1

First case: $G$ is disconnected. By [L5] the vertex sets of its components are nonempty, pairwise disjoint and cover $V (G)$ , and by [L2] each is a module, so they form a modular partition $P$ .

1.3assume-case codiscL2L6F1

Second case: $\overline{G}$ is disconnected, that is, $G$ is not anticonnected. By [L6] the anticomponents are nonempty, pairwise disjoint and cover $V (G)$ , and by [L2] each is a module, so they form a modular partition $Q$ .

1.4assume-case bothL1F1

Third case: $G$ and $\overline{G}$ are both connected, so $G$ is connected and anticonnected. By [L1] the sets $M (v)$ are proper modules, pairwise equal or disjoint, and cover $V (G)$ ; they are nonempty since $v \in M (v)$ , so the distinct ones form a modular partition $R$ .

2.1step 1.2L7F1

In the first case, distinct components are anticomplete to one another by [L7], so no pair of distinct parts of $P$ is complete and the quotient $G / P$ has no edge.

2.2step 1.3L7F1

In the second case, distinct anticomponents are complete to one another by [L7], so every pair of distinct parts of $Q$ is complete and every pair of distinct vertices of $G / Q$ is an edge.

2.3step 1.4L1F1

In the third case $R$ has at least two parts: a single part would be $M (v) = V (G)$ for some $v$ , contradicting that $M (v)$ is proper.

3.1step 1.4step 2.3L4F1

Still in the third case, let $X$ be a module of $G / R$ that is neither $\emptyset$ nor $R$ , and put $U = ⋃_{M \in X} M$ . By [L4] the set $U$ is a module of $G$ , and $U \neq V (G)$ because some part outside $X$ is nonempty and disjoint from $U$ , so $U$ is a proper module.

4.1step 3.1L1F1choose

Choose $M \in X$ , possible because $X \neq \emptyset$ , and $x \in M$ , possible because parts are nonempty. Then $M = M (u)$ for some $u$ , and $M (x)$ meets $M (u)$ at $x$ , so $M (x) = M$ by [L1]; the set $U$ is a proper module containing $x$ , so maximality gives $U \subseteq M (x) = M$ . Every $M^{'} \in X$ therefore satisfies $M^{'} \subseteq M$ , and a part distinct from $M$ is disjoint from $M$ and nonempty, so no such part lies in $X$ : that is, $X = {M}$ .

5.1step 1.1step 2.1step 2.2step 2.3step 4.1F2cases-exhaustive∎

So in the third case every module of $G / R$ is $\emptyset$ , a singleton or all of $R$ , that is, $G / R$ is prime; with steps 1.1, 2.1, 2.2 and 2.3 this proves all three clauses and their mutual exclusion.

CorollaryStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

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]

[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$ .

CorollaryStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

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) ∣ \geq 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) ∣ \geq 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 \in V (G) ∖ M$ , and $M$ is proper when $M \neq 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]

[L2]

[L3]

[L4]

The maximal proper modules of such a graph 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).

Proof

technique · direct

1.1F1F2given

Every part $N \in P$ is a nonempty module of $G$ , and $N \neq 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 $M_{0} \in P$ and $x \in M_{0}$ , and let $M (x)$ be the largest proper module of $G$ containing $x$ . Then $M_{0} \subseteq M (x)$ by step 1.1 and the maximality in [L3].

3.1step 1.1step 2.1L2L3

Let $X = {N \in P : N \cap M (x) \neq \emptyset}$ and let $N \in X$ . Both $N$ and $M (x)$ are proper modules and they meet, so $N \cup M (x)$ is a proper module by [L2]; it contains $x$ , so [L3] gives $N \cup M (x) \subseteq M (x)$ and hence $N \subseteq 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 \in X} N$ .

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 $M_{0} \in 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 $M_{0}$ , whence $M (x) = M_{0}$ .

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.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

$hom (G [W]) \leq hom (G)$ for every vertex subset $W$

Statement

Let $G$ be a finite simple graph and $W \subseteq V (G)$ . Then $ω (G [W]) \leq ω (G)$ , $α (G [W]) \leq α (G)$ , and consequently $hom (G [W]) \leq hom (G)$ .

Facts & Assumptions

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

[F1]

A set $X \subseteq V (G)$ is a clique when every two distinct vertices of $X$ are adjacent and a stable set when no two distinct vertices of $X$ are adjacent; $ω (G)$ and $α (G)$ are the largest cardinalities of a clique and of a stable set (Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[F2]

$hom (G) = \max {ω (G), α (G)}$ (Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

[F3]

$G [W] = (W, E (G) \cap [W]^{2})$ , so two vertices of $W$ are adjacent in $G [W]$ exactly when they are adjacent in $G$ (Subgraphs, induced subgraphs and spanning subgraphs).

Proof

technique · direct

1.1F1F3

Let $X \subseteq W$ be a clique of $G [W]$ . Every two distinct vertices of $X$ are adjacent in $G [W]$ , hence adjacent in $G$ , so $X$ is a clique of $G$ .

1.2F1F3

Let $X \subseteq W$ be a stable set of $G [W]$ . No two distinct vertices of $X$ are adjacent in $G [W]$ , hence none are adjacent in $G$ , so $X$ is a stable set of $G$ .

2.1step 1.1step 1.2F1

Every clique of $G [W]$ is therefore a clique of $G$ , so the largest cardinality of a clique of $G [W]$ is at most that of a clique of $G$ : $ω (G [W]) \leq ω (G)$ . The same argument with step 1.2 gives $α (G [W]) \leq α (G)$ .

3.1step 2.1F2algebra∎

Taking the larger of the two numbers on each side, $hom (G [W]) = \max {ω (G [W]), α (G [W])} \leq \max {ω (G), α (G)} = hom (G)$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

If $ϵ$ is an Erdős–Hajnal constant for $H$ and $W$ is a nonempty vertex set with $∣ W ∣^{ϵ} > hom (G)$ , then $G [W]$ has an induced copy of $H$

Statement

Let $H$ be a finite simple graph and let $ϵ > 0$ be an Erdős–Hajnal constant for the hereditary class of $H$ -free graphs. Let $G$ be a finite simple graph and let $W \subseteq V (G)$ be nonempty with $∣ W ∣^{ϵ} > hom (G)$ . Then $G [W]$ has an induced copy of $H$ .

Facts & Assumptions

Given: A finite simple graph $H$ , an Erdős–Hajnal constant $ϵ > 0$ for the class of $H$ -free graphs, a finite simple graph $G$ , and a nonempty $W \subseteq V (G)$ with $∣ W ∣^{ϵ} > hom (G)$ .

[F1]

A real $ϵ > 0$ is an Erdős–Hajnal constant for a hereditary class $C$ when every nonempty $J \in C$ satisfies $hom (J) \geq ∣ V (J) ∣^{ϵ}$ (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class, Real powers for positive bases, with the zero-base positive-exponent convention).

[F2]

$G$ is $H$ -free when $G$ has no induced copy of $H$ ( $H$ -free and $F$ -free graphs under the induced-subgraph convention, Induced embeddings and induced copies of a graph).

[L1]

For every family $F$ of finite graphs, the class of $F$ -free finite graphs is hereditary (Every class defined by forbidden induced subgraphs is hereditary).

[L2]

$hom (G [W]) \leq hom (G)$ for every $W \subseteq V (G)$ ( $hom (G [W]) \leq hom (G)$ for every vertex subset $W$ ).

[F3]

$hom (G) = \max {ω (G), α (G)}$ (Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

[F4]

$G [W]$ has vertex set $W$ (Subgraphs, induced subgraphs and spanning subgraphs).

Proof

technique · contrapositive

1.1contrapositive-reduce

It suffices to prove the contrapositive: if $G [W]$ has no induced copy of $H$ , then $∣ W ∣^{ϵ} \leq hom (G)$ .

1.2assume-hypF2L1

Assume $G [W]$ has no induced copy of $H$ . Then $G [W]$ is $H$ -free, and the class of $H$ -free graphs is hereditary, so $G [W]$ is a member of the class for which $ϵ$ is an Erdős–Hajnal constant.

2.1step 1.2F1F3F4given

The graph $G [W]$ is nonempty, since $W \neq \emptyset$ and $V (G [W]) = W$ , so [F1] applies to it and gives $hom (G [W]) \geq ∣ W ∣^{ϵ}$ .

3.1step 2.1L2discharge-contrapositive∎

By [L2] we have $hom (G) \geq hom (G [W])$ , so $hom (G) \geq ∣ W ∣^{ϵ}$ , which is the conclusion of the contrapositive; the Statement follows.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-26Open item page →

If every $m$ -element vertex set contains an induced copy of $H$ , then at least $(\binom{n}{h}) / (\binom{m}{h})$ of the $h$ -element vertex sets induce a copy of $H$

Statement

Let $H$ be a finite simple graph with $h = ∣ V (H) ∣ \geq 1$ , let $G$ be a finite simple graph with $n = ∣ V (G) ∣$ , and let $m$ be a natural number with $h \leq m \leq n$ . Suppose every $W \subseteq V (G)$ with $∣ W ∣ = m$ has a subset $S \subseteq W$ with $∣ S ∣ = h$ and $G [S] ≅ H$ . Let $g$ be the number of sets $S \subseteq V (G)$ with $∣ S ∣ = h$ and $G [S] ≅ H$ . Then

$g \geq \frac{(\binom{n}{h})}{(\binom{m}{h})} \geq \frac{(n - h + 1)^{h}}{m^{h}} .$

Facts & Assumptions

Given: Finite simple graphs $H$ and $G$ with $h = ∣ V (H) ∣ \geq 1$ and $n = ∣ V (G) ∣$ , a natural number $m$ with $h \leq m \leq n$ , and the hypothesis that every $m$ -element $W \subseteq V (G)$ has an $h$ -element subset $S$ with $G [S] ≅ H$ .

[F1]

For a finite set $A$ and $k \in N$ , $[A]^{k}$ is the set of $k$ -element subsets of $A$ , it is finite, and $∣ [A]^{k} ∣ = (\binom{∣ A ∣}{k})$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , The cardinality $∣ A ∣$ of a finite set).

[L1]

For finite sets $X, Y$ and a relation $R \subseteq X \times Y$ with row fibres $R_{x}$ and column fibres $R^{y}$ , one has $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets, A relation $R \subseteq X \times Y$ between finite sets, its row fibres $R_{x}$ and its column fibres $R^{y}$ ).

[F2]

For a finite index set $S$ and a constant $c$ , $\sum_{i \in S} c = ∣ S ∣ \cdot c$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form).

[L2]

Every subset of a finite set is finite, and its cardinality is at most that of the set (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ).

[L3]

For $k \leq N$ one has $(\binom{N}{k}) \cdot k! = N^{\underline{k}}$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

[F3]

$N^{\underline{0}} = 1$ and $N^{\underline{k + 1}} = N^{\underline{k}} \cdot (N - k)$ , so for $k \leq N$ the falling factorial $N^{\underline{k}}$ is the product $N (N - 1) \dots (N - k + 1)$ of the $k$ topmost factors (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[F4]

An induced copy of $H$ in $G$ is the image $G [φ (V (H))]$ of an induced embedding, and $G [S] = (S, E (G) \cap [S]^{2})$ (Induced embeddings and induced copies of a graph, Subgraphs, induced subgraphs and spanning subgraphs).

Proof

technique · direct

1.1F1F4L2

Write $G = {S \in [V (G)]^{h} : G [S] ≅ H}$ , so $g = ∣ G ∣$ , and let $R \subseteq [V (G)]^{m} \times [V (G)]^{h}$ consist of the pairs $(W, S)$ with $S \subseteq W$ , and $R^{'} \subseteq R$ of those with $S \in G$ . Both index sets are finite.

1.2F1L2

The row fibre of $R$ at $W$ is $[W]^{h}$ , of size $(\binom{m}{h})$ , and the column fibre of $R$ at $S$ is ${W \in [V (G)]^{m} : S \subseteq W}$ , which the map $W \mapsto W ∖ S$ carries bijectively onto $[V (G) ∖ S]^{m - h}$ , of size $(\binom{n - h}{m - h})$ .

1.3F1givenL2

The row fibre of $R^{'}$ at $W$ is ${S \in G : S \subseteq W}$ , which is nonempty by hypothesis, and the column fibre of $R^{'}$ at $S \in G$ is the same set as for $R$ , of size $(\binom{n - h}{m - h})$ , while the column fibre at $S \notin G$ is empty.

1.4L3F3algebra

By [L3] and [F3], $(\binom{n}{h}) h! = n^{\underline{h}} = n (n - 1) \dots (n - h + 1)$ and $(\binom{m}{h}) h! = m^{\underline{h}} = m (m - 1) \dots (m - h + 1)$ , so $(\binom{n}{h}) / (\binom{m}{h}) = n^{\underline{h}} / m^{\underline{h}}$ .

2.1step 1.1step 1.2L1F1F2

Double counting $R$ with the two fibre sizes of step 1.2 and the constant-summand rule gives $(\binom{n}{m}) (\binom{m}{h}) = ∣ R ∣ = (\binom{n}{h}) (\binom{n - h}{m - h})$ .

2.2step 1.1step 1.3L1F1F2algebra

Double counting $R^{'}$ gives $∣ R^{'} ∣ = \sum_{W} ∣ R_{W}^{'} ∣ \geq \sum_{W} 1 = (\binom{n}{m})$ , since every row fibre has at least one element, and also $∣ R^{'} ∣ = g (\binom{n - h}{m - h})$ by summing the column fibres of step 1.3 over $G$ .

2.3step 1.4F3algebra

Each of the $h$ factors of $n^{\underline{h}}$ is at least $n - h + 1 \geq 1$ and each of the $h$ factors of $m^{\underline{h}}$ is at most $m$ , and all of them are positive because $h \leq m \leq n$ ; hence $n^{\underline{h}} \geq (n - h + 1)^{h}$ and $m^{\underline{h}} \leq m^{h}$ , so $n^{\underline{h}} / m^{\underline{h}} \geq (n - h + 1)^{h} / m^{h}$ .

3.1step 2.1step 2.2F1algebra

Since $m - h \leq n - h$ and $h \leq m$ , the sets $[n - h]^{m - h}$ and $[m]^{h}$ are nonempty, so $(\binom{n - h}{m - h}) \geq 1$ and $(\binom{m}{h}) \geq 1$ ; dividing the inequality of step 2.2 by $(\binom{n - h}{m - h})$ and substituting step 2.1 gives $g \geq (\binom{n}{m}) / (\binom{n - h}{m - h}) = (\binom{n}{h}) / (\binom{m}{h})$ .

4.1step 3.1step 1.4step 2.3algebra∎

Combining steps 3.1, 1.4 and 2.3 gives $g \geq (\binom{n}{h}) / (\binom{m}{h}) \geq (n - h + 1)^{h} / m^{h}$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The induced copies of $H_{1}$ in $G$ are counted by summing, over the induced embeddings of $H_{1} - v$ , the number of vertices that extend them at $v$

Statement

Let $H_{1}$ be a finite simple graph with $h_{1} = ∣ V (H_{1}) ∣ \geq 1$ , let $v \in V (H_{1})$ , write $H_{1} - v$ for the induced subgraph $H_{1} [V (H_{1}) ∖ {v}]$ , and let $G$ be a finite simple graph with $n = ∣ V (G) ∣$ . For an induced embedding $φ$ of $H_{1} - v$ into $G$ define its extension set

$X_{φ} : = {u \in V (G) ∖ φ [V (H_{1}) ∖ {v}] : the map extending φ by v \mapsto u is an induced embedding of H_{1} into G} .$

Then, writing $Ψ$ for the set of induced embeddings of $H_{1} - v$ into $G$ ,

${ind}_{H_{1}} (G) = \sum_{φ \in Ψ} ∣ X_{φ} ∣, ∣ Ψ ∣ \leq n^{h_{1} - 1} .$

Facts & Assumptions

Given: A finite simple graph $H_{1}$ with $h_{1} = ∣ V (H_{1}) ∣ \geq 1$ , a vertex $v \in V (H_{1})$ , and a finite simple graph $G$ with $n = ∣ V (G) ∣$ ; the sets $Φ$ of induced embeddings of $H_{1}$ into $G$ and $Ψ$ of induced embeddings of $H_{1} - v$ into $G$ .

[F1]

An induced embedding of $H$ in $G$ is an injection $φ : V (H) \to V (G)$ such that, for all distinct $x, y \in V (H)$ , $x y \in E (H)$ if and only if $φ (x) φ (y) \in E (G)$ (Induced embeddings and induced copies of a graph).

[F2]

${ind}_{H} (G)$ is the number of induced embeddings of $H$ into $G$ (The induced-embedding count ${ind}_{H} (G)$ ).

[F3]

$H_{1} [W] = (W, E (H_{1}) \cap [W]^{2})$ , so two vertices of $W$ are adjacent in $H_{1} [W]$ exactly when they are adjacent in $H_{1}$ (Subgraphs, induced subgraphs and spanning subgraphs).

[L1]

[F4]

For a finite index set $S$ and a constant $c$ , $\sum_{i \in S} c = ∣ S ∣ \cdot c$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form).

[L2]

For finite sets $A$ and $B$ , the set $A^{B}$ of functions $B \to A$ is finite with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ (The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ ).

[L3]

Every subset of a finite set is finite, and its cardinality is at most that of the set (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , The cardinality $∣ A ∣$ of a finite set).

Proof

technique · direct

1.1F1F3

If $ψ \in Φ$ then its restriction $ψ^{'}$ to $V (H_{1}) ∖ {v}$ is injective, and for distinct $x, y \in V (H_{1}) ∖ {v}$ the condition $x y \in E (H_{1} - v)$ is the condition $x y \in E (H_{1})$ , which holds exactly when $ψ (x) ψ (y) \in E (G)$ ; so $ψ^{'} \in Ψ$ , and it is the only member of $Ψ$ that $ψ$ restricts to.

1.2F1L2L3

Let $R \subseteq Ψ \times Φ$ consist of the pairs $(φ, ψ)$ whose second entry restricts to the first. Both $Φ$ and $Ψ$ are sets of functions between finite sets, hence finite.

2.1step 1.1step 1.2F4

The column fibre of $R$ at $ψ \in Φ$ has exactly one element by step 1.1, so $\sum_{ψ \in Φ} ∣ R^{ψ} ∣ = ∣ Φ ∣$ .

2.2step 1.2F1given

The row fibre of $R$ at $φ \in Ψ$ is carried bijectively onto $X_{φ}$ by $ψ \mapsto ψ (v)$ : the map is injective because $ψ$ is determined by $φ$ together with $ψ (v)$ , and its image is exactly $X_{φ}$ , because a vertex $u$ arises as some $ψ (v)$ precisely when extending $φ$ by $v \mapsto u$ gives an induced embedding of $H_{1}$ , and injectivity of that extension is exactly the requirement $u \notin φ [V (H_{1}) ∖ {v}]$ .

3.1step 2.1step 2.2L1F2

Double counting $R$ therefore gives $\sum_{φ \in Ψ} ∣ X_{φ} ∣ = ∣ R ∣ = ∣ Φ ∣ = {ind}_{H_{1}} (G)$ .

4.1step 3.1F1L2L3∎

Every member of $Ψ$ is a function from $V (H_{1}) ∖ {v}$ , a set of $h_{1} - 1$ elements, to $V (G)$ , so $Ψ$ is a subset of a set of size $n^{h_{1} - 1}$ and $∣ Ψ ∣ \leq n^{h_{1} - 1}$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

An induced copy of $H_{2}$ inside the extension set of an induced embedding of $H_{1} - v$ yields an induced copy of $H_{1}$ with $H_{2}$ substituted for $v$

Statement

Let $H_{1}$ be a finite simple graph, $v \in V (H_{1})$ , and let $H_{2}$ be a finite simple graph for which $H : = H_{1} [v \to H_{2}]$ is defined. Let $G$ be a finite simple graph, let $φ$ be an induced embedding of $H_{1} - v$ into $G$ with extension set $X_{φ}$ (The induced copies of $H_{1}$ in $G$ are counted by summing, over the induced embeddings of $H_{1} - v$ , the number of vertices that extend them at $v$ ), and let $ψ$ be an induced embedding of $H_{2}$ into $G$ whose image is contained in $X_{φ}$ . Then the map $θ : V (H) \to V (G)$ that agrees with $φ$ on $V (H_{1}) ∖ {v}$ and with $ψ$ on $V (H_{2})$ is an induced embedding of $H$ into $G$ . In particular $G$ is not $H$ -free.

Facts & Assumptions

Given: Graphs $H_{1}$ , $H_{2}$ , $G$ as in the Statement, with $U = V (H_{1}) ∖ {v}$ , the substitution $H = H_{1} [v \to H_{2}]$ , the induced embedding $φ$ of $H_{1} - v$ into $G$ , and the induced embedding $ψ$ of $H_{2}$ into $G$ with $ψ [V (H_{2})] \subseteq X_{φ}$ .

[F1]

The vertex set of $H_{1} [v \to H_{2}]$ is $U \cup V (H_{2})$ , a disjoint union; two vertices of $U$ are adjacent there exactly when they are adjacent in $H_{1}$ , two vertices of $V (H_{2})$ exactly when they are adjacent in $H_{2}$ , and $x \in U$ is adjacent to $y \in V (H_{2})$ exactly when $x$ is adjacent to $v$ in $H_{1}$ (Substituting one graph for a vertex of another).

[F2]

An induced embedding of $J$ in $G$ is an injection $θ : V (J) \to V (G)$ such that, for all distinct $x, y \in V (J)$ , $x y \in E (J)$ if and only if $θ (x) θ (y) \in E (G)$ (Induced embeddings and induced copies of a graph). A graph is $J$ -free exactly when it has no induced copy of $J$ ( $H$ -free and $F$ -free graphs under the induced-subgraph convention).

[L1]

The extension set $X_{φ}$ consists of the vertices $u \in V (G) ∖ φ [U]$ for which the map extending $φ$ by $v \mapsto u$ is an induced embedding of $H_{1}$ into $G$ (The induced copies of $H_{1}$ in $G$ are counted by summing, over the induced embeddings of $H_{1} - v$ , the number of vertices that extend them at $v$ ).

[F3]

$H_{1} - v = H_{1} [U]$ , so two vertices of $U$ are adjacent in $H_{1} - v$ exactly when they are adjacent in $H_{1}$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F4]

A map is injective when equal values force equal arguments (Injection, surjection, bijection).

Proof

technique · cases

1.1F1F2F4L1given

The vertex set of $H$ is the disjoint union $U \cup V (H_{2})$ , so $θ$ is a well-defined map on $V (H)$ . It is injective: $φ$ and $ψ$ are injective, and their images are disjoint, because $ψ [V (H_{2})] \subseteq X_{φ}$ and every member of $X_{φ}$ lies outside $φ [U]$ .

1.2assume-case hostF1F2F3

First case: distinct $x, y \in U$ . Then $x y \in E (H)$ exactly when $x y \in E (H_{1})$ , which is exactly when $x y \in E (H_{1} - v)$ , which because $φ$ is an induced embedding of $H_{1} - v$ is exactly when $φ (x) φ (y) \in E (G)$ .

1.3assume-case insertedF1F2

Second case: distinct $x, y \in V (H_{2})$ . Then $x y \in E (H)$ exactly when $x y \in E (H_{2})$ , which because $ψ$ is an induced embedding of $H_{2}$ is exactly when $ψ (x) ψ (y) \in E (G)$ .

1.4assume-case crossF1F2L1given

Third case: $x \in U$ and $y \in V (H_{2})$ . The vertex $ψ (y)$ lies in $X_{φ}$ , so extending $φ$ by $v \mapsto ψ (y)$ is an induced embedding of $H_{1}$ ; applied to the pair $x, v$ of $H_{1}$ this gives that $x v \in E (H_{1})$ exactly when $φ (x) ψ (y) \in E (G)$ . And $x y \in E (H)$ exactly when $x v \in E (H_{1})$ .

2.1step 1.2step 1.3step 1.4F1cases-exhaustive

Every pair of distinct vertices of $H$ falls under exactly one of the three cases, because $U$ and $V (H_{2})$ are disjoint and cover $V (H)$ ; so in every case $x y \in E (H)$ holds exactly when $θ (x) θ (y) \in E (G)$ .

3.1step 1.1step 2.1F2∎

With the injectivity of step 1.1, the map $θ$ is therefore an induced embedding of $H$ into $G$ , so $G$ has an induced copy of $H$ and is not $H$ -free.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26Open item page →

Alon–Pach–Solymosi: if $H_{1}$ and $H_{2}$ have the Erdős–Hajnal property, so does the graph obtained from $H_{1}$ by substituting $H_{2}$ for a vertex

Statement

Let $H_{1}$ and $H_{2}$ be finite simple graphs with the Erdős–Hajnal property, let $v \in V (H_{1})$ , and suppose the substitution $H = H_{1} [v \to H_{2}]$ is defined (Substituting one graph for a vertex of another). Then $H$ has the Erdős–Hajnal property.

Facts & Assumptions

Given: Finite simple graphs $H_{1}, H_{2}$ with the Erdős–Hajnal property, a vertex $v \in V (H_{1})$ , and the substitution $H = H_{1} [v \to H_{2}]$ ; write $h = ∣ V (H_{1}) ∣$ , so $h \geq 1$ .

[F1]

A real $ϵ > 0$ is an Erdős–Hajnal constant for a hereditary class $C$ when every nonempty $J \in C$ satisfies $hom (J) \geq ∣ V (J) ∣^{ϵ}$ ; a finite graph $K$ has the Erdős–Hajnal property when the class of $K$ -free graphs has such a constant (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).

[F2]

$hom (G) = \max {ω (G), α (G)}$ , where $ω (G)$ and $α (G)$ are the largest cardinalities of a clique and of a stable set of $G$ (Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ , Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[F3]

$G$ is $K$ -free when $G$ has no induced copy of $K$ , an induced copy being the image of an induced embedding ( $H$ -free and $F$ -free graphs under the induced-subgraph convention, Induced embeddings and induced copies of a graph).

[L1]

For every family $F$ of finite graphs, the class of $F$ -free finite graphs is hereditary (Every class defined by forbidden induced subgraphs is hereditary).

[L2]

If $ϵ > 0$ is an Erdős–Hajnal constant for the class of $K$ -free graphs and $W \subseteq V (G)$ is nonempty with $∣ W ∣^{ϵ} > hom (G)$ , then $G [W]$ has an induced copy of $K$ (If $ϵ$ is an Erdős–Hajnal constant for $H$ and $W$ is a nonempty vertex set with $∣ W ∣^{ϵ} > hom (G)$ , then $G [W]$ has an induced copy of $H$ ).

[L3]

If $h \leq m \leq n = ∣ V (G) ∣$ and every $m$ -element $W \subseteq V (G)$ has an $h$ -element subset $S$ with $G [S] ≅ H_{1}$ , then the number of $h$ -element sets $S \subseteq V (G)$ with $G [S] ≅ H_{1}$ is at least $(n - h + 1)^{h} / m^{h}$ (If every $m$ -element vertex set contains an induced copy of $H$ , then at least $(\binom{n}{h}) / (\binom{m}{h})$ of the $h$ -element vertex sets induce a copy of $H$ ).

[L4]

With $Ψ$ the set of induced embeddings of $H_{1} - v$ into $G$ and $X_{φ}$ the extension set of $φ \in Ψ$ , one has ${ind}_{H_{1}} (G) = \sum_{φ \in Ψ} ∣ X_{φ} ∣$ and $∣ Ψ ∣ \leq n^{h - 1}$ (The induced copies of $H_{1}$ in $G$ are counted by summing, over the induced embeddings of $H_{1} - v$ , the number of vertices that extend them at $v$ ).

[L5]

If $φ \in Ψ$ and $ψ$ is an induced embedding of $H_{2}$ into $G$ whose image lies in $X_{φ}$ , then $G$ has an induced copy of $H = H_{1} [v \to H_{2}]$ (An induced copy of $H_{2}$ inside the extension set of an induced embedding of $H_{1} - v$ yields an induced copy of $H_{1}$ with $H_{2}$ substituted for $v$ ).

[L6]

For finite sets $X \neq \emptyset$ and $Y$ and a relation $R \subseteq X \times Y$ with row fibres $R_{x}$ , there is $x_{+} \in X$ with $∣ R_{x_{+}} ∣ \geq ∣ R ∣ / ∣ X ∣$ (If $X$ is nonempty, some row fibre is at least the average size and some row fibre is at most the average size).

[F4]

${ind}_{K} (G)$ is the number of induced embeddings of $K$ into $G$ (The induced-embedding count ${ind}_{H} (G)$ ).

[F5]

$G [W] = (W, E (G) \cap [W]^{2})$ , so two vertices of $W$ are adjacent in $G [W]$ exactly when they are adjacent in $G$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F6]

For $a > 0$ and real $x$ , $a^{x} = \exp (x \log a)$ (Real powers for positive bases, with the zero-base positive-exponent convention).

[L7]

For $a, b > 0$ and real $r, s$ : $a^{r + s} = a^{r} a^{s}$ , $(a b)^{r} = a^{r} b^{r}$ , $(a / b)^{r} = a^{r} / b^{r}$ and $(a^{r})^{s} = a^{r s}$ (The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents).

[L8]

The logarithm is continuous and strictly increasing on $(0, \infty)$ , is onto $R$ , satisfies $\log (x y) = \log x + \log y$ and $\log (x / y) = \log x - \log y$ , and $\log 1 = 0$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[L9]

The exponential is continuous and strictly increasing on $R$ (The exponential function is strictly increasing).

[F7]

For $b > 0$ with $b \neq 1$ and $x > 0$ , $\log_{b} x = \log x / \log b$ (The logarithm to a positive base other than one).

[L10]

Every complete ordered field is Archimedean: for every $x$ there is a natural number $k \geq 1$ with $x < k$ (Every complete ordered field is Archimedean).

[L11]

Every nonempty subset of $N$ has a least element (The well-ordering principle).

Proof

technique · direct

1.1givenF1F7L8choosealgebra

Choose Erdős–Hajnal constants $ϵ_{1} > 0$ for the class of $H_{1}$ -free graphs and $ϵ_{2} > 0$ for the class of $H_{2}$ -free graphs, and set $β = 1 / (2 (h + 1))$ , $ϵ_{0} = β \min {ϵ_{1}, ϵ_{2}}$ , $n_{0} = \max {4 \cdot 16^{h}, 2 h, h^{2 (h + 1)}}$ and $ϵ = \min {ϵ_{0}, 1 / \log_{2} n_{0}}$ . Then $0 < β \leq 1 / 4$ , $ϵ_{0} > 0$ , $n_{0} \geq 64$ and $ϵ > 0$ , and $β (h + 1) = 1 / 2$ gives $1 - β h = 1 / 2 + β$ .

1.2F6L8L9

For $a \geq 1$ and $s \leq t$ one has $a^{s} \leq a^{t}$ , because $\log a \geq 0$ and both $\exp$ and $\log$ are increasing; and for $0 < a \leq b$ and $r > 0$ one has $a^{r} \leq b^{r}$ for the same reason.

1.3L1F1

By [L1] the class of $H$ -free graphs is hereditary, so it is a class for which [F1] can supply a constant.

2.1step 1.1step 1.2L10L11F6choose

Let $G$ be a finite simple graph with $n = ∣ V (G) ∣ \geq n_{0}$ and $hom (G) < n^{ϵ_{0}}$ . The set of natural numbers $k$ with $k \geq n^{β}$ is nonempty by [L10], so it has a least element $m$ by [L11]; since $n^{β} > 0$ we have $m \geq 1$ , and $m - 1 < n^{β}$ , so $n^{β} \leq m < n^{β} + 1 \leq 2 n^{β}$ , the last step because $n \geq 1$ gives $n^{β} \geq 1$ .

2.2step 1.1step 1.2F2F6F7L8algebra

Turning to the small orders, let $J$ be any nonempty $H$ -free graph with $n^{'} = ∣ V (J) ∣ < n_{0}$ . If $n^{'} \geq 2$ then two distinct vertices of $J$ form a clique or a stable set, so $hom (J) \geq 2$ ; and ${n^{'}}^{ϵ} < n_{0}^{ϵ} \leq n_{0}^{1 / \log_{2} n_{0}} = \exp (\log n_{0} \cdot \log 2 / \log n_{0}) = 2$ , so $hom (J) \geq {n^{'}}^{ϵ}$ . If $n^{'} = 1$ then $hom (J) = 1 = 1^{ϵ}$ .

3.1step 1.1step 2.1step 1.2L7algebra

Since $n \geq h^{2 (h + 1)} = h^{1 / β}$ , raising to the power $β$ gives $n^{β} \geq h$ , so $m \geq h$ ; and $β \leq 1 / 4$ with $n \geq 64$ gives $m < n^{1 / 4} + 1 \leq n$ . Hence $h \leq m \leq n$ .

4.1step 2.1step 3.1step 1.2L2L7F5F3

Let $W \subseteq V (G)$ with $∣ W ∣ = m$ . Then $W \neq \emptyset$ and $∣ W ∣^{ϵ_{1}} = m^{ϵ_{1}} \geq (n^{β})^{ϵ_{1}} = n^{β ϵ_{1}} \geq n^{ϵ_{0}} > hom (G)$ , using $ϵ_{0} \leq β ϵ_{1}$ and $n \geq 1$ ; so by [L2] the graph $G [W]$ has an induced copy of $H_{1}$ , that is, an $h$ -element $S \subseteq W$ with $G [S] ≅ H_{1}$ .

5.1step 3.1step 4.1L3F3F4

By [L3] the number $g$ of $h$ -element sets $S \subseteq V (G)$ with $G [S] ≅ H_{1}$ is at least $(n - h + 1)^{h} / m^{h}$ , and each such $S$ carries at least one induced embedding of $H_{1}$ into $G$ , distinct sets carrying distinct embeddings because their images differ; so ${ind}_{H_{1}} (G) \geq g \geq (n - h + 1)^{h} / m^{h} > 0$ .

6.1step 5.1L4L6F4

By [F4] and step 5.1 the set $Φ$ of induced embeddings of $H_{1}$ into $G$ is nonempty, so the set $Ψ$ of [L4] is nonempty as well, since each member of $Φ$ restricts into it. Applying [L6] to the relation pairing $φ \in Ψ$ with the members of $Φ$ restricting to it, whose row fibres have sizes $∣ X_{φ} ∣$ and whose total size is ${ind}_{H_{1}} (G)$ by [L4], gives $φ_{+} \in Ψ$ with $∣ X_{φ_{+}} ∣ \geq {ind}_{H_{1}} (G) / ∣ Ψ ∣$ .

7.1step 1.1step 2.1step 5.1step 6.1L4L7algebra

Since $∣ Ψ ∣ \leq n^{h - 1}$ and $n \geq n_{0} \geq 2 h$ gives $n - h + 1 > n / 2$ , and $m < 2 n^{β}$ by step 2.1, we get $∣ X_{φ_{+}} ∣ \geq \frac{(n - h + 1)^{h}}{m^{h} n^{h - 1}} > \frac{(n / 2)^{h}}{2^{h} n^{β h} n^{h - 1}} = \frac{n^{1 - β h}}{4^{h}} = 4^{- h} n^{1 / 2} n^{β}$ .

8.1step 1.1step 2.1step 7.1step 1.2L7algebra

From $n \geq 4 \cdot 16^{h}$ we get $n^{1 / 2} \geq 2 \cdot 4^{h}$ , so $4^{- h} n^{1 / 2} \geq 2$ and step 7.1 gives $∣ X_{φ_{+}} ∣ > 2 n^{β} > m \geq n^{β}$ . In particular $X_{φ_{+}}$ is nonempty.

9.1step 2.1step 8.1step 1.2L2L7F5F3

Therefore $∣ X_{φ_{+}} ∣^{ϵ_{2}} \geq (n^{β})^{ϵ_{2}} = n^{β ϵ_{2}} \geq n^{ϵ_{0}} > hom (G)$ , so by [L2] the graph $G [X_{φ_{+}}]$ has an induced copy of $H_{2}$ ; the corresponding induced embedding has image inside $X_{φ_{+}}$ and, adjacency in $G [X_{φ_{+}}]$ agreeing with adjacency in $G$ , it is an induced embedding of $H_{2}$ into $G$ .

10.1step 2.1step 9.1step 1.2L5F3

By [L5] applied to $φ_{+}$ and that embedding, the graph $G$ of step 2.1 has an induced copy of $H$ and so is not $H$ -free. Hence an $H$ -free graph $G$ with $∣ V (G) ∣ = n \geq n_{0}$ cannot satisfy $hom (G) < n^{ϵ_{0}}$ , and therefore satisfies $hom (G) \geq n^{ϵ_{0}} \geq n^{ϵ}$ , the last inequality by step 1.2 and $ϵ \leq ϵ_{0}$ .

11.1step 1.3step 10.1step 2.2F1∎

Steps 10.1 and 2.2 together give $hom (G) \geq ∣ V (G) ∣^{ϵ}$ for every nonempty $H$ -free graph $G$ , whatever its order, and the class of $H$ -free graphs is hereditary by step 1.3; that is, $ϵ$ is an Erdős–Hajnal constant for it and $H$ has the Erdős–Hajnal property.

CorollaryStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-08-26Open item page →

Every graph has the Erdős–Hajnal property if and only if every prime graph does

Statement

The following are equivalent.

Every finite simple graph has the Erdős–Hajnal property (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).
Every prime graph (Prime graphs: those whose only modules are the trivial ones) has the Erdős–Hajnal property.

Facts & Assumptions

Given: The two assertions above.

[L1]

A graph on at least two vertices is prime exactly when it is not obtained by substituting one graph on at least two vertices for a vertex of another such graph (A graph with at least two vertices is prime exactly when it is not obtained by substituting one graph on at least two vertices for a vertex of another graph on at least two vertices).

[L2]

If $H_{1}$ and $H_{2}$ have the Erdős–Hajnal property, then the graph obtained by substituting $H_{2}$ for a vertex of $H_{1}$ has the Erdős–Hajnal property (Alon–Pach–Solymosi: if $H_{1}$ and $H_{2}$ have the Erdős–Hajnal property, so does the graph obtained from $H_{1}$ by substituting $H_{2}$ for a vertex).

[L3]

A graph on $0$ or $1$ vertices is prime, since every module is trivial (Prime graphs: those whose only modules are the trivial ones, The cardinality $∣ A ∣$ of a finite set).

Proof

technique · induction

1.1given

If every graph has the Erdős–Hajnal property, then in particular every prime graph has it.

1.2base

For the converse direction, assume every prime graph has the Erdős–Hajnal property, and induct on the number of vertices of a graph $G$ .

1.3L3base

If $∣ V (G) ∣ \leq 1$ , then $G$ is prime by [L3], so the assumption covers $G$ .

1.4L1ih

Fix $n \geq 2$ and assume inductively that every graph with fewer than $n$ vertices has the Erdős–Hajnal property whenever every prime graph does. Let $G$ have $n$ vertices. If $G$ is prime, the assumption on prime graphs covers it. Otherwise [L1] gives graphs $G_{1}, G_{2}$ with at least two vertices each such that $G = G_{1} [a \to G_{2}]$ for some vertex $a$ of $G_{1}$ .

2.1step 1.4L2ih

In the non-prime case of step 1.4, both $G_{1}$ and $G_{2}$ have fewer than $n$ vertices, so the induction hypothesis gives the Erdős–Hajnal property for both, and then [L2] gives it for $G$ .

3.1step 1.3step 1.4step 2.1discharge-induction∎

Steps 1.3, 1.4 and 2.1 prove that every $n$ -vertex graph has the Erdős–Hajnal property, so the induction closes.

CorollaryStatement: AI-generatedProof: AI-generatedprecheck passaudited 2026-08-26Open item page →

Substituting a complete or an edgeless graph for a vertex preserves the Erdős–Hajnal property

Statement

Let $H$ be a graph with the Erdős–Hajnal property and let $v \in V (H)$ . If $t \geq 1$ , then the graph obtained by substituting $K_{t}$ or $\overline{K_{t}}$ for $v$ also has the Erdős–Hajnal property.

Facts & Assumptions

Given: A graph $H$ with the Erdős–Hajnal property, a vertex $v \in V (H)$ , and an integer $t \geq 1$ .

[L1]

For every $t \geq 1$ , the class of $K_{t}$ -free graphs has the Erdős–Hajnal property (For every $t \geq 1$ , the class of $K_{t}$ -free graphs has the Erdős–Hajnal property).

[L2]

A graph is $\overline{K_{t}}$ -free exactly when its complement is $K_{t}$ -free, and the Erdős–Hajnal property is preserved by taking complements of graph classes ( $G$ is $H$ -free if and only if $\overline{G}$ is $\overline{H}$ -free, The complement of a graph class, A hereditary class has the Erdős–Hajnal property exactly when its complementary class does, with the same constants).

[L3]

If two graphs have the Erdős–Hajnal property, then substituting one for a vertex of the other preserves that property (Alon–Pach–Solymosi: if $H_{1}$ and $H_{2}$ have the Erdős–Hajnal property, so does the graph obtained from $H_{1}$ by substituting $H_{2}$ for a vertex, Substituting one graph for a vertex of another).

Proof

technique · direct

1.1L1

The complete graph $K_{t}$ has the Erdős–Hajnal property, since every $K_{t}$ -free class does by [L1].

2.1step 1.1L2

The edgeless graph $\overline{K_{t}}$ has the Erdős–Hajnal property: by [L2] the class of $\overline{K_{t}}$ -free graphs is the complementary class of the $K_{t}$ -free graphs, so it has the same property.

3.1step 1.1step 2.1L3∎

Applying [L3] to $H$ and $K_{t}$ shows that substituting $K_{t}$ for $v$ preserves the Erdős–Hajnal property, and applying [L3] to $H$ and $\overline{K_{t}}$ shows the same for the edgeless graph.

RemarkRemark: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

Why this page says module where some sources say homogeneous set

The target paper uses the phrase homogeneous set for what this page calls a module. This library already uses homogeneous set at order 395 for a clique or a stable set, through the homogeneous number $hom (G)$ (Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ), so reusing the same words here would create an avoidable ambiguity inside the same graph-theory block.

Harju writes clan and explicitly notes that it is the same object as a module. His notes-on-references list the wider synonym family: closed set (Gallai), autonomous set, partitive set, externally related set, condensible set, homogeneous set, interval, and module. The present page adopts Habib and Paul's word module because it is standard and does not collide with the already-published meaning of homogeneous set.

RemarkRemark: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

Which small graphs count as prime on this page

This page adopts the direct module-theoretic convention: a graph is prime when its only modules are the trivial ones. Under that convention every graph on one or two vertices is prime, and no graph on exactly three vertices is prime (No graph on exactly three vertices is prime).

Some sources build a size restriction into the terminology instead. Chudnovsky phrases primality through non-substitutability for graphs with at least two vertices, while other texts reserve the word prime for graphs on at least four vertices. These conventions agree with the direct module-theoretic convention on graphs with at least four vertices, but deliberately differ at smaller orders. The equivalence with non-substitutability is stated with its size hypotheses in A graph with at least two vertices is prime exactly when it is not obtained by substituting one graph on at least two vertices for a vertex of another graph on at least two vertices.

5 · Examples, counterexamples and false statements

None yet.

Modules, Substitution and Prime Graphs

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Modules of a graph, and the trivial modules

Definition

Remarks

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

Statement

Facts & Assumptions

Proof

A vertex set is a module of GG exactly when it is a module of G‾G

Statement

Facts & Assumptions

Proof

Every union of connected components is a module, and so is every union of anticonnected components

Statement

Facts & Assumptions

Proof

Two disjoint nonempty modules form a complete or an anticomplete pair

Statement

Facts & Assumptions

Proof

The intersection of two modules is a module

Statement

Facts & Assumptions

Proof

The union of two modules with a common vertex is a module

Statement

Facts & Assumptions

Proof

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

Statement

Facts & Assumptions

Proof

If MM is a module of GG and W⊆V(G)W⊆V(G), then M∩WM∩W is a module of G[W]G[W]

Statement

Facts & Assumptions

Proof

A module of G[M]G[M] is a module of GG whenever MM is a module of GG

Statement

Facts & Assumptions

Proof

In a connected graph, some vertex outside a nonempty proper module is complete to it

Statement

Facts & Assumptions

Proof

Prime graphs: those whose only modules are the trivial ones

Definition

No graph on exactly three vertices is prime

Statement

Facts & Assumptions

Proof

Substituting one graph for a vertex of another

Definition

In G1G1​ with G2G2​ substituted for aa, the vertex set of G2G2​ is a module, the two factors are recovered as induced subgraphs, and substituting a one-vertex graph changes nothing

Statement

Facts & Assumptions

Proof

The complement of G1[a→G2]G1​[a→G2​] is G1‾[a→G2‾]G1​​[a→G2​​]

Statement

Facts & Assumptions

Proof

A graph with at least two vertices is prime exactly when it is not obtained by substituting one graph on at least two vertices for a vertex of another graph on at least two vertices

Statement

Facts & Assumptions

Proof

Modular partitions and the quotient graph they define

Definition

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

Statement

Facts & Assumptions

Proof

A graph is recovered from any modular partition by the induced subgraphs on the parts together with the quotient graph

Statement

Facts & Assumptions

Proof

The quotient by a modular partition is isomorphic to the subgraph induced by any set meeting each part exactly once

Statement

A vertex set is a module of $G$ exactly when it is a module of $\overline{G}$

If $M$ is a module of $G$ and $W \subseteq V (G)$ , then $M \cap W$ is a module of $G [W]$

A module of $G [M]$ is a module of $G$ whenever $M$ is a module of $G$

In $G_{1}$ with $G_{2}$ substituted for $a$ , the vertex set of $G_{2}$ is a module, the two factors are recovered as induced subgraphs, and substituting a one-vertex graph changes nothing

The complement of $G_{1} [a \to G_{2}]$ is $\overline{G_{1}} [a \to \overline{G_{2}}]$

$hom (G [W]) \leq hom (G)$ for every vertex subset $W$

If $ϵ$ is an Erdős–Hajnal constant for $H$ and $W$ is a nonempty vertex set with $∣ W ∣^{ϵ} > hom (G)$ , then $G [W]$ has an induced copy of $H$

If every $m$ -element vertex set contains an induced copy of $H$ , then at least $(\binom{n}{h}) / (\binom{m}{h})$ of the $h$ -element vertex sets induce a copy of $H$

The induced copies of $H_{1}$ in $G$ are counted by summing, over the induced embeddings of $H_{1} - v$ , the number of vertices that extend them at $v$

An induced copy of $H_{2}$ inside the extension set of an induced embedding of $H_{1} - v$ yields an induced copy of $H_{1}$ with $H_{2}$ substituted for $v$

Alon–Pach–Solymosi: if $H_{1}$ and $H_{2}$ have the Erdős–Hajnal property, so does the graph obtained from $H_{1}$ by substituting $H_{2}$ for a vertex