Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck 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.

A split set with both a complete and an anticomplete outside vertex yields a nontrivial module

Statement

Let G be a bull-free graph and let S⊆V(G) be a split set. Suppose there are vertices c,a∈V(G)∖S such that c is complete to S and a is anticomplete to S. Then G has a nontrivial module.

Facts & Assumptions

Given: A bull-free graph G, a split set S⊆V(G), and vertices c,a∈V(G)∖S with c complete to S and a anticomplete to S.

[F1]

A set is split exactly when every outside vertex mixed on it has one of the two witnesses from the definition: either an induced three-vertex path, or a three-vertex configuration with exactly one edge among the three vertices (A split set in a bull-free graph).

[F2]

A module is a vertex set to which every outside vertex is complete or anticomplete (Modules of a graph, and the trivial modules).

[L1]

Bull-freeness is preserved by complementation (A graph is bull-free if and only if its complement is bull-free).

Proof

technique · direct
1.1F1givenalgebra

First claim: if x∈V(G)∖S is neither complete nor anticomplete to S, then either c is adjacent to a and x is adjacent to c, or c is nonadjacent to a and x is nonadjacent to a. Indeed, let S1 be the neighbors of x in S and S2=S∖S1; both are nonempty. By [F1], either there are u,v∈S1 and w∈S2 with u-v-w an induced path, or there are u∈S1 and v,w∈S2 with uw∈E(G) while uv,vw∉E(G). In the first case bull-freeness rules out both x-a and xc‾ simultaneously, because otherwise {a,x,u,v,w} and then {x,v,w,c,a} would be bulls. In the second case bull-freeness similarly rules out both xc‾ and x-a, because otherwise {x,u,w,c,v} and then {a,x,u,c,v} would be bulls.

2.1step 1.1L1F1F2chooseinduction

Let C be the set of vertices complete to S, let A be the set of vertices anticomplete to S, and let X=V(G)∖(S∪C∪A). Either every vertex of C has a neighbor in A, or every vertex of A has a nonneighbor in C: otherwise a vertex of C anticomplete to A and a vertex of A complete to C would contradict each other. Replacing G by G‾ if necessary preserves bull-freeness, splitness, and modules by [L1], [F1], and [F2], so assume that every vertex of C has a neighbor in A. Step 1.1 then makes C complete to X. Let A′ be the set of vertices of A lying on an induced path x-a1-⋯-ak with x∈X and all ai∈A. We prove by induction on k that ak is complete to C. For k=1, if c′a1 were a nonedge for some c′∈C, step 1.1 applied to x,c′,a1 would force xa1 to be a nonedge, a contradiction. For k>1, put a0=x and assume the result through ak−1. Choose s∈S nonadjacent to ak−2 when k=2, which is possible because x is mixed on S; for k>2 any s∈S works because ak−2∈A. If some c′∈C were nonadjacent to ak, then {s,c′,ak−2,ak−1,ak} would be a bull: c′,ak−2,ak−1 form its triangle, while s and ak are pendant at c′ and ak−1. Hence A′ is complete to C.

3.1step 2.1F2∎

Put Z=S∪X∪A′. Every vertex of A∖A′ is anticomplete to Z: it is anticomplete to S by definition, and any path from it to X∪A′ through A has a shortest, hence induced, subpath that would put it in A′. Every vertex of C is complete to Z by step 2.1 and the definition of C. Thus every outside vertex is complete or anticomplete to Z, so Z is a module by [F2]. The set Z is nontrivial because S⊆Z and ∣S∣>1, while c∈C∖Z, so Z≠V(G).

Depends on

Used by

Dependency tree · two levels

15 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