AFTD Auto-Formalizing Theoretical Domains

graph_config_is_almost_stacked_single

theoremverified

A configuration with all pebbles on a single vertex is almost stacked.

Statement

theorem graph_config_is_almost_stacked_single {V : Type*} [DecidableEq V] (v : V) (m : ℕ) :
    graph_config_is_almost_stacked (Pi.single v m)
Source
arXiv:2610.09650 Def 3.1
Verified
25 Oct 2026
Axioms
propext
Built on 1
  • graph_config_is_almost_stackedA configuration c on a graph is almost stacked if at most one vertex carries more than one pebble, meaning there exists a vertex r such…

Read back from the Lean

For any type V with decidable equality, any element v : V, and any natural number m : ℕ, the function Pi.single v m : V → ℕ satisfies graph_config_is_almost_stacked, meaning there exists some r : V such that every vertex other than r is assigned a value of at most 1.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

A configuration is almost stacked if there exists a vertex such that every other vertex has at most one pebble. For a configuration where all pebbles sit on a single vertex v, we choose v as the witness vertex. Every other vertex has zero pebbles, which is trivially at most one.

  1. It suffices to show that any vertex w ≠ v has at most one pebble in the configuration.

    By definition, a configuration is almost stacked if there is a vertex r such that every other vertex has at most one pebble. We choose r = v as the witness and let w be an arbitrary vertex distinct from v.

    line 4

      refine ⟨v, fun w hw => ?_⟩
  2. The configuration assigns 0 pebbles to w, and 0 ≤ 1.

    Since w ≠ v, the function Pi.single v m evaluates to 0 at w by Pi.single_eq_of_ne. The remaining goal 0 ≤ 1 is established by Nat.zero_le.

    lines 5–6

    uses Pi.single_eq_of_ne, Nat.zero_le

      rw [Pi.single_eq_of_ne hw]
      exact Nat.zero_le 1
Pi.single_eq_of_ne
A function supported on a single element v evaluates to 0 at any input distinct from v.
Nat.zero_le
Zero is less than or equal to any natural number.

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

/-- A configuration with all pebbles on a single vertex is almost stacked. -/theorem graph_config_is_almost_stacked_single {V : Type*} [DecidableEq V] (v : V) (m : ℕ) :    graph_config_is_almost_stacked (Pi.single v m) := by  refine ⟨v, fun w hw => ?_⟩  rw [Pi.single_eq_of_ne hw]  exact Nat.zero_le 1
See it in the graphDiscuss this resultChallenge it