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 be nonempty finite simple graphs, where . Let be their disjoint union, formed using tagged copies, and let 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 is the maximum size of such a set in . Then and . If , this maximum is strictly less than the sum.
Statement references
Facts & Assumptions
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
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
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
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 .
Let be independent in . Its intersection with the th tagged part corresponds to an independent set of , so it has at most vertices. The intersections partition ; the finite sum rule gives . Conversely, choose an independent set of size in each . Their tagged copies have no edges between them, so their union is independent in and has size . Therefore equals that sum.
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 meets at most one part, and its size is at most ; 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 , so .
If , choose an index attaining the maximum. Every is nonempty, so every ; in particular the sum over indices other than is positive. Splitting the sum at gives . Together with the preceding steps this proves all assertions.
Depends on
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Tagged graph families with anticomplete parts
- The complete connection of two disjoint graphs
- Cliques, independent sets, clique number and independence number
- 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
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.