AFTD Auto-Formalizing Theoretical Domains

not_graph_config_stackable_zero

theoremverified

The empty configuration is not stackable: no step applies and its support is empty.

Statement

theorem not_graph_config_stackable_zero {V : Type*} [DecidableEq V] (G : SimpleGraph V) :
    ¬ graph_config_stackable G 0
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 proof proceeds by contradiction. If the zero configuration were stackable, pebbling steps would reach a configuration with at least one pebble at some vertex. However, an induction on the sequence of pebbling moves shows that any configuration reachable from the zero configuration is still the zero configuration, because every pebbling step requires at least two pebbles on some vertex. This contradicts the existence of a vertex with a positive pebble count.

  1. Assume for contradiction that the zero configuration is stackable, yielding a reachable configuration $c'$ with at least one pebble on some vertex $v$.

    We assume for contradiction that the zero configuration is stackable. By definition of `graph_config_stackable`, this yields a configuration $c'$ reachable from the initial configuration $0$ by a sequence of pebbling steps (hypothesis `hr`), together with a vertex $v$ containing at least one pebble ($0 < c'(v)$, hypothesis `hv`).

    line 3

      rintro ⟨c', hr, v, hv, -⟩
  2. Any configuration $c'$ reachable from the zero configuration is identically zero ($c' = 0$).

    We prove this auxiliary claim by induction on the sequence of pebbling steps (`hr`). In the base case of zero steps (`refl`), the configuration is trivially zero ($0 = 0$). In the inductive step (`tail`), the preceding configuration is zero by the induction hypothesis (`ih`). A pebbling step (`hstep`) transitioning from the zero configuration to a new configuration would require some vertex $u$ to have at least two pebbles ($2 \le 0(u)$). Because $0(u) = 0$, this yields $2 \le 0$, which is impossible, so no pebbling step can ever be taken from the zero configuration.

    lines 4–11

      have : c' = 0 := by
        clear hv
        induction hr with
        | refl => rfl
        | tail _ hstep ih =>
          subst ih
          obtain ⟨u, w, -, hu, -⟩ := hstep
          simp at hu
  3. This contradicts the existence of a vertex with a strictly positive pebble count.

    Substituting $c' = 0$ into the hypothesis $0 < c'(v)$ gives $0 < 0$, which simplifies to False and completes the proof.

    lines 12–13

      subst this
      simp at hv

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 not_graph_config_stackable_zero {V : Type*} [DecidableEq V] (G : SimpleGraph V) :    ¬ graph_config_stackable G 0 := by  rintro ⟨c', hr, v, hv, -⟩  have : c' = 0 := by    clear hv    induction hr with    | refl => rfl    | tail _ hstep ih =>      subst ih      obtain ⟨u, w, -, hu, -⟩ := hstep      simp at hu  subst this  simp at hv
See it in the graphDiscuss this resultChallenge it