Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-09-01
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.

Mixed anticonnected blocks lift pattern obstructions to the ambient graph

Statement

Let G be a finite graph, let vV(G), and let B1,,BsV(G){v} be pairwise disjoint nonempty sets. Assume:

  1. each Bi is anticonnected;
  2. 0<NG(v)Bi<12Bi for each i[s]; and
  3. for all distinct i,j[s], either Bi is complete to Bj, or both Bi is η-sparse to Bj and Bj is η-sparse to Bi for some real η0.

Let J be the graph on vertex set [s] defined by

ijE(J)Bi is complete to Bj.

Then:

  1. if X[s] is a clique of size t in J, then G contains an induced copy of the complement of the 1-subdivision of K1,t;
  2. if F is a graph on vertex set [q] with qs and (q1)η<1, and if J[{1,,q}]=F, then G contains an induced copy of F with the vertex i realized inside Bi for every i[q];
  3. if H is a graph on vertex set [q] with qs, with distinguished vertices 1,2 satisfying 12E(H) and (q1)η<12, and if J[{1,,q}]=H, then G contains an induced copy of H+.

Facts & Assumptions

Given: The graph G, the outside vertex v, the disjoint sets B1,,Bs, the parameter η, and the auxiliary graph J from the Statement.

[L1]

If Bi is anticonnected and 0<NG(v)Bi<Bi, then v is mixed on Bi, so there exist nonadjacent bi,biBi such that vbiE(G) and vbiE(G) (A vertex mixed on an anticonnected set yields opposite adjacency on a nonedge).

[L2]

A complete pair has all cross-edges, while a mixed pair is neither complete nor anticomplete (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

[L3]

If Bi is η-sparse to Bj, then every vertex of Bi has at most ηBj neighbours in Bj (Sparsity of one vertex set to another, and weak sparsity of a pair).

[L4]

For adjacent distinguished vertices 1,2 of H, the graph H+ is obtained by adjoining a new vertex adjacent exactly to 1 and 2 (The graphs H+ and H for two distinguished vertices).

Proof

technique · direct constructive lifting
1.1

For each i[s], apply [L1] to choose nonadjacent vertices bi,biBi with vbiE(G) and vbiE(G).

L1givenchoose
1.2

Now assume J[{1,,q}]=F and (q1)η<1. Choose x1B1 arbitrarily. Suppose x1,,xj1 have been chosen with 2jq, so that for all 1i<k<j one has xixkE(G) if and only if ikE(F).

givenconstruct
1.3

Assume instead that J[{1,,q}]=H, that 12E(H), and that (q1)η<12. Because 0<NG(v)Bi for i=1,2, choose x1B1 and x2B2 adjacent to v. Since 12E(H)=E(J[{1,,q}]), the pair (B1,B2) is complete, so x1x2E(G). Suppose now that x1,,xj1 have been chosen with 3jq so that vx1,vx2E(G), vxiE(G) for 3i<j, and xixkE(G) if and only if ikE(H) for all 1i<k<j.

givenchoose
2.1

Let X={i1,,it} be a clique in J. By definition of J, the pairs (Bir,Biu) are complete for all ru, so every vertex chosen from one selected block is adjacent to every vertex chosen from another selected block. Together with step 1.1, this shows that on the vertex set {v,bi1,bi1,,bit,bit} the only nonedges are vbir and birbir for r[t]. That is exactly the nonedge pattern of the complement of the 1-subdivision of K1,t, with v as the complemented center, bir as the subdivision vertex, and bir as the corresponding leaf.

step 1.1L2construct
2.2

For each i<j with ijE(F)=E(J[{1,,q}]), the pair (Bi,Bj) is not complete, so hypothesis 3 and [L3] imply that xi has at most ηBj neighbours in Bj. Therefore at most (j1)ηBj vertices of Bj violate one of the required nonadjacency conditions to the previously chosen vertices. Since (q1)η<1 and j1q1, some vertex xjBj avoids all those forbidden sets. For such a choice, every required edge holds automatically because whenever ijE(F)=E(J) the pair (Bi,Bj) is complete.

step 1.2L2L3choose
3.1

By induction on j, steps 1.2 and 2.2 produce vertices x1,,xq with xixjE(G) if and only if ijE(F) for all distinct i,j[q]. Hence G[{x1,,xq}] is an induced copy of F. This proves assertion 2.

step 1.2step 2.2induction
4.1

For j3, hypothesis 2 gives fewer than 12Bj neighbours of v in Bj, so more than 12Bj vertices of Bj are nonadjacent to v. As in step 2.2, the nonedge requirements to the previously chosen xi exclude at most (j1)ηBj<(q1)ηBj<12Bj further vertices. Hence some xjBj is simultaneously nonadjacent to v and satisfies xixjE(G) if and only if ijE(H) for every i<j. Inducting on j produces vertices x1,,xq such that the old vertices induce H, the new vertex v is adjacent exactly to x1 and x2, and therefore G[{v,x1,,xq}] is an induced copy of H+ by [L4]. This proves assertion 3.

step 1.3L3L4discharge-construct

Depends on

Used by

Dependency tree · two levels

12 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