AFTD Auto-Formalizing Theoretical Domains

graph_config_stackable_single

theoremverified

A configuration with m ≥ 1 pebbles all on one vertex is stackable (it is already stacked).

Statement

theorem graph_config_stackable_single {V : Type*} [DecidableEq V] (G : SimpleGraph V) (v : V)
    (m : ℕ) (hm : 0 < m) : graph_config_stackable G (Pi.single v m)
Source
Sanity lemma for graph_config_stackable (arXiv:2610.09650 (The Almost Stacked Hypothesis: A Conjectural Analogue of Sjöstrand's Cover Pebbling Theorem), Definition 2.1).
Verified
12 Oct 2026
Axioms
propext
Built on 2
  • graph_config_stackableA configuration c on G is stackable if a sequence of pebbling steps (possibly empty) turns it into a stacked configuration, one whose…
  • 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

The initial configuration already has all m pebbles concentrated on the single vertex v and none elsewhere. By reflexivity of the reflexive-transitive reachability relation, zero pebbling moves are needed. The stackability condition is therefore satisfied directly by taking the configuration itself as the witness.

  1. The configuration is stackable by taking zero pebbling moves and choosing v as the target vertex.

    To show that the configuration is stackable, we exhibit the initial configuration itself as the witness c', which is reachable in zero pebbling steps by the reflexivity of the reflexive-transitive closure (Relation.ReflTransGen.refl). Choosing v as the target vertex, the pebble count at v is m > 0 by assumption hm, and for any other vertex w ≠ v, the pebble count is 0 by the definition of Pi.single.

    line 3

    uses Relation.ReflTransGen.refl

      ⟨_, Relation.ReflTransGen.refl, v, by simpa using hm, fun w hw => by simp [hw]⟩
Relation.ReflTransGen.refl
Every element is reachable from itself in zero steps under the reflexive-transitive closure of any binary relation.

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_config_stackable_single {V : Type*} [DecidableEq V] (G : SimpleGraph V) (v : V)    (m : ℕ) (hm : 0 < m) : graph_config_stackable G (Pi.single v m) :=  ⟨_, Relation.ReflTransGen.refl, v, by simpa using hm, fun w hw => by simp [hw]⟩
See it in the graphDiscuss this resultChallenge it