graph_pebbling_step_sum
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.
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).
uses
G.ne_of_adjobtain ⟨u, v, huv, hu, hc'⟩ := h have hne : u ≠ v := G.ne_of_adj huv
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.
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]
∑ 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).
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.sum_ite_eq',Finset.mem_univ,if_truehave 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
∑ 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 ℕ.
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
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.
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