LemmaStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck 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 complete connection of two perfect graphs is perfect

Statement

If $G$ and $H$ are perfect graphs on disjoint vertex sets, then their complete connection $G \nabla H$ 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 $G \nabla H$ on $X$ is $G [X_{G}] \nabla H [X_{H}]$ (The complete connection of two disjoint graphs, Subgraphs, induced subgraphs and spanning subgraphs).

[L3]

In a complete connection, every clique is the union of a clique from each side, while every stable set lies entirely in one side; therefore $ω (G \nabla H) = ω (G) + ω (H)$ and $χ (G \nabla H) = χ (G) + χ (H)$ (Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ , Proper vertex colourings and chromatic number).

Proof

technique · direct

1.1

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

L1given

2.1

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

step 1.1L2L3

3.1

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

step 2.1L1∎

Depends on

Used by

Every cograph is perfect Theorem

Dependency tree · two levels

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