LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-09-24 (gpt-6-sol)

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.

Perfect vertex deletions imply 2-narrowness

Statement

Let $G$ be a finite graph with at least three vertices. If $G - v$ is perfect for every vertex $v$ , then $G$ is two-narrow.

Facts & Assumptions

Given: A finite graph $G$ with $n = ∣ V (G) ∣ \geq 3$ such that every single-vertex deletion $G - v$ is perfect.

[F1]

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

[F2]

Two-narrowness means that every good function has sum of squared weights at most $1$ (An $α$ -narrow graph).

Proof

technique · direct

1.1

Let $g$ be any good function on $G$ . Choose a vertex $v_{0}$ with minimum weight $m = g (v_{0})$ , and put $A = \sum_{v \neq v_{0}} g (v)$ .

F1construct

2.1

Since $G - v_{0}$ is perfect, [F1] gives $A \leq 1$ . The other $n - 1$ weights are each at least $m \geq 0$ , so $A \geq (n - 1) m$ . For any $u \neq v_{0}$ , the remaining $n - 2$ weights in $A$ are at least $m$ , hence $g (u) \leq A - (n - 2) m$ .

F1step 1.1algebra

3.1

Consequently $\sum_{v \in V (G)} g (v)^{2} \leq m^{2} + (A - (n - 2) m) A = A^{2} - m ((n - 2) A - m) \leq A^{2} \leq 1$ . Indeed, $(n - 2) A \geq (n - 2) (n - 1) m \geq m$ because $n \geq 3$ and $m \geq 0$ .

step 2.1algebra

4.1

This holds for every good $g$ , so $G$ is two-narrow by [F2].

step 3.1F2∎

Depends on

Used by

The five-cycle is 2-narrow but not 1-narrow Example

Dependency tree · two levels

7 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 (good functions and narrowness) (standard reference, not scraped)