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

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

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]

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

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

Depends on

Used by

Dependency tree · two levels

20 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

T. Huang, Y. Ju and R. Zhou, Erdős–Hajnal beyond the five-vertex path, sec. 1.2 (standard reference, not scraped)
M. Chudnovsky, The Erdős–Hajnal Conjecture: A Survey, sec. 2 (standard reference, not scraped)