Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-28
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 cV(G)V(H) be complete to V(H), and let uV(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 k5, 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.1

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. Since neither outcome holds, k>5 and u is not complete to H. Since {u,h2,h3,c,hk1} is not a bull, u is adjacent to at least one of h3,hk1; 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 hi2,hi1, while u is adjacent to hk. If ik1, then {hi,hi1,hi2,u,hk} is a bull, so i=k15. But then {hi,hi1,hi2,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.

F1F2givenchoosealgebra
2.1

Since u is adjacent to h1 but to no consecutive pair on H, the vertices {u,h1,h2,c,hi} with 4ik1 would induce a bull unless u were adjacent to every such hi. Reflecting the cycle through h1 gives the same conclusion for h3,,hk2. 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.

step 1.1F2algebra
3.1

One of the two stated outcomes must hold.

step 1.1step 2.1

Depends on

Used by

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