ExampleConstruction: AI-adaptedVerification: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-07

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 first co-Bird witness by adjacency

Example

On six distinct vertices $(x, y, u, a, b, c)$ take exactly the edges $x a, x b, x c, y a, y b, y c, x u, u a, a b$ . This graph is co-Bird and realizes the edge-plus-isolate obstruction configuration.

Facts & Assumptions

[F1]

The edge-plus-isolate co-Bird obstruction supplies the following statement: Let $G$ be a finite simple co-Bird-free graph. Let $x, y, u$ be distinct vertices outside the indicated induced subgraph, with $x y \notin E (G)$ , $u x \in E (G)$ and $u y \notin E (G)$ , and with $x, y$ complete to that subgraph. If $H = {a, b, c}$ induces just the edge $a b$ , then $u$ cannot be mixed on ${a, b}$ and nonadjacent to $c$ .

[F2]

The Bird graph and co-Bird supplies the following definition: The Bird graph is the graph on vertices ${x_{1}, x_{2}, x_{3}, y, z, w}$ with edge set ${x_{1} x_{2}, x_{2} x_{3}, x_{1} x_{3}, x_{1} y, x_{2} z, y w} .$ So ${x_{1}, x_{2}, x_{3}, y, z}$ spans the bull, and $w$ is a new leaf attached to the horn vertex $y$ . The co-Bird graph is the complement of the Bird graph.

Verification

Given: The graph, vertices, sets and hypotheses in the example.

1.1F2given

The fifteen unordered pairs split into nine edges $x a, x b, x c, y a, y b, y c, x u, u a, a b$ and six nonedges $x y, y u, u b, u c, a c, b c$ . Under $(x, y, u, a, b, c) \mapsto (w, y, x_{1}, z, x_{3}, x_{2})$ the latter become precisely $w y, y x_{1}, x_{1} x_{3}, x_{1} x_{2}, z x_{2}, x_{3} x_{2}$ , the Bird edges. The map is bijective and hence verifies both edges and nonedges of co-Bird.

2.1F1∎

The induced set ${a, b, c}$ has just edge $a b$ , the nonadjacent pair $x, y$ is complete to it, and $u$ sees $x, a$ but misses $y, b, c$ . These are exactly the prohibited data of the first obstruction; the example itself contains co-Bird and therefore does not satisfy that lemma’s freeness assumption.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

4 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

Huang–Ju–Zhou, Erdős–Hajnal beyond the five-vertex path, §6.2, Figure 9, first witness (standard reference, not scraped)