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.1

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.

L1givenconstruct

2.1

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}$ .

step 1.1L2∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01‡ rests on unproved material (inherited)Open item page →

‡ Rests on 3 statements not proved in this library, by way of the results it cites. This item cites no such statement directly; it depends on results that do. The unproved premises it inherits are ‡ Strong Perfect Graph Theorem, ‡ Substituting perfect graphs preserves perfection and ‡ Weak Perfect Graph Theorem. Each is recorded with a citation to the literature and is not established here, because the track that would prove it has not yet been developed in this library. Everything else in this proof is proved here.

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.1

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}]$ .

givenconstruct

1.2

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.

L3givenalgebra

2.1

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.

step 1.1L1L2

3.1

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.

step 2.1L3algebra

4.1

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.

step 2.1step 3.1step 1.2∎

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