Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (gpt-5.6-terra)audited 2026-08-28 rests on unproved material
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.

Rests on 1 statement not proved in this library. Every dependency marked below is recorded with a citation but is not established here, because the track that would prove it has not yet been developed in this library. Everything else in this proof is proved here.

For a vertex in a basic bull-free graph, either its neighborhood or its antineighborhood is perfect

Statement

Let G be a basic bull-free graph and let uV(G). Let N be the set of neighbors of u, and let M be the set of nonneighbors of u. Then at least one of the induced graphs G[N] and G[M] is perfect.

Facts & Assumptions

Given: A basic bull-free graph G, a vertex uV(G), its neighborhood N, and its antineighborhood M.

[L1]

In a basic bull-free graph, a vertex outside a hole that is nonadjacent to a complete outside witness is either complete to the hole or is in the exceptional five-hole case; in particular it has at least H2 neighbors on that hole (In a basic bull-free graph, an odd hole with a complete outside vertex has tightly constrained neighbors).

[L2]

In a basic bull-free graph, a vertex adjacent to an anticomplete outside witness has at least H/2 nonneighbors on the hole (In a basic bull-free graph, an odd hole with an anticomplete outside vertex forbids consecutive neighbors).

[L3]

A finite graph is perfect exactly when it contains no odd hole and no odd antihole (Strong Perfect Graph Theorem ).

[L4]

Bull-freeness, and therefore basicness, is preserved by complementation (A graph is bull-free if and only if its complement is bull-free, Basic and composite bull-free graphs).

Proof

technique · direct
1.1

Suppose neither G[N] nor G[M] is perfect. First they cannot both contain odd holes. Indeed, let HNG[N] and HMG[M] be odd holes of lengths n and m. Every vertex of HM is nonadjacent to u, while u is complete to HN, so [L1] gives each vertex of HM at least n2 neighbors in HN. Thus there are at least m(n2) cross edges. On the other hand every vertex of HN is adjacent to u, while u is anticomplete to HM, so [L2] gives each vertex of HN at least (m+1)/2 nonneighbors in HM. Hence there are at least n(m+1)/2 cross nonedges. Since there are only mn cross pairs altogether, we obtain m(n2)+n(m+1)/2mn, equivalently mn4m+n0, impossible because m,n5 make the left-hand side at least m+5>0.

L1L2 L3algebra
2.1

By [L4], the same argument in G shows that G[N] and G[M] cannot both contain odd antiholes. If G[N] contained an odd hole, then step 1.1 would force G[M] to contain no odd hole, so [L3] would give an odd antihole HM in G[M]. Because a 5-antihole is also a 5-hole, step 1.1 excludes the case HM=5, and the same complement argument excludes HN=5; hence both have length at least 7. Now every vertex of HM is nonadjacent to u, so [L1] applied to the odd hole HN with complete outside vertex u makes each vertex of HM complete to HN. Applying the same lemma in G reverses the roles of hole and antihole and shows that each vertex of HN is anticomplete to HM, contradiction. Therefore G[N] has no odd hole, and by [L3] it must contain an odd antihole. Symmetrically, G[M] contains an odd hole.

step 1.1L1 L3L4algebra
3.1

Take the odd antihole HNG[N] and the odd hole HMG[M] from step 2.1, with lengths n and m. By [L2], each vertex of HN has at least (m+1)/2 nonneighbors in HM. Applying [L2] in the complement graph, where HN becomes an odd hole and u is anticomplete to it, shows that each vertex of HM has at least (n+1)/2 neighbors in HN. Hence the number of cross nonedges is at least n(m+1)/2 and the number of cross edges is at least m(n+1)/2. Their sum is at least (2mn+m+n)/2>mn, impossible. This contradiction proves that at least one of G[N] and G[M] is perfect.

step 2.1L2L4algebra

Depends on

Used by

Dependency tree · two levels

13 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