LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-28

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.

A disjoint union of two perfect graphs is perfect

Statement

If $G$ and $H$ are perfect graphs on disjoint vertex sets, then their disjoint union is perfect.

Facts & Assumptions

Given: Perfect graphs $G = (V_{G}, E_{G})$ and $H = (V_{H}, E_{H})$ with $V_{G} \cap V_{H} = \emptyset$ .

[L1]

A graph is perfect exactly when every induced subgraph has equal clique number and chromatic number (Perfect graphs).

[L2]

If $X \subseteq V_{G} \cup V_{H}$ and $X_{G} : = X \cap V_{G}$ , $X_{H} : = X \cap V_{H}$ , then the induced subgraph of the disjoint union on $X$ is the disjoint union of $G [X_{G}]$ and $H [X_{H}]$ (Subgraphs, induced subgraphs and spanning subgraphs).

[L3]

In a disjoint union, every clique lies in one side, while optimal colourings of the two sides may reuse the same palette; therefore $ω (G ⊔ H) = \max {ω (G), ω (H)}$ and $χ (G ⊔ H) = \max {χ (G), χ (H)}$ (Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ , Proper vertex colourings and chromatic number).

Proof

technique · direct

1.1L1given

Let $X \subseteq V_{G} \cup V_{H}$ , and write $X_{G} : = X \cap V_{G}$ and $X_{H} : = X \cap V_{H}$ . Since $G$ and $H$ are perfect, [L1] gives $χ (G [X_{G}]) = ω (G [X_{G}])$ and $χ (H [X_{H}]) = ω (H [X_{H}])$ .

2.1step 1.1L2L3

By [L2], the induced subgraph of $G ⊔ H$ on $X$ is $G [X_{G}] ⊔ H [X_{H}]$ . Applying [L3] to that disjoint union and then using step 1.1 yields $χ ((G ⊔ H) [X]) = \max {χ (G [X_{G}]), χ (H [X_{H}])} = \max {ω (G [X_{G}]), ω (H [X_{H}])} = ω ((G ⊔ H) [X]) .$

3.1step 2.1L1∎

Step 2.1 proves $χ (K) = ω (K)$ for every induced subgraph $K = (G ⊔ H) [X]$ , so the disjoint union $G ⊔ H$ is perfect by [L1].

Depends on

Used by

Every cograph is perfect 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

Maria Chudnovsky, The Erdos-Hajnal Conjecture - A Survey, Introduction (standard reference, not scraped)