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.

✓ 2 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 2 also cleared it.

Leaf Reducibility and Wonderful Families — Examples

1 · Prerequisites

2 · Summary

These examples spend the two finite checks that the A-page proofs actually use. The first isolates the one-subdivided-star model behind the $E$ -graph route and the pendant-leaf deletion back to $P_{5}$ . The second records an explicit six-vertex witness graph for Bird, checks the homogeneous pair that gives it the Erdős-Hajnal property by substitution, and verifies the induced co-Bird models inside its $H^{+}$ and $H^{-}$ extensions.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

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

The $E$ -graph sits inside a one-subdivided star and deletes to the five-vertex path

Example

The $E$ -graph occurs as an induced subgraph of the $1$ -subdivision of $K_{1, 3}$ , and deleting the remaining pendant leaf recovers the five-vertex path.

Facts & Assumptions

Given: The $1$ -subdivision of $K_{1, 3}$ with center $c$ , subdivision vertices $s_{1}, s_{2}, s_{3}$ , and leaves $t_{1}, t_{2}, t_{3}$ .

[L1]

The $E$ -graph has edge set ${p_{1} p_{2}, p_{2} p_{3}, p_{3} p_{4}, p_{4} p_{5}, p_{3} q}$ (The $E$ -graph and co- $E$ ).

[L2]

The path $P_{5}$ has five vertices in one chain and no other edges (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · direct finite check

1.1L1givenconstruct

On the six-vertex subset ${t_{1}, s_{1}, c, s_{2}, t_{2}, s_{3}}$ , the induced edges are $t_{1} s_{1}$ , $s_{1} c$ , $c s_{2}$ , $s_{2} t_{2}$ , and $c s_{3}$ . Relabelling $p_{1} = t_{1}$ , $p_{2} = s_{1}$ , $p_{3} = c$ , $p_{4} = s_{2}$ , $p_{5} = t_{2}$ , and $q = s_{3}$ turns this induced subgraph into the edge set from [L1]. Hence the selected subset is an induced copy of the $E$ -graph.

2.1step 1.1L2∎

Deleting the vertex $q = s_{3}$ from that induced copy leaves the five vertices $p_{1}, p_{2}, p_{3}, p_{4}, p_{5}$ with exactly the four path edges $p_{1} p_{2}, p_{2} p_{3}, p_{3} p_{4}, p_{4} p_{5}$ . By [L2], this is $P_{5}$ .

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

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.

Leaf Reducibility and Wonderful Families — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The EE-graph sits inside a one-subdivided star and deletes to the five-vertex path

Example

Facts & Assumptions

Verification

A six-vertex witness graph makes the Bird criterion explicit

Example

Facts & Assumptions

Verification

Sources

The $E$ -graph sits inside a one-subdivided star and deletes to the five-vertex path