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

Example

On six distinct vertices $(y, u, a, b, c, d)$ take exactly the edges $y a, y b, y c, y d, u b, u c, u d, a b, b c$ . This graph is co-Bird and is the six-vertex witness for the path-plus-isolate obstruction.

Facts & Assumptions

[F1]

The path-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, d}$ induces the path $a - b - c$ and isolated vertex $d$ , then $u$ cannot be adjacent to $d$ and two consecutive vertices of the path and nonadjacent to the remaining endpoint.

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

The complement consists exactly of the six pairs $y u, u a, a c, a d, b d, c d$ . The other nine of the fifteen pairs are the stated edges. The bijection $(y, u, a, b, c, d) \mapsto (w, y, x_{1}, z, x_{3}, x_{2})$ sends these six pairs to $w y, y x_{1}, x_{1} x_{3}, x_{1} x_{2}, z x_{2}, x_{3} x_{2}$ , precisely the Bird edges, and sends the other pairs to co-Bird edges.

F2given

2.1

Here $a - b - c$ is induced, $d$ is isolated from that path, $y$ is complete to all four vertices and misses $u$ , while $u$ sees exactly $b, c, d$ among them. These are the six vertices of the co-Bird witness underlying the second obstruction. The obstruction's full hypothesis also requires a seventh vertex $x$ : add $x$ adjacent to $u, a, b, c, d$ and nonadjacent to $y$ ; the displayed induced co-Bird persists.

F1∎

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, second witness (standard reference, not scraped)