Alphabeta Math
LemmaStatement: AI-generatedProof: AI-generated
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.

Independence numbers of disjoint families and complete joins

Statement

Let J1,…,Jt be nonempty finite simple graphs, where t≥1. Let D be their disjoint union, formed using tagged copies, and let Q be their iterated complete join: it has the same tagged parts, retains the edges within each part, and has every possible edge between distinct parts. An independent set is a vertex set containing no adjacent pair, and α(J) is the maximum size of such a set in J. Then α(D)=∑j=1tα(Jj) and α(Q)=max⁡1≤j≤tα(Jj). If t≥2, this maximum is strictly less than the sum.

Facts & Assumptions

[F1]

In the tagged disjoint family, the parts are pairwise disjoint, each part is a copy of its graph, and no edges join distinct parts. Tagged graph families with anticomplete parts

[F2]

The complete connection of two disjoint graphs retains their internal edges and adds every edge between their vertex sets. The complete connection of two disjoint graphs

[F3]

For a finite simple graph, an independent set contains no two adjacent vertices, and its independence number is the attained maximum of the sizes of its independent sets. A nonempty graph has independence number at least one. Cliques, independent sets, clique number and independence number

[F4]

The cardinality of a finite union of pairwise disjoint finite sets is the sum of their cardinalities; a finite sum splits over a partition of its index set. The sum rule: a finite disjoint union is finite with | A ∪ B| = | A| + | B| and |⋃_i ∈ I Aᵢ| = ∑_i ∈ I| Aᵢ|, and a sum over a finite index set splits along a partition

Proof

Given: The graphs and constructions in the statement.

Goal: Prove the two formulas and the strict inequality when t≥2.

1.1F1F3F4

Let S be independent in D. Its intersection with the jth tagged part corresponds to an independent set of Jj, so it has at most α(Jj) vertices. The intersections partition S; the finite sum rule gives ∣S∣≤∑j=1tα(Jj). Conversely, choose an independent set of size α(Jj) in each Jj. Their tagged copies have no edges between them, so their union is independent in D and has size ∑j=1tα(Jj). Therefore α(D) equals that sum.

1.2F1F2F3

By the complete-connection definition, successive joins retain all internal edges and make every two distinct tagged parts completely adjacent. Thus an independent set of Q meets at most one part, and its size is at most max⁡jα(Jj); this also holds for the empty set. Choose an index attaining that finite maximum and a maximum independent set in its part. It remains independent in Q, so α(Q)=max⁡jα(Jj).

2.1step 1.1step 1.2F3F4∎

If t≥2, choose an index r attaining the maximum. Every Jj is nonempty, so every α(Jj)≥1; in particular the sum over indices other than r is positive. Splitting the sum at r gives ∑jα(Jj)>α(Jr)=max⁡jα(Jj). Together with the preceding steps this proves all assertions.

Depends on

Used by · 1

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.