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.

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.

Depends on

Used by

Alon–Pach–Solymosi: if H₁ and H₂ have the Erdős–Hajnal property, so does the graph obtained from H₁ by substituting H₂ for a vertex Theorem

Dependency tree · two levels

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

Sources

M. Chudnovsky, The Erdős–Hajnal Conjecture: A Survey, sec. 2 (standard reference, not scraped)

An induced copy of H2H2​ inside the extension set of an induced embedding of H1−vH1​−v yields an induced copy of H1H1​ with H2H2​ substituted for vv