AFTD Auto-Formalizing Theoretical Domains

star_graph_one_stacking_number_eq_tree_estimate

theoremverifiedformalization

Conjecture 5.6 (OP-144) holds for the single-vertex tree K₁: stack(K₁) = estim(K₁) (both equal 2).

Statement

theorem star_graph_one_stacking_number_eq_tree_estimate :
    graph_stacking_number (SimpleGraph.starGraph (0 : Fin 1)) =
      simple_graph_tree_estimate (SimpleGraph.starGraph (0 : Fin 1))
Formalizes
arXiv:2610.09650 Thm 5.2
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • graph_stacking_numberThe stacking number stack(G): the least integer t ≥ 2 such that every configuration of size t on G is stackable (0 by convention if there…
  • simple_graph_tree_estimateThe tree estimate estim(T) = max{2, 1 + max_r (ρ_T(r) + leaf_T(r))}, where leaf_T(r) is the number of leaves of T other than r and ρ_T(r)…
  • 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…

Read back from the Lean

The stacking number of the star graph centered at $0 \in \text{Fin } 1$ (the graph on the single-element vertex set $\text{Fin } 1$ with no edges) equals the simple graph tree estimate for the same graph.

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

The theorem verifies Conjecture 5.6 for the single-vertex star graph K₁ by showing that its stacking number and its tree estimate both evaluate to 2. The stacking number is 2 because any configuration of 2 pebbles on the unique vertex is already concentrated on that vertex without any pebbling moves. The tree estimate is 2 because the unique vertex has degree 0 and there are no leaves, simplifying the estimate formula to max(2, 1 + 0) = 2.

  1. To show that the stacking number of K₁ is 2, it suffices to prove that 2 is the least element of the set of valid stackable pebble counts.

    Unfolding the definition of graph_stacking_number reveals it to be the infimum of all pebble counts t ≥ 2 such that every configuration with t pebbles can be stacked onto a single vertex. By IsLeast.csInf_eq, showing the infimum is 2 reduces to showing that 2 is the least element of this set, which splits into membership (2 is in the set) and lower bound (2 is at most any element in the set).

    lines 3–5

    uses IsLeast.csInf_eq

      unfold graph_stacking_number
      apply IsLeast.csInf_eq
      constructor
  2. Any configuration c of 2 pebbles on K₁ can be stacked onto vertex 0 in zero pebbling steps.

    The lower bound 2 ≤ 2 holds trivially by le_rfl. Given any configuration c summing to 2, unfolding graph_config_stackable requires finding a sequence of pebbling moves to a configuration concentrated on one vertex. We choose c itself reachable in zero steps via Relation.ReflTransGen.refl, with vertex 0 as the target, leaving the requirements that c(0) > 0 and all other vertices have 0 pebbles.

    lines 6–9

    uses le_rfl, Relation.ReflTransGen.refl

      · refine ⟨le_rfl, ?_⟩
        intro c hc
        unfold graph_config_stackable
        refine ⟨c, Relation.ReflTransGen.refl, 0, ?_, ?_⟩
  3. Vertex 0 has strictly positive pebbles: c(0) > 0.

    Because the universe of vertices Fin 1 is the singleton {0}, the sum of pebbles over all vertices equals c(0) by Finset.sum_singleton. Substituting this into the assumption that the total number of pebbles is 2 yields c(0) = 2, which implies c(0) > 0 by linear arithmetic (omega).

    lines 10–14

    uses Finset.sum_singleton

        · have h_sum : ∑ v : Fin 1, c v = c 0 := by
            have : (Finset.univ : Finset (Fin 1)) = {0} := rfl
            rw [← Finset.sum_singleton c 0, ← this]
          rw [h_sum] at hc
          omega
  4. Every vertex other than 0 has 0 pebbles, vacuously.

    For any vertex w in Fin 1, w must equal 0 by Subsingleton.elim. The assumption w ≠ 0 is therefore contradictory, so False.elim completes the branch vacuously.

    lines 15–17

    uses Subsingleton.elim, False.elim

        · intro w hw
          have : w = 0 := Subsingleton.elim w 0
          exact False.elim (hw this)
  5. 2 is a lower bound for all stackable pebble counts.

    Any element t in the set satisfies 2 ≤ t by the first conjunct of the definition of the set.

    lines 18–19

      · intro t ht
        exact ht.1
  6. The tree estimate formula on K₁ simplifies to evaluating the expression at the unique root r = 0.

    Unfolding simple_graph_tree_estimate gives max(2, 1 + sup_r (...)). Since Fin 1 consists only of the vertex 0, the supremum over the singleton {0} simplifies by Finset.sup_singleton to the value at r = 0.

    lines 23–26

    uses Finset.sup_singleton

      unfold simple_graph_tree_estimate
      have h_univ : (Finset.univ : Finset (Fin 1)) = {0} := rfl
      rw [h_univ]
      simp only [Finset.sup_singleton]
  7. There are no non-root leaf vertices in K₁, so the leaf-count term vanishes.

    The set of vertices in {0} distinct from 0 with degree 1 is empty (verified by decide). Its cardinality is 0 by Finset.card_empty, and adding 0 is an identity by add_zero.

    lines 27–30

    uses Finset.card_empty, add_zero

      have h_leaf : {v ∈ ({0} : Finset (Fin 1)) | v ≠ (0 : Fin 1) ∧ (SimpleGraph.starGraph (0 : Fin 1)).degree v = 1} = ∅ := by
        decide
      rw [h_leaf]
      simp only [Finset.card_empty, add_zero]
  8. The degree-weighted sum over high-degree vertices and the root is 0.

    Using Finset.sum_eq_zero, every term in the sum is zero because any vertex v in Fin 1 equals 0 by Subsingleton.elim, and the degree of vertex 0 in K₁ is 0 (computed by decide). Hence the product degree(v) * 2^(dist(0, v)) equals 0 by zero_mul.

    lines 31–39

    uses Finset.sum_eq_zero, Subsingleton.elim, zero_mul

      have h_sum : (∑ v ∈ {0} with v = (0 : Fin 1) ∨ 1 < (SimpleGraph.starGraph (0 : Fin 1)).degree v,
          (SimpleGraph.starGraph (0 : Fin 1)).degree v * 2 ^ (SimpleGraph.starGraph (0 : Fin 1)).dist 0 v) = 0 := by
        apply Finset.sum_eq_zero
        intro v _
        have hv : (SimpleGraph.starGraph (0 : Fin 1)).degree v = 0 := by
          have : v = 0 := Subsingleton.elim v 0
          subst this
          decide
        rw [hv, zero_mul]
  9. The tree estimate for K₁ is 2.

    Substituting the zero sum simplifies the tree estimate expression to max(2, 1 + 0) = max(2, 1) = 2, which holds by reflexivity (rfl).

    lines 40–41

      rw [h_sum]
      rfl
  10. The stacking number of K₁ equals its tree estimate, both being 2.

    Rewriting both sides with star_graph_one_stacking_number_eq_tree_estimate_stacking_number and star_graph_one_stacking_number_eq_tree_estimate_tree_estimate evaluates both the stacking number and the tree estimate to 2, establishing the equality.

    lines 47–48

    uses star_graph_one_stacking_number_eq_tree_estimate_stacking_number, star_graph_one_stacking_number_eq_tree_estimate_tree_estimate

      rw [star_graph_one_stacking_number_eq_tree_estimate_stacking_number,
          star_graph_one_stacking_number_eq_tree_estimate_tree_estimate]
IsLeast.csInf_eq
If a is the least element of a set s, then the infimum of s equals a.
le_rfl
The preorder inequality is reflexive: a ≤ a for any a.
Relation.ReflTransGen.refl
The reflexive-transitive closure of a relation is reflexive: every element can reach itself in zero steps.
Finset.sum_singleton
The sum of a function over a singleton set {a} is the value of the function at a.
Subsingleton.elim
In a subsingleton type, any two elements are equal.
False.elim
From a contradiction (False), any conclusion can be deduced.
Finset.sup_singleton
The supremum of a function over a singleton set {b} is the value of the function at b.
Finset.card_empty
The cardinality of the empty set is 0.
add_zero
Adding zero to an element gives the element itself: a + 0 = a.
Finset.sum_eq_zero
If a function is zero at every element of a finite set s, its sum over s is zero.
zero_mul
Zero multiplied by any element is zero: 0 * a = 0.
star_graph_one_stacking_number_eq_tree_estimate_stacking_number
The stacking number of the single-vertex star graph K₁ is 2.
star_graph_one_stacking_number_eq_tree_estimate_tree_estimate
The tree estimate of the single-vertex star graph K₁ is 2.

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 star_graph_one_stacking_number_eq_tree_estimate_stacking_number :    graph_stacking_number (SimpleGraph.starGraph (0 : Fin 1)) = 2 := by  unfold graph_stacking_number  apply IsLeast.csInf_eq  constructor  · refine ⟨le_rfl, ?_⟩    intro c hc    unfold graph_config_stackable    refine ⟨c, Relation.ReflTransGen.refl, 0, ?_, ?_⟩    · have h_sum : ∑ v : Fin 1, c v = c 0 := by        have : (Finset.univ : Finset (Fin 1)) = {0} := rfl        rw [← Finset.sum_singleton c 0, ← this]      rw [h_sum] at hc      omega    · intro w hw      have : w = 0 := Subsingleton.elim w 0      exact False.elim (hw this)  · intro t ht    exact ht.1theorem star_graph_one_stacking_number_eq_tree_estimate_tree_estimate :    simple_graph_tree_estimate (SimpleGraph.starGraph (0 : Fin 1)) = 2 := by  unfold simple_graph_tree_estimate  have h_univ : (Finset.univ : Finset (Fin 1)) = {0} := rfl  rw [h_univ]  simp only [Finset.sup_singleton]  have h_leaf : {v ∈ ({0} : Finset (Fin 1)) | v ≠ (0 : Fin 1) ∧ (SimpleGraph.starGraph (0 : Fin 1)).degree v = 1} = ∅ := by    decide  rw [h_leaf]  simp only [Finset.card_empty, add_zero]  have h_sum : (∑ v ∈ {0} with v = (0 : Fin 1) ∨ 1 < (SimpleGraph.starGraph (0 : Fin 1)).degree v,      (SimpleGraph.starGraph (0 : Fin 1)).degree v * 2 ^ (SimpleGraph.starGraph (0 : Fin 1)).dist 0 v) = 0 := by    apply Finset.sum_eq_zero    intro v _    have hv : (SimpleGraph.starGraph (0 : Fin 1)).degree v = 0 := by      have : v = 0 := Subsingleton.elim v 0      subst this      decide    rw [hv, zero_mul]  rw [h_sum]  rfl/-- OP-144 holds for the single-vertex tree K₁: stack(K₁) = estim(K₁) = 2. -/theorem star_graph_one_stacking_number_eq_tree_estimate :    graph_stacking_number (SimpleGraph.starGraph (0 : Fin 1)) =      simple_graph_tree_estimate (SimpleGraph.starGraph (0 : Fin 1)) := by  rw [star_graph_one_stacking_number_eq_tree_estimate_stacking_number,      star_graph_one_stacking_number_eq_tree_estimate_tree_estimate]
See it in the graphDiscuss this resultChallenge it