Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-09-24 (gpt-6-sol)
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.

In a basic bull-free graph, an odd hole with a complete outside vertex has tightly constrained neighbors

Statement

Let G be a basic bull-free graph, let H be an odd hole in G with ∣V(H)∣≥5, let c∈V(G)∖V(H) be complete to V(H), and let u∈V(G)∖V(H) be nonadjacent to c. Then either:

  1. u is complete to V(H); or
  2. ∣V(H)∣=5 and u has at least three neighbors in V(H).

Facts & Assumptions

Given: A basic bull-free graph G, an odd hole H with vertices h1,…,hk in cyclic order and k≥5, a vertex c complete to V(H), and a vertex u nonadjacent to c.

[F1]

A basic bull-free graph is a bull-free graph that is not composite (Basic and composite bull-free graphs).

[F2]

A hole is an induced cycle (Holes, antiholes, and odd holes).

Proof

technique · direct
1.1F1F2givenchoosealgebra

Because G is basic, u cannot be anticomplete to V(H): otherwise the odd hole H would have the complete outside vertex c and the anticomplete outside vertex u, making G composite and contradicting [F1]. Assume neither outcome of the Statement holds. By cyclic symmetry choose h1 adjacent to u. Suppose that u is adjacent to h2. Since {hk,h1,u,h2,h3} is not a bull, u is adjacent to at least one of hk,h3; after reversing and shifting the cyclic labels in the second case, we may assume that u is adjacent to hk. If k=5, the three distinct neighbors h1,h2,hk give outcome 2, contrary to our assumption. Thus k>5, and outcome 1 failing means u is not complete to H. Since {u,h2,h3,c,hk−1} is not a bull, u is adjacent to at least one of h3,hk−1; reflecting the cyclic labels through h1 if necessary, we may assume that u is adjacent to h3. Let i>3 be minimal with u nonadjacent to hi. Minimality makes u adjacent to hi−2,hi−1, while u is adjacent to hk. If i≠k−1, then {hi,hi−1,hi−2,u,hk} is a bull, so i=k−1≥5. But then {hi,hi−1,hi−2,u,h1} is a bull, a contradiction. Thus u is not adjacent to h2; applying the same argument to any putative consecutive pair shows that u has no two consecutive neighbors on H.

2.1step 1.1F2algebra

Since u is adjacent to h1 but to no consecutive pair on H, the vertices {u,h1,h2,c,hi} with 4≤i≤k−1 would induce a bull unless u were adjacent to every such hi. Reflecting the cycle through h1 gives the same conclusion for h3,…,hk−2. In particular u is adjacent to both h3 and h4, a consecutive pair, contradicting step 1.1. Therefore our assumption that neither outcome holds was impossible.

3.1step 1.1step 2.1∎

One of the two stated outcomes must hold.

Depends on

Used by

Nothing in the library uses this result yet.

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