op_258_card_fiber_sum
For any colouring c of the edges of the complete graph on Fin n, the sum over the colours actually used of the number of edges of that colour equals C(n,2).
Statement
theorem op_258_card_fiber_sum (n : ℕ) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) : (∑ i ∈ Finset.univ.image c, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ)) = (n.choose 2 : ℝ)
- Source
- step towards op_258_triangle_forcing_implies_decay_ramsey
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- op_258_forces_of_capacity_lt_oneIf k ≥ 2 and Σ_i min(a_i, 1 - 1/(k-1)) < 1, then every a-bounded colouring of K_n for large n already contains a monochromatic K_k; i.e. a…
- op_258_one_le_tsum_of_boundedLet n ≥ 2, let a : ℕ+ → ℝ and let c be an a-bounded colouring of the edges of K_n. Then the ENNReal-sum of the a i is at least 1.
The proof, explained
The edges of the complete graph K_n are partitioned into fibers by the edge colouring c, so the sum of the sizes of the colour classes equals the total number of edges by `Finset.card_eq_sum_card_fiberwise`. The total edge count of K_n is C(n, 2) by `SimpleGraph.card_edgeFinset_top_eq_card_choose_two`. Casting this fiber partition identity from natural numbers to real numbers yields the result.
The total number of edges of K_n equals the sum of the cardinalities of the colour classes.
By `Finset.card_eq_sum_card_fiberwise`, partitioning any finite set into the fibers of a function expresses its cardinality as the sum of the fiber sizes over its image. Applying this to the colouring c on the full edge set of K_n shows that the total number of edges equals the sum over all used colours i of the number of edges assigned colour i.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_image_of_mem,Finset.mem_univhave hsplit : ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card : ℕ) = ∑ i ∈ Finset.univ.image c, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card) := Finset.card_eq_sum_card_fiberwise (fun x _ => Finset.mem_image_of_mem c (Finset.mem_univ x))
The complete graph K_n has C(n,2) edges.
Rewriting with `Finset.card_univ` and `SimpleGraph.edgeFinset_card` expresses the size of the universal edge set as the cardinality of the complete graph's edge finset. By `SimpleGraph.card_edgeFinset_top_eq_card_choose_two`, this equals C(|Fin n|, 2), which simplifies to C(n,2) since |Fin n| = n.
uses
Finset.card_univ,SimpleGraph.edgeFinset_card,SimpleGraph.card_edgeFinset_top_eq_card_choose_twohave hcard : ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card : ℕ) = n.choose 2 := by rw [Finset.card_univ, ← SimpleGraph.edgeFinset_card (G := SimpleGraph.completeGraph (Fin n))] exact SimpleGraph.card_edgeFinset_top_eq_card_choose_two (V := Fin n) |>.trans (by simp)
The sum of the fiber cardinalities in ℝ equals the total number of edges cast to ℝ.
Rewriting with the integer partitioning identity `hsplit` and using `push_cast` moves the coercion from ℕ to ℝ inside the finite summation, completing the equality by reflexivity.
have key : (∑ i ∈ Finset.univ.image c, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ)) = (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card : ℕ) : ℝ) := by rw [hsplit] push_cast rfl
The sum of the fiber cardinalities in ℝ equals C(n,2).
Rewriting the sum with `key` replaces it by the total edge count in ℝ, and then rewriting with `hcard` replaces the edge count with C(n,2).
rw [key, hcard]
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set s equals the sum over b ∈ t of the cardinalities of the fibers f⁻¹(b) ∩ s, provided f maps s into t.
Finset.mem_image_of_mem- If an element a belongs to s, then f(a) belongs to the image of s under f.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
SimpleGraph.edgeFinset_card- The cardinality of the edge finset of a graph equals the cardinality of its edge set.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two- The complete graph on a finite vertex set V has C(|V|, 2) edges.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The colour classes of any colouring of the edges of K_n partition its `C(n,2)` edges, so their cardinalities sum to `C(n,2)`. -/theorem op_258_card_fiber_sum (n : ℕ) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) : (∑ i ∈ Finset.univ.image c, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ)) = (n.choose 2 : ℝ) := by have hsplit : ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card : ℕ) = ∑ i ∈ Finset.univ.image c, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card) := Finset.card_eq_sum_card_fiberwise (fun x _ => Finset.mem_image_of_mem c (Finset.mem_univ x)) have hcard : ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card : ℕ) = n.choose 2 := by rw [Finset.card_univ, ← SimpleGraph.edgeFinset_card (G := SimpleGraph.completeGraph (Fin n))] exact SimpleGraph.card_edgeFinset_top_eq_card_choose_two (V := Fin n) |>.trans (by simp) have key : (∑ i ∈ Finset.univ.image c, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ)) = (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card : ℕ) : ℝ) := by rw [hsplit] push_cast rfl rw [key, hcard]