TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passverified 2026-09-24 (gpt-6-sol)

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 a perfect graph into a perfect graph preserves perfection

Statement

Let $H_{1}, H_{2}$ be finite perfect graphs, let $v \in V (H_{1})$ , and assume the nonempty substitution $G = H_{1} [v \to H_{2}]$ is defined as in Substituting one graph for a vertex of another. Then $G$ is perfect. This includes every induced subgraph of $G$ , whether it meets the inserted copy of $H_{2}$ or not.

Facts & Assumptions

Given: Perfect finite graphs $H_{1}, H_{2}$ and a defined substitution $G = H_{1} [v \to H_{2}]$ .

[L1]

Every induced subgraph of a perfect graph has chromatic number equal to its clique number. A proper coloring splits its vertices into stable color classes (A perfect graph, Proper vertex colourings and chromatic number, Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[L2]

Replicating a vertex of a perfect graph into a nonempty finite clique of true twins preserves perfection (Replicating a vertex of a perfect graph preserves perfection).

[L3]

In $H_{1} [v \to H_{2}]$ , each vertex of $H_{2}$ has precisely the outside neighbors that $v$ had. Deleting a vertex set gives an induced subgraph (Substituting one graph for a vertex of another, Subgraphs, induced subgraphs and spanning subgraphs).

Proof

technique · direct

1.1

Fix an arbitrary $W \subseteq V (G)$ , put $R = H_{2} [W \cap V (H_{2})]$ and $S = W ∖ V (H_{2})$ . If $R$ is empty, then $G [W] = H_{1} [S]$ , which is perfect by [L1]. Suppose $R$ is nonempty. Let $Q = H_{1} [S \cup {v}]$ . By [L3], $G [W] = Q [v \to R]$ , and $Q, R$ are perfect induced subgraphs of $H_{1}, H_{2}$ .

L1L3construct

2.1

Put $k = χ (R) = ω (R) \geq 1$ . Replace $v$ in $Q$ by a $k$ -vertex clique $C$ of true twins, obtaining $Q_{C}$ . By [L2], $Q_{C}$ is perfect. Every clique of $G [W]$ either avoids $R$ or consists of a clique in $R$ together with outside vertices all adjacent to $v$ in $Q$ ; its inside part has size at most $k$ . Conversely, for any clique of outside vertices adjacent to $v$ , a $k$ -clique of $R$ can be added. The same description holds with $C$ in place of $R$ , so $ω (G [W]) = ω (Q_{C})$ .

L1L2L3step 1.1

3.1

Color $Q_{C}$ optimally with $ω (Q_{C})$ colors. Its $k$ mutually adjacent twin vertices use $k$ distinct colors. Color $R$ properly with $k$ colors and relabel those colors by the $k$ colors on $C$ ; keep the colors of all vertices in $S$ from the coloring of $Q_{C}$ . This colors $G [W]$ properly. Indeed, inside $S$ and inside $R$ the colorings are proper; an outside vertex adjacent to $v$ was adjacent to every member of $C$ , so its color differs from all $k$ colors now used on $R$ ; and an outside vertex not adjacent to $v$ has no edge into $R$ . Thus $χ (G [W]) \leq ω (Q_{C}) = ω (G [W])$ . The reverse inequality holds for every graph, so equality follows.

L1L3step 2.1

4.1

Since $W$ was arbitrary, every induced subgraph of $G$ has $χ = ω$ . Therefore $G$ is perfect.

L1step 1.1step 3.1∎

Source notes

Diestel, Exercise 51, p. 152, requests this substitution theorem after giving the replication lemma. Chudnovsky-Safra cite the theorem as their Theorem 5.1. Both source passages were read. The coloring transfer and induced-subgraph argument above supply the complete local proof.

Depends on

Used by

Substituting two α-narrow graphs yields another α-narrow graph Theorem

Dependency tree · two levels

15 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

Reinhard Diestel, Graph Theory, 5th ed., Exercise 51, p. 152, following Lemma 5.5.5 (standard reference, not scraped)
Maria Chudnovsky and Shmuel Safra, The Erdos-Hajnal conjecture for bull-free graphs, Theorem 5.1 (standard reference, not scraped)