LemmaStatement: AI-adaptedProof: 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.

A mixed vertex on E is pure on both terminal edges

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. Let $S = {p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, q}$ induce $E$ , with edges exactly $p_{1} p_{2}, p_{2} p_{3}, p_{3} p_{4}, p_{4} p_{5}, p_{3} q$ . If $u$ is mixed on $S$ , it is nevertheless pure to both terminal edges ${p_{1}, p_{2}}$ and ${p_{4}, p_{5}}$ .

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

[F3]

The $E$ -graph and co- $E$ supplies the following definition: The $E$ -graph is the graph on vertices ${p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, q}$ with edge set ${p_{1} p_{2}, p_{2} p_{3}, p_{3} p_{4}, p_{4} p_{5}, p_{3} q} .$ Thus $p_{1} p_{2} p_{3} p_{4} p_{5}$ is a five-vertex path and $q$ is a leaf attached to its middle vertex $p_{3}$ . The co- $E$ graph is the complement of this graph.

Proof

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

1.1

Use the exact five-edge description of $S$ . Suppose $u$ mixes on $p_{1} p_{2}$ . Each of $q, p_{4}, p_{5}$ is isolated from this edge; the edge-plus-isolate obstruction forces all three to be neighbours of $u$ .

givenF1F3

1.2

If $u p_{1}$ is present and $u p_{2}$ absent, then $u p_{3}$ must be present: otherwise the path $p_{3} - p_{4} - p_{5}$ with isolate $p_{1}$ has precisely the prohibited neighbourhood. Now the path $p_{2} - p_{3} - q$ with isolate $p_{5}$ has that same prohibited pattern, a contradiction.

1.3

If $u p_{2}$ is present and $u p_{1}$ absent, the edge $p_{3} q$ with isolate $p_{1}$ forces $u p_{3}$ to be present. The path $p_{1} - p_{2} - p_{3}$ with isolate $p_{5}$ then violates the path-plus-isolate obstruction.

F1F2

2.1

The two possibilities exhaust mixing on $p_{1} p_{2}$ . Reflection $p_{j} \mapsto p_{6 - j}$ fixing $q$ preserves all five edges and the external hypotheses, and proves the same conclusion for $p_{4} p_{5}$ .

F3∎

Depends on

Used by

Complete nonedge pairs force purity on induced E graphs Lemma

Dependency tree · two levels

6 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, Claim 6.5.2, terminal-edge cases (standard reference, not scraped)