AFTD Auto-Formalizing Theoretical Domains

graph_pebbling_step_sum

theoremverified

A pebbling step lowers the size ‖c‖ = Σ_v c(v) by exactly one.

Statement

theorem graph_pebbling_step_sum {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    {c c' : V → ℕ} (h : graph_pebbling_step G c c') : ∑ v, c' v + 1 = ∑ v, c v
Source
Sanity lemma for graph_pebbling_step (arXiv:2610.09650 (The Almost Stacked Hypothesis: A Conjectural Analogue of Sjöstrand's Cover Pebbling Theorem), Sec. 2).
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_pebbling_stepA pebbling step on a graph G turns the configuration c : V → ℕ into c' when some edge uv has c(u) ≥ 2 and c' is c with two pebbles removed…

The proof, explained

A pebbling step removes two pebbles from a vertex u and adds one pebble to an adjacent vertex v. The proof establishes a pointwise identity relating the pebble counts before and after the step at every vertex, using indicator terms at u and v. Summing this relation over all vertices and collapsing the indicator sums shows that the total number of pebbles in c' plus 1 equals the total in c.

  1. There exist distinct adjacent vertices u and v such that c(u) ≥ 2 and c' is obtained by removing 2 pebbles from u and adding 1 pebble to v.

    Unfolding the definition of a pebbling step yields vertices u and v with an edge between them, at least 2 pebbles at u, and the updated configuration c' given by subtracting 2 at u and adding 1 at v. Because G is a simple graph, adjacent vertices are distinct (u ≠ v).

    lines 3–4

    uses G.ne_of_adj

      obtain ⟨u, v, huv, hu, hc'⟩ := h
      have hne : u ≠ v := G.ne_of_adj huv
  2. For every vertex x, c'(x) + (if x = u then 2 else 0) = c(x) + (if x = v then 1 else 0).

    We rewrite c' in terms of the function updates and distinguish three cases for an arbitrary vertex x: if x = v, then x ≠ u, so c'(v) = c(v) + 1 and both sides evaluate to c(v) + 1; if x = u, then x ≠ v, so c'(u) = c(u) - 2 and the equality reduces to (c(u) - 2) + 2 = c(u), which holds because c(u) ≥ 2; finally, if x ∉ {u, v}, neither update applies, so c'(x) = c(x) and both indicator terms are 0.

    lines 5–15

      have key : ∀ x, c' x + (if x = u then 2 else 0) = c x + (if x = v then 1 else 0) := by
        intro x
        rw [hc']
        by_cases hxv : x = v
        · subst hxv
          simp [hne.symm]
        · by_cases hxu : x = u
          · subst hxu
            simp [hxv]
            omega
          · simp [hxu, hxv]
  3. ∑ x, c'(x) + 2 = ∑ x, c(x) + 1

    Summing the pointwise identity over all vertices and distributing the sum over addition yields ∑ x, c'(x) plus the sum of the indicator for u, equal to ∑ x, c(x) plus the sum of the indicator for v. Since both u and v belong to the universe of vertices, each indicator sum collapses to its single nonzero value (2 and 1 respectively).

    lines 16–19

    uses Finset.sum_congr, Finset.sum_add_distrib, Finset.sum_ite_eq', Finset.mem_univ, if_true

      have hs := Finset.sum_congr rfl (fun x (_ : x ∈ (Finset.univ : Finset V)) => key x)
      rw [Finset.sum_add_distrib, Finset.sum_add_distrib, Finset.sum_ite_eq', Finset.sum_ite_eq']
        at hs
      simp only [Finset.mem_univ, if_true] at hs
  4. ∑ v, c'(v) + 1 = ∑ v, c(v)

    Subtracting 1 from both sides of ∑ x, c'(x) + 2 = ∑ x, c(x) + 1 yields the desired equality by linear arithmetic over ℕ.

    line 20

      omega
G.ne_of_adj
adjacent vertices in a simple graph are distinct
Finset.sum_congr
if two finite sets are equal and their summands agree on every element, then their sums are equal
Finset.sum_add_distrib
the sum of a sum of functions equals the sum of the individual sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x
Finset.sum_ite_eq'
summing an indicator expression (if x = a then b x else 0) over a finite set s evaluates to b a if a ∈ s and 0 otherwise
Finset.mem_univ
every element of a finite type belongs to its universal finset Finset.univ
if_true
the conditional (if True then t else e) simplifies to t

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 graph_pebbling_step_sum {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    {c c' : V → ℕ} (h : graph_pebbling_step G c c') : ∑ v, c' v + 1 = ∑ v, c v := by  obtain ⟨u, v, huv, hu, hc'⟩ := h  have hne : u ≠ v := G.ne_of_adj huv  have key : ∀ x, c' x + (if x = u then 2 else 0) = c x + (if x = v then 1 else 0) := by    intro x    rw [hc']    by_cases hxv : x = v    · subst hxv      simp [hne.symm]    · by_cases hxu : x = u      · subst hxu        simp [hxv]        omega      · simp [hxu, hxv]  have hs := Finset.sum_congr rfl (fun x (_ : x ∈ (Finset.univ : Finset V)) => key x)  rw [Finset.sum_add_distrib, Finset.sum_add_distrib, Finset.sum_ite_eq', Finset.sum_ite_eq']    at hs  simp only [Finset.mem_univ, if_true] at hs  omega
See it in the graphDiscuss this resultChallenge it