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

How statement and proof provenance work

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

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

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

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]

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

Depends on

Used by

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 Theorem

Dependency tree · two levels

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

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