AFTD Auto-Formalizing Theoretical Domains

op_258_card_fiber_sum

theoremverified

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.

  1. 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.

    lines 6–9

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_image_of_mem, Finset.mem_univ

      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))
  2. 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.

    lines 10–12

    uses Finset.card_univ, SimpleGraph.edgeFinset_card, SimpleGraph.card_edgeFinset_top_eq_card_choose_two

      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)
  3. 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.

    lines 13–18

      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
  4. 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).

    line 19

      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

/-- 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]
See it in the graphDiscuss this resultChallenge it