TheoremStatement: 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 contains a perfect induced subgraph of order at least $∣ V (G) ∣^{1 / α}$

Statement

Let $G$ be a nonempty finite graph and let $α > 0$ . If $G$ is $α$ -narrow, then it has a perfect induced subgraph of order at least $∣ V (G) ∣^{1 / α}$ .

Facts & Assumptions

Given: A nonempty finite graph $G$ and a real number $α > 0$ .

[F1]

A graph is $α$ -narrow when every good function $g$ satisfies $\sum_{v \in V (G)} g (v)^{α} \leq 1$ (An $α$ -narrow graph).

[F2]

A good function has weight at most $1$ on every perfect induced subgraph (A good function on a graph, A perfect graph).

[L1]

For every real $β > 0$ , the function $x \mapsto x^{β}$ is increasing on $(0, \infty)$ : its derivative is $β x^{β - 1}$ , the factor $x^{β - 1}$ is positive for $x > 0$ because real powers are defined through $\exp$ and $\exp$ is positive, and the derivative-sign theorem then gives monotonicity (Continuity and derivatives of positive-base real powers, Real powers for positive bases, with the zero-base positive-exponent convention, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ , On an interval $I$ , for $f$ continuous on $I$ and differentiable at every interior point: $f^{'} \geq 0$ throughout gives $f$ nondecreasing, $f^{'} > 0$ gives $f$ increasing, $f^{'} \leq 0$ and $f^{'} < 0$ give the two decreasing forms; conversely a nondecreasing $f$ has $f^{'} \geq 0$ and a nonincreasing $f$ has $f^{'} \leq 0$ wherever it is differentiable, and no strict converse is claimed).

[L2]

For positive reals, $(a^{r})^{s} = a^{r s}$ (The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents).

[F3]

Real powers use the notation $x^{1 / α}$ for positive $x$ (Real powers for positive bases, with the zero-base positive-exponent convention).

Proof

technique · direct

1.1F2choosealgebra

Let $K$ be the maximum order of a perfect induced subgraph of $G$ . Since $G$ is nonempty, every one-vertex induced subgraph is perfect, so $K \geq 1$ . Define $g (v) = 1 / K$ for every $v \in V (G)$ . If $P$ is a perfect induced subgraph of $G$ , then $∣ V (P) ∣ \leq K$ , so $\sum_{v \in V (P)} g (v) = ∣ V (P) ∣ / K \leq 1$ . Thus $g$ is good by [F2].

2.1step 1.1F1L1L2F3algebra

If $G$ is $α$ -narrow, [F1] applied to the good function of step 1.1 yields $∣ V (G) ∣ / K^{α} = \sum_{v \in V (G)} g (v)^{α} \leq 1$ . Therefore $K^{α} \geq ∣ V (G) ∣$ . Since $K \geq 1$ and $∣ V (G) ∣ \geq 1$ , both sides are positive, so applying [L1] with exponent $1 / α > 0$ and then using [L2] gives $K = (K^{α})^{1 / α} \geq ∣ V (G) ∣^{1 / α}$ .

3.1step 2.1∎

By definition of $K$ , there is a perfect induced subgraph of order $K$ , and step 2.1 gives $K \geq ∣ V (G) ∣^{1 / α}$ .

Depends on

Used by

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

Dependency tree · two levels

34 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, Section 2 (standard reference, not scraped)

An αα-narrow graph contains a perfect induced subgraph of order at least ∣V(G)∣1/α∣V(G)∣1/α