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 v∈V(G), and let B1,…,Bs⊆V(G)∖{v} be pairwise disjoint nonempty sets. Assume:

  1. each Bi is anticonnected;
  2. 0<∣NG(v)∩Bi∣<12∣Bi∣ 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

ij∈E(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 q≤s and (q−1)η<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 q≤s, with distinguished vertices 1,2 satisfying 12∈E(H) and (q−1)η<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,bi′∈Bi such that vbi∈E(G) and vbi′∉E(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.1L1givenchoose

For each i∈[s], apply [L1] to choose nonadjacent vertices bi,bi′∈Bi with vbi∈E(G) and vbi′∉E(G).

1.2givenconstruct

Now assume J[{1,…,q}]=F and (q−1)η<1. Choose x1∈B1 arbitrarily. Suppose x1,…,xj−1 have been chosen with 2≤j≤q, so that for all 1≤i<k<j one has xixk∈E(G) if and only if ik∈E(F).

1.3givenchoose

Assume instead that J[{1,…,q}]=H, that 12∈E(H), and that (q−1)η<12. Because 0<∣NG(v)∩Bi∣ for i=1,2, choose x1∈B1 and x2∈B2 adjacent to v. Since 12∈E(H)=E(J[{1,…,q}]), the pair (B1,B2) is complete, so x1x2∈E(G). Suppose now that x1,…,xj−1 have been chosen with 3≤j≤q so that vx1,vx2∈E(G), vxi∉E(G) for 3≤i<j, and xixk∈E(G) if and only if ik∈E(H) for all 1≤i<k<j.

2.1step 1.1L2construct

Let X={i1,…,it} be a clique in J. By definition of J, the pairs (Bir,Biu) are complete for all r≠u, 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.

2.2step 1.2L2L3choose

For each i<j with ij∉E(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 (j−1)η∣Bj∣ vertices of Bj violate one of the required nonadjacency conditions to the previously chosen vertices. Since (q−1)η<1 and j−1≤q−1, some vertex xj∈Bj avoids all those forbidden sets. For such a choice, every required edge holds automatically because whenever ij∈E(F)=E(J) the pair (Bi,Bj) is complete.

3.1step 1.2step 2.2induction

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

4.1step 1.3L3L4discharge-construct∎

For j≥3, hypothesis 2 gives fewer than 12∣Bj∣ neighbours of v in Bj, so more than 12∣Bj∣ vertices of Bj are nonadjacent to v. As in step 2.2, the nonedge requirements to the previously chosen xi exclude at most (j−1)η∣Bj∣<(q−1)η∣Bj∣<12∣Bj∣ further vertices. Hence some xj∈Bj is simultaneously nonadjacent to v and satisfies xixj∈E(G) if and only if ij∈E(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.

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