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

An $α$ -narrow graph has a clique or stable set of size at least $∣ V (G) ∣^{1 / (2 α)}$

Statement

Let $G$ be a nonempty finite graph and let $α > 0$ . If $G$ is $α$ -narrow, then $G$ contains a clique or a stable set of size at least $∣ V (G) ∣^{1 / (2 α)}$ .

Facts & Assumptions

Given: A nonempty $α$ -narrow finite graph $G$ .

[L1]

The graph $G$ has a perfect induced subgraph $P$ with $∣ V (P) ∣ \geq ∣ V (G) ∣^{1 / α}$ (An $α$ -narrow graph contains a perfect induced subgraph of order at least $∣ V (G) ∣^{1 / α}$ ).

[L2]

Every finite graph $H$ satisfies $∣ V (H) ∣ \leq χ (H) α (H)$ (The bounds $ω (G) \leq χ (G)$ and $∣ V (G) ∣ \leq χ (G) α (G)$ ).

[F1]

In a perfect graph, every induced subgraph satisfies $χ = ω$ (A perfect graph).

[F2]

The clique number and stability number are the sizes of the largest clique and stable set (Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[F3]

Real powers use the displayed exponent notation (Real powers for positive bases, with the zero-base positive-exponent convention).

Proof

technique · direct

1.1L1L2F1F2algebra

Let $P$ be the perfect induced subgraph given by [L1]. Applying [L2] to $P$ and then using [F1] gives $∣ V (P) ∣ \leq α (P) ω (P)$ . Hence either $α (P) \geq ∣ V (P) ∣^{1 / 2}$ or $ω (P) \geq ∣ V (P) ∣^{1 / 2}$ . So $P$ , and therefore $G$ , has a stable set or clique of size at least $∣ V (P) ∣^{1 / 2}$ .

2.1step 1.1L1F3algebra∎

Since $∣ V (P) ∣ \geq ∣ V (G) ∣^{1 / α}$ , step 1.1 yields a clique or stable set of size at least $∣ V (G) ∣^{1 / (2 α)}$ by [F3].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

23 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 and Shmuel Safra, The Erdős-Hajnal conjecture for bull-free graphs, Proposition 2.1 (standard reference, not scraped)

An αα-narrow graph has a clique or stable set of size at least ∣V(G)∣1/(2α)∣V(G)∣1/(2α)