CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (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.

The polynomial Rödl witness need not be the whole graph

Statement refuted

Whenever a finite family has the polynomial Rödl property, the restricted set guaranteed by that property can always be chosen to be the whole graph.

Facts & Assumptions

Given: A real $ϵ \in (0, \frac{1}{2})$ and the graph $G : = K_{N} ⊔ K_{N}$ with $N > 1 / (1 - 2 ϵ)$ .

[L1]

Every graph on at most three vertices has the Erdős–Hajnal property (Every graph on at most three vertices has the Erdős–Hajnal property).

[L2]

For a single graph, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent (For a single graph, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent).

[L3]

$P_{3}$ is the three-vertex path, and $K_{N}$ is the complete graph on $N$ vertices (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[L4]

A set is $ϵ$ -restricted when it is $ϵ$ -sparse or $ϵ$ -dense ( $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

[L5]

A graph is $P_{3}$ -free when it has no induced copy of the three-vertex path ( $H$ -free and $F$ -free graphs under the induced-subgraph convention, Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Counterexample

technique · constructive

1.1L3L5construct

The graph $G$ is $P_{3}$ -free: three vertices in one clique induce a triangle, three vertices meeting both cliques induce either one edge or no edge, and none of those induced subgraphs is $P_{3}$ .

1.2L4algebra

Let $X : = V (G)$ . Every vertex of $X$ has exactly $N - 1$ neighbours and exactly $N$ non-neighbours inside $X$ . Since $N > 1 / (1 - 2 ϵ)$ , one has $N - 1 > 2 ϵ N = ϵ ∣ X ∣$ , so $X$ is not $ϵ$ -sparse; and because $ϵ < 1 / 2$ , one also has $N > ϵ ∣ X ∣$ , so $X$ is not $ϵ$ -dense. Thus $X$ is not $ϵ$ -restricted by [L4].

1.3L4algebra

One clique component of $G$ is $0$ -dense and therefore $ϵ$ -restricted, so the polynomial Rödl conclusion for $G$ is realized by a proper subset of vertices rather than by the whole graph.

1.4L1L2L3

By [L3], the graph $P_{3}$ has three vertices, so [L1] gives the Erdős–Hajnal property for $P_{3}$ . Applying [L2] then shows that the singleton family ${P_{3}}$ has the polynomial Rödl property.

2.1step 1.2step 1.3discharge-construct∎

Steps 1.2 and 1.3 show that the theorem's restricted witness need not be $V (G)$ itself, refuting the claim.

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.