AFTD Auto-Formalizing Theoretical Domains

coloring_reversal_weight_add

theoremverified

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

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

    line 6

    uses Finset.sum_add_distrib

      rw [← Finset.sum_add_distrib]
  2. 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`.

    lines 7–8

    uses Nat.sub_add_cancel, Nat.le_pred_of_lt

      have h (v : V) : (coloring_reversal κ v : ℕ) + (κ v : ℕ) = n - 1 :=
        Nat.sub_add_cancel (Nat.le_pred_of_lt (κ v).isLt)
  3. 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`).

    lines 9–10

    uses mul_comm

      simp_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

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