LemmaStatement: 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.

Replicating a vertex of a perfect graph preserves perfection

Statement

Let $G$ be a finite perfect graph and let $x \in V (G)$ . Form $G^{'}$ by adding a new vertex $x^{'}$ adjacent exactly to $x$ and every neighbor of $x$ . Then $G^{'}$ is perfect. In particular, replacing $x$ by any nonempty finite clique of true twins preserves perfection, by repeated replication.

Facts & Assumptions

Given: A finite perfect graph $G$ , a vertex $x \in V (G)$ , and its replication $G^{'}$ as in the Statement.

[L1]

A graph is perfect when every induced subgraph $H$ has $χ (H) = ω (H)$ (A perfect graph).

[L2]

A proper coloring partitions the vertices into stable color classes, and a clique meets each color class in at most one vertex (Proper vertex colourings and chromatic number, Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[L3]

Deleting vertices gives an induced subgraph, so every induced subgraph of a perfect graph is perfect (Subgraphs, induced subgraphs and spanning subgraphs, A perfect graph).

Proof

technique · direct

1.1

Induct on $∣ V (G) ∣$ . For $G = K_{1}$ , its replication is $K_{2}$ , whose induced subgraphs have equal chromatic and clique numbers. Assume the assertion for smaller perfect graphs. Every proper induced subgraph of $G^{'}$ either contains at most one of $x, x^{'}$ and is isomorphic to an induced subgraph of $G$ , or contains both and is the replication of $x$ in a proper induced subgraph of $G$ . It is perfect by [L3] or by the induction hypothesis, respectively. Thus it remains to show $χ (G^{'}) = ω (G^{'})$ .

L1L3induction

2.1

Put $w = ω (G) = χ (G)$ . Every clique of $G^{'}$ contains at most the one additional vertex $x^{'}$ , so $ω (G^{'})$ is $w$ or $w + 1$ . If it is $w + 1$ , color $G$ with $w$ colors and give $x^{'}$ a new color. Then $χ (G^{'}) \leq w + 1 = ω (G^{'})$ , and the reverse inequality holds in every graph.

L1L2step 1.1

3.1

Suppose $ω (G^{'}) = w$ . No $w$ -clique of $G$ contains $x$ , since its union with $x^{'}$ would be a $(w + 1)$ -clique of $G^{'}$ . Fix a proper $w$ -coloring of $G$ , and let $X$ be the color class of $x$ . Every $w$ -clique of $G$ meets $X$ exactly once by [L2], and that meeting vertex is not $x$ . Hence the induced graph $H = G - (X ∖ {x})$ has no $w$ -clique and $ω (H) \leq w - 1$ . Since $H$ is perfect by [L3], it admits a coloring with at most $w - 1$ colors.

L1L2L3step 2.1choose

4.1

The remaining set $(X ∖ {x}) \cup {x^{'}}$ is stable in $G^{'}$ : $X$ was a color class, and $x^{'}$ is adjacent outside $x$ only to neighbors of $x$ , none of which lies in $X$ . Give that set one new color, extending the coloring of $H$ to a $w$ -coloring of $G^{'}$ . Thus $χ (G^{'}) \leq w = ω (G^{'})$ ; the opposite inequality is universal. With step 2.1, this proves $G^{'}$ perfect by step 1.1. To replace $x$ by a clique of $k \geq 1$ true twins, replicate $x$ successively $k - 1$ times; each step starts from a perfect graph and creates one further twin.

step 1.1step 2.1step 3.1L1L2induction∎

Source notes

Diestel, Lemma 5.5.5, pp. 142-143, gives the same induction and the key color-class argument. The PDF was read in full for this lemma. The finite clique-of-twins conclusion is the explicit iteration needed below.

Depends on

Used by

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

Reinhard Diestel, Graph Theory, 5th ed., Lemma 5.5.5, pp. 142-143 (standard reference, not scraped)