coloring_reversal_weight_add
The sum of the weights of a proper coloring kappa and its color reversal coloring_reversal kappa is equal to (n - 1) times the number of vertices.
Statement
theorem coloring_reversal_weight_add {V : Type*} [Fintype V] {G : SimpleGraph V} {n : ℕ} (κ : G.Coloring (Fin n)) : (∑ v : V, (coloring_reversal κ v : ℕ)) + (∑ v : V, (κ v : ℕ)) = (n - 1) * Fintype.card V
- Source
- arXiv:2610.31785 Proposition 3.16 proof
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- coloring_reversalFor a proper coloring kappa : V -> Fin n of a simple graph G, the coloring obtained by mapping each color c to n - 1 - c is also a proper…
Read back from the Lean
For any finite type V, any simple graph G on V, any natural number n, and any proper coloring κ : G.Coloring (Fin n) of G with colors in Fin n:
the sum over all vertices v : V of (coloring_reversal κ v : ℕ) plus the sum over all v : V of (κ v : ℕ) is equal to (n - 1) * Fintype.card V.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof combines the two sums over the vertices into a single sum of vertex-wise values $(\text{coloring\_reversal}(\kappa)(v) + \kappa(v))$. By definition, the reversed coloring assigns each vertex the color $(n - 1) - \kappa(v)$, so the vertex-wise sum is $(n - 1 - \kappa(v)) + \kappa(v) = n - 1$. Summing this constant value over all vertices of $V$ yields $(n - 1) \cdot |V|$.
The sum of the two color weight sums over $V$ can be expressed as a single sum of vertex-wise sums: $\sum_{v \in V} (\text{coloring\_reversal}(\kappa)(v) + \kappa(v))$.
Applying the distributivity of summation over addition in reverse (`Finset.sum_add_distrib`) merges the sum of the reversal coloring values and the sum of the original coloring values into a single summation over all vertices $v \in V$.
uses
Finset.sum_add_distribrw [← Finset.sum_add_distrib]For every vertex $v \in V$, the sum of the reversed color and the original color is $n - 1$.
By definition of `coloring_reversal`, the reversed color assigned to $v$ is $n - 1 - \kappa(v)$. Since $\kappa(v) < n$ (as $\kappa(v) \in \text{Fin } n$), we have $\kappa(v) \le n - 1$ by `Nat.le_pred_of_lt`. Therefore, $(n - 1 - \kappa(v)) + \kappa(v) = n - 1$ by `Nat.sub_add_cancel`.
uses
Nat.sub_add_cancel,Nat.le_pred_of_lthave h (v : V) : (coloring_reversal κ v : ℕ) + (κ v : ℕ) = n - 1 := Nat.sub_add_cancel (Nat.le_pred_of_lt (κ v).isLt)The sum evaluates to $(n - 1) \cdot |V|$, completing the proof.
Replacing each summand with $n - 1$ via `simp_rw [h]` yields the sum of the constant $n - 1$ over all vertices in $V$. Summing this constant over the finite type $V$ produces $|V| \cdot (n - 1)$, which simplifies to $(n - 1) \cdot |V|$ by commutativity of multiplication (`mul_comm`).
uses
mul_commsimp_rw [h] simp [mul_comm]
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of the first function plus the sum of the second function: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
Nat.sub_add_cancel- For natural numbers, if $m \le n$, then $(n - m) + m = n$.
Nat.le_pred_of_lt- If $n < m$ for natural numbers, then $n \le m - 1$ (the predecessor of $m$).
mul_comm- Multiplication is commutative: $a * b = b * a$.
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 sum of the weight of a proper coloring and its reversal equals (n - 1) * |V|. -/theorem coloring_reversal_weight_add {V : Type*} [Fintype V] {G : SimpleGraph V} {n : ℕ} (κ : G.Coloring (Fin n)) : (∑ v : V, (coloring_reversal κ v : ℕ)) + (∑ v : V, (κ v : ℕ)) = (n - 1) * Fintype.card V := by rw [← Finset.sum_add_distrib] have h (v : V) : (coloring_reversal κ v : ℕ) + (κ v : ℕ) = n - 1 := Nat.sub_add_cancel (Nat.le_pred_of_lt (κ v).isLt) simp_rw [h] simp [mul_comm]