not_graph_config_stackable_zero
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.
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`).
rintro ⟨c', hr, v, hv, -⟩
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.
have : c' = 0 := by clear hv induction hr with | refl => rfl | tail _ hstep ih => subst ih obtain ⟨u, w, -, hu, -⟩ := hstep simp at hu
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.
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
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 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