star_graph_one_stacking_number_eq_tree_estimate
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.
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).
uses
IsLeast.csInf_equnfold graph_stacking_number apply IsLeast.csInf_eq constructor
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.
uses
le_rfl,Relation.ReflTransGen.refl· refine ⟨le_rfl, ?_⟩ intro c hc unfold graph_config_stackable refine ⟨c, Relation.ReflTransGen.refl, 0, ?_, ?_⟩
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).
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
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.
uses
Subsingleton.elim,False.elim· intro w hw have : w = 0 := Subsingleton.elim w 0 exact False.elim (hw this)
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.
· intro t ht exact ht.1
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.
uses
Finset.sup_singletonunfold simple_graph_tree_estimate have h_univ : (Finset.univ : Finset (Fin 1)) = {0} := rfl rw [h_univ] simp only [Finset.sup_singleton]
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.
uses
Finset.card_empty,add_zerohave 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]
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.
uses
Finset.sum_eq_zero,Subsingleton.elim,zero_mulhave 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]
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).
rw [h_sum] rfl
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.
uses
star_graph_one_stacking_number_eq_tree_estimate_stacking_number,star_graph_one_stacking_number_eq_tree_estimate_tree_estimaterw [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
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 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]