DefinitionDefinition: Literature-sourcedProof: Not applicableSession-authored (Fable 5 assisted)judge 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.

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.

Depends on

Used by

Dependency tree · two levels

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