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 Berge cycle bounds the union of its hyperedges
Statement
Let and let be the distinct edges of a Berge cycle of length in a finite -uniform hypergraph. Then .
Statement references
Facts & Assumptions
Berge cycles, incidence graphs and girth defines a Berge cycle using distinct vertices , cyclically. r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s gives , and The cardinality | A| of a finite set interprets the finite cardinalities.
Double counting: ∑_x ∈ X| Rₓ| = | R| = ∑_y ∈ Y| Rʸ| for a relation between finite sets states that for finite sets and a relation , the sum of the row-fibre cardinalities and the sum of the column-fibre cardinalities both equal . The sum ∑_i ∈ S aᵢ over a finite index set, and its product form defines these natural-valued sums independently of enumeration, with reindexing and constant-summand clauses.
Clauses 1--4 of Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ) give additivity, constant sums, splitting and monotonicity for finite sums of natural numbers. Applying them to an enumeration as in The sum ∑_i ∈ S aᵢ over a finite index set, and its product form gives the corresponding laws for a finite index set; a finite list may be extended by zeros to a sequence on .
Proof
Given: The hypotheses of the statement.
Goal: Its asserted conclusion.
Put and . These are finite, with . Define and for . The row fibre at has size and the column fibre at is , of size . Double counting therefore gives .
Every lies in at least one displayed edge, so and is a natural number satisfying . Additivity and the constant-summand law yield .
Each cycle vertex belongs to the two distinct edges , so , also when . Enumerate with the distinct cycle vertices first. By splitting the sum after these vertices, monotonicity and the constant-summand law give , since the remaining terms are nonnegative. Thus , and cancellation gives .
Depends on
- Berge cycles, incidence graphs and girth
- r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s
- The cardinality | A| of a finite set
- Double counting: ∑_x ∈ X| Rₓ| = | R| = ∑_y ∈ Y| Rʸ| for a relation between finite sets
- The sum ∑_i ∈ S aᵢ over a finite index set, and its product form
- Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ)
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.