ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01

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.

A six-vertex witness graph makes the Bird criterion explicit

Example

The six-vertex graph

$H : E (H) = {v_{1} v_{2}, v_{1} v_{3}, v_{1} v_{5}, v_{1} v_{6}, v_{2} v_{3}, v_{2} v_{4}, v_{2} v_{5}, v_{3} v_{5}, v_{4} v_{5}, v_{4} v_{6}}$

has a homogeneous clique ${v_{2}, v_{5}}$ , so $H$ has the Erdős-Hajnal property; moreover $H^{+} - v_{3}$ and $H^{-} - v_{6}$ are both co-Bird.

Facts & Assumptions

Given: The graph $H$ above, with distinguished vertices $v_{1}$ and $v_{2}$ .

[L1]

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

[L2]

Substitution preserves the Erdős-Hajnal property (Alon–Pach–Solymosi: if $H_{1}$ and $H_{2}$ have the Erdős–Hajnal property, so does the graph obtained from $H_{1}$ by substituting $H_{2}$ for a vertex).

[L3]

The graph $H^{+}$ adds a new vertex adjacent to the two distinguished vertices, while $H^{-}$ does the same after deleting the distinguished edge if it is present; co-Bird is the complement of Bird (The graphs $H^{+}$ and $H^{-}$ for two distinguished vertices, The Bird graph and co-Bird).

Verification

technique · direct finite check

1.1givenconstruct

Outside the pair ${v_{2}, v_{5}}$ , both vertices are adjacent exactly to $v_{1}, v_{3}, v_{4}$ and are nonadjacent to $v_{6}$ . Hence ${v_{2}, v_{5}}$ is a homogeneous clique. Let $Q$ be the graph on ${x, v_{1}, v_{3}, v_{4}, v_{6}}$ with edges ${x v_{1}, x v_{3}, x v_{4}, v_{1} v_{3}, v_{1} v_{6}, v_{4} v_{6}}$ . Replacing $x$ by the clique ${v_{2}, v_{5}}$ recovers all edges of $H$ , so $H = Q [x \to K_{2}]$ .

1.2L3givenalgebra

In $H^{-}$ , delete $v_{6}$ . The remaining six vertices ${v, v_{1}, v_{2}, v_{3}, v_{4}, v_{5}}$ have edge set ${v v_{1}, v v_{2}, v_{1} v_{3}, v_{1} v_{5}, v_{2} v_{3}, v_{2} v_{4}, v_{2} v_{5}, v_{3} v_{5}, v_{4} v_{5}}$ . Relabel them by $x_{1} = v_{4}$ , $x_{2} = v$ , $x_{3} = v_{3}$ , $y = v_{1}$ , $z = v_{5}$ , and $w = v_{2}$ . Again the only missing edges are $x_{1} x_{2}, x_{1} x_{3}, x_{2} x_{3}, x_{1} y, x_{2} z, y w$ , so $H^{-} - v_{6}$ is also co-Bird.

2.1step 1.1L1L2

The graphs $Q$ and $K_{2}$ both have at most five vertices, so [L1] gives the Erdős-Hajnal property for each. By [L2], $H$ also has the Erdős-Hajnal property.

3.1step 2.1L3algebra

In $H^{+}$ , delete $v_{3}$ . The remaining six vertices ${v, v_{1}, v_{2}, v_{4}, v_{5}, v_{6}}$ have edge set ${v v_{1}, v v_{2}, v_{1} v_{2}, v_{1} v_{5}, v_{1} v_{6}, v_{2} v_{4}, v_{2} v_{5}, v_{4} v_{5}, v_{4} v_{6}}$ . Relabel them by $x_{1} = v$ , $x_{2} = v_{6}$ , $x_{3} = v_{5}$ , $y = v_{4}$ , $z = v_{2}$ , and $w = v_{1}$ . Then the only missing edges are $x_{1} x_{2}, x_{1} x_{3}, x_{2} x_{3}, x_{1} y, x_{2} z, y w$ , which are exactly the Bird edges. Therefore $H^{+} - v_{3}$ is co-Bird.

4.1step 2.1step 3.1step 1.2∎

Steps 2.1-3.1 together with step 1.2 verify the finite witness data used in the Bird route: $H$ has the Erdős-Hajnal property, and both $H^{+}$ and $H^{-}$ contain induced co-Bird subgraphs.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

31 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

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Figure 6 and Lemma 2.2 (standard reference, not scraped)