AFTD Auto-Formalizing Theoretical Domains

maxcut_pair_sum_comm

theoremverified

The number of bichromatic adjacent ordered pairs (v, w) with v in S and w in T equals the number with v in T and w in S.

Statement

theorem maxcut_pair_sum_comm {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]
    {k : ℕ} (ρ : V → Fin k) (S T : Finset V) :
    ∑ v ∈ S, ∑ w ∈ T, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) =
      ∑ v ∈ T, ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ)
Source
step towards maxcut_optimal_strong_of_degree_le (arXiv:2610.04948, Corollary 9)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • maxcut_welfare_splitFor any set S of players, the welfare of a coloring is A + 2B + C, where A counts bichromatic adjacent ordered pairs inside S, B those…

The proof, explained

The theorem states that the number of bichromatic edges directed from S to T equals the number directed from T to S. The proof first interchanges the order of summation on the left-hand side, reducing the goal to showing that corresponding summands are equal pointwise. It then uses the symmetry of graph adjacency and color inequality to show that the indicator conditions are logically equivalent, concluding by case analysis that both indicator terms always evaluate to the same value.

  1. The order of summation on the left-hand side is swapped to sum first over T and then over S.

    Using Finset.sum_comm, we exchange the inner and outer finite sums on the left-hand side, so that the outer index runs over T and the inner index runs over S.

    line 5

    uses Finset.sum_comm

      rw [Finset.sum_comm]
  2. It suffices to show that the individual summands agree for each pair (v, w) with v ∈ T and w ∈ S.

    Applying Finset.sum_congr to both the outer sum over T and the inner sum over S reduces equality of the double sums to showing that their terms are equal pointwise: namely, that the indicator for (w, v) equals the indicator for (v, w).

    line 6

    uses Finset.sum_congr

      refine Finset.sum_congr rfl fun v _ => Finset.sum_congr rfl fun w _ => ?_
  3. The bichromatic adjacency condition on (w, v) is logically equivalent to the condition on (v, w).

    Adjacency in a simple graph is symmetric (G.Adj w v ↔ G.Adj v w), and inequality of colors is symmetric (ρ v ≠ ρ w ↔ ρ w ≠ ρ v). Combining these symmetries establishes the equivalence e.

    lines 7–8

      have e : (G.Adj w v ∧ ρ v ≠ ρ w) ↔ (G.Adj v w ∧ ρ w ≠ ρ v) :=
        ⟨fun h => ⟨h.1.symm, h.2.symm⟩, fun h => ⟨h.1.symm, h.2.symm⟩⟩
  4. The two conditional expressions evaluate to the same value in all cases, completing the proof.

    We split into cases on whether the edge condition G.Adj v w ∧ ρ w ≠ ρ v holds. If it holds, the equivalent condition for (w, v) also holds, so both if-then-else expressions evaluate to 1 by if_pos. If it fails, neither condition holds by modus tollens (mt), so both expressions evaluate to 0 by if_neg.

    lines 9–11

    uses if_pos, if_neg, mt

      by_cases h : G.Adj v w ∧ ρ w ≠ ρ v
      · rw [if_pos h, if_pos (e.2 h)]
      · rw [if_neg h, if_neg (mt e.1 h)]
Finset.sum_comm
The order of summation in a double sum over finite sets can be swapped without changing the result: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
Finset.sum_congr
Two finite sums over the same set are equal if their summands agree on every element of the set.
if_pos
If a decidable condition c holds, then the expression (if c then t else e) evaluates to t.
if_neg
If a decidable condition c does not hold, then the expression (if c then t else e) evaluates to e.
mt
Modus tollens: from an implication a → b and the negation ¬b, one concludes ¬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

theorem maxcut_pair_sum_comm {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]    {k : ℕ} (ρ : V → Fin k) (S T : Finset V) :    ∑ v ∈ S, ∑ w ∈ T, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) =      ∑ v ∈ T, ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) := by  rw [Finset.sum_comm]  refine Finset.sum_congr rfl fun v _ => Finset.sum_congr rfl fun w _ => ?_  have e : (G.Adj w v ∧ ρ v ≠ ρ w) ↔ (G.Adj v w ∧ ρ w ≠ ρ v) :=    ⟨fun h => ⟨h.1.symm, h.2.symm⟩, fun h => ⟨h.1.symm, h.2.symm⟩⟩  by_cases h : G.Adj v w ∧ ρ w ≠ ρ v  · rw [if_pos h, if_pos (e.2 h)]  · rw [if_neg h, if_neg (mt e.1 h)]
See it in the graphDiscuss this resultChallenge it