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.

$hom (G [W]) \leq hom (G)$ for every vertex subset $W$

Statement

Let $G$ be a finite simple graph and $W \subseteq V (G)$ . Then $ω (G [W]) \leq ω (G)$ , $α (G [W]) \leq α (G)$ , and consequently $hom (G [W]) \leq hom (G)$ .

Facts & Assumptions

Given: A finite simple graph $G$ and a set $W \subseteq V (G)$ .

[F1]

A set $X \subseteq V (G)$ is a clique when every two distinct vertices of $X$ are adjacent and a stable set when no two distinct vertices of $X$ are adjacent; $ω (G)$ and $α (G)$ are the largest cardinalities of a clique and of a stable set (Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[F2]

$hom (G) = \max {ω (G), α (G)}$ (Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

[F3]

$G [W] = (W, E (G) \cap [W]^{2})$ , so two vertices of $W$ are adjacent in $G [W]$ exactly when they are adjacent in $G$ (Subgraphs, induced subgraphs and spanning subgraphs).

Proof

technique · direct

1.1F1F3

Let $X \subseteq W$ be a clique of $G [W]$ . Every two distinct vertices of $X$ are adjacent in $G [W]$ , hence adjacent in $G$ , so $X$ is a clique of $G$ .

1.2F1F3

Let $X \subseteq W$ be a stable set of $G [W]$ . No two distinct vertices of $X$ are adjacent in $G [W]$ , hence none are adjacent in $G$ , so $X$ is a stable set of $G$ .

2.1step 1.1step 1.2F1

Every clique of $G [W]$ is therefore a clique of $G$ , so the largest cardinality of a clique of $G [W]$ is at most that of a clique of $G$ : $ω (G [W]) \leq ω (G)$ . The same argument with step 1.2 gives $α (G [W]) \leq α (G)$ .

3.1step 2.1F2algebra∎

Taking the larger of the two numbers on each side, $hom (G [W]) = \max {ω (G [W]), α (G [W])} \leq \max {ω (G), α (G)} = hom (G)$ .

Depends on

Used by

If ε is an Erdős–Hajnal constant for H and W is a nonempty vertex set with |W|^ε>hom(G), then G[W] has an induced copy of H Lemma

Dependency tree · two levels

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

hom⁡(G[W])≤hom⁡(G)hom(G[W])≤hom(G) for every vertex subset WW