path_graph_two_stacking_number_eq_tree_estimate
Conjecture 5.6 (OP-144) holds for the path on two vertices: stack(P₂) = estim(P₂) (both equal 3).
Statement
theorem path_graph_two_stacking_number_eq_tree_estimate
[DecidableRel (SimpleGraph.pathGraph 2).Adj] :
graph_stacking_number (SimpleGraph.pathGraph 2) =
simple_graph_tree_estimate (SimpleGraph.pathGraph 2)- Related work
- arXiv:2610.09650 (The Almost Stacked Hypothesis: A Conjectural Analogue of Sjöstrand's Cover Pebbling Theorem), Conjecture 5.6, smallest nontrivial tree; the paper's Theorem 4.4 (from earlier work) gives stack(P_n) = 2^n − 1.
- Verified
- 12 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_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…
- 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…
The proof, explained
The proof verifies Conjecture 5.6 for the two-vertex path graph P₂ by calculating both its tree estimate and its stacking number and showing they are both equal to 3. The tree estimate is evaluated directly: both vertices have degree 1, so the formula simplifies to max(2, 1 + 2) = 3. For the stacking number, the proof checks all four configurations of 3 pebbles and shows each reaches a single stacked vertex in at most one pebbling move, while the 2-pebble configuration (1, 1) cannot make any moves and is not stacked, confirming that 3 is the minimal required pebble count.
The neighbor finset of any vertex v in P₂ consists of the other vertex, namely Finset.univ.erase v.
By extensionality, a vertex w is a neighbor of v if and only if v and w are adjacent in P₂. On the two-element type Fin 2, checking all four pairs (v, w) shows that adjacency holds exactly when w ≠ v.
uses
SimpleGraph.mem_neighborFinset,SimpleGraph.pathGraph_adj,Finset.mem_erase,Finset.mem_univ,and_truehave : (SimpleGraph.pathGraph 2).neighborFinset v = Finset.univ.erase v := by ext w simp only [SimpleGraph.mem_neighborFinset, SimpleGraph.pathGraph_adj, Finset.mem_erase, Finset.mem_univ, and_true] fin_cases v <;> fin_cases w <;> decide
Every vertex in P₂ has degree 1.
The degree of v is defined as the cardinality of its neighbor finset. Since the neighbor finset is Finset.univ.erase v, its cardinality is 2 - 1 = 1.
uses
SimpleGraph.degreerw [SimpleGraph.degree, this] simp
Unfold the tree estimate definition and note that every vertex in P₂ has degree 1.
Unfolding simple_graph_tree_estimate expresses the estimate as max 2 (1 + sup_r ...). We record that every vertex has degree 1 from the previous lemma.
uses
path_graph_two_stacking_number_eq_tree_estimate_degreeunfold simple_graph_tree_estimate have h_deg : ∀ v : Fin 2, (SimpleGraph.pathGraph 2).degree v = 1 := path_graph_two_stacking_number_eq_tree_estimate_degree
For any root r ∈ Fin 2, the rooted tree estimate expression evaluates to 2.
Because every vertex has degree 1, no vertex has degree > 1, so the set of vertices satisfying v = r ∨ 1 < deg(v) is just {r}, which contributes deg(r) * 2^(dist r r) = 1 * 2^0 = 1. The set of vertices with v ≠ r and deg(v) = 1 is the single remaining vertex, contributing cardinality 1. The sum is 1 + 1 = 2.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_singleton,Finset.mem_erase,and_true,SimpleGraph.dist_selfhave h_r : ∀ r : Fin 2, (∑ v ∈ Finset.univ.filter (fun v => v = r ∨ 1 < (SimpleGraph.pathGraph 2).degree v), (SimpleGraph.pathGraph 2).degree v * 2 ^ (SimpleGraph.pathGraph 2).dist r v) + (Finset.univ.filter (fun v => v ≠ r ∧ (SimpleGraph.pathGraph 2).degree v = 1)).card = 2 := by intro r have hfilt1 : Finset.univ.filter (fun v => v = r ∨ 1 < (SimpleGraph.pathGraph 2).degree v) = {r} := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton, h_deg] omega have hfilt2 : Finset.univ.filter (fun v => v ≠ r ∧ (SimpleGraph.pathGraph 2).degree v = 1) = Finset.univ.erase r := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true, h_deg] rw [hfilt1, hfilt2] simp [h_deg, SimpleGraph.dist_self]
The supremum over all roots r ∈ Fin 2 of the rooted expression is 2.
By antisymmetry: the supremum is at most 2 because every root evaluates to 2, and it is at least 2 by evaluating at root 0.
uses
le_antisymm,Finset.sup_le,le_trans,Finset.le_sup,Finset.mem_univhave h_sup : Finset.univ.sup (fun r : Fin 2 => (∑ v ∈ Finset.univ.filter (fun v => v = r ∨ 1 < (SimpleGraph.pathGraph 2).degree v), (SimpleGraph.pathGraph 2).degree v * 2 ^ (SimpleGraph.pathGraph 2).dist r v) + (Finset.univ.filter (fun v => v ≠ r ∧ (SimpleGraph.pathGraph 2).degree v = 1)).card) = 2 := by apply le_antisymm · refine Finset.sup_le ?_ intro r _ rw [h_r r] · refine le_trans ?_ (Finset.le_sup (f := fun r => _) (Finset.mem_univ 0)) rw [h_r 0]
The tree estimate of P₂ is 3.
Substituting the supremum value 2 into the tree estimate formula gives max 2 (1 + 2) = 3 by definition.
rw [h_sup] rfl
Any configuration c on Fin 2 with sum 3 satisfies (c(0), c(1)) ∈ {(3, 0), (2, 1), (1, 2), (0, 3)}.
Rewriting the total sum over Fin 2 as c(0) + c(1) = 3 restricts the non-negative integer values of c(0) and c(1) to these four cases.
uses
Fin.sum_univ_tworw [Fin.sum_univ_two] at hc have hcases : (c 0 = 3 ∧ c 1 = 0) ∨ (c 0 = 2 ∧ c 1 = 1) ∨ (c 0 = 1 ∧ c 1 = 2) ∨ (c 0 = 0 ∧ c 1 = 3) := by omega rcases hcases with ⟨h0, h1⟩ | ⟨h0, h1⟩ | ⟨h0, h1⟩ | ⟨h0, h1⟩
The configuration (3, 0) is stackable on P₂.
The configuration is already stacked on vertex 0 with 0 pebbling steps (reflexivity), as vertex 0 has 3 pebbles and vertex 1 has 0.
uses
Relation.ReflTransGen.refl· refine ⟨c, Relation.ReflTransGen.refl, 0, by omega, ?_⟩ intro w hw; fin_cases w; contradiction; exact h1
The configuration (2, 1) is stackable on P₂.
Since vertex 0 has 2 pebbles and is adjacent to vertex 1, a pebbling step removes 2 pebbles from vertex 0 and adds 1 to vertex 1, producing configuration (0, 2). This configuration is stacked on vertex 1, which has 2 pebbles while vertex 0 has 0.
uses
SimpleGraph.pathGraph_adj,Relation.ReflTransGen.single,Function.update_of_ne,Function.update_self· let c' := Function.update (Function.update c 0 (c 0 - 2)) 1 (c 1 + 1) have hstep : graph_pebbling_step (SimpleGraph.pathGraph 2) c c' := by refine ⟨0, 1, ?_, ?_, rfl⟩ · rw [SimpleGraph.pathGraph_adj]; decide · omega refine ⟨c', Relation.ReflTransGen.single hstep, 1, by dsimp [c']; simp, ?_⟩ intro w hw; fin_cases w · dsimp [c']; simp [Function.update_of_ne, Function.update_self]; omega · contradiction
The configuration (1, 2) is stackable on P₂.
Symmetrically, vertex 1 has 2 pebbles and is adjacent to vertex 0, so one pebbling step moves 2 pebbles from vertex 1 to vertex 0, reaching configuration (2, 0). This configuration is stacked on vertex 0.
uses
SimpleGraph.pathGraph_adj,Relation.ReflTransGen.single,Function.update_of_ne,Function.update_self· let c' := Function.update (Function.update c 1 (c 1 - 2)) 0 (c 0 + 1) have hstep : graph_pebbling_step (SimpleGraph.pathGraph 2) c c' := by refine ⟨1, 0, ?_, ?_, rfl⟩ · rw [SimpleGraph.pathGraph_adj]; decide · omega refine ⟨c', Relation.ReflTransGen.single hstep, 0, by dsimp [c']; simp, ?_⟩ intro w hw; fin_cases w · contradiction · dsimp [c']; simp [Function.update_of_ne, Function.update_self]; omega
The configuration (0, 3) is stackable on P₂.
The configuration is already stacked on vertex 1 with 0 pebbling steps, as vertex 1 has 3 pebbles and vertex 0 has 0.
uses
Relation.ReflTransGen.refl· refine ⟨c, Relation.ReflTransGen.refl, 1, by omega, ?_⟩ intro w hw; fin_cases w; exact h0; contradiction
If no transition step can be made from state a, then any state reachable from a in the reflexive-transitive closure is a itself.
We proceed by head induction on reachability. The base case (zero steps) gives b = a. In the inductive step, taking a first step from a contradicts the hypothesis that no step is possible from a.
uses
Relation.ReflTransGen.head_induction_oninduction hr using Relation.ReflTransGen.head_induction_on with | refl => rfl | head hstep _ _ => exact (h _ hstep).elim
No pebbling step is possible from the configuration (1, 1).
A pebbling step requires at least 2 pebbles at some vertex u, but under (1, 1) each vertex has only 1 pebble, which is strictly less than 2.
intro ⟨c', hreach, v, _, hzero⟩ have hno_step : ∀ d, ¬ graph_pebbling_step (SimpleGraph.pathGraph 2) (fun _ => 1) d := by intro d ⟨u, _, _, h2, _⟩ dsimp at h2 omega
Any configuration c' reachable from (1, 1) must equal (1, 1).
Since no pebbling step is possible from (1, 1), the previous general reachability lemma implies that c' = (1, 1).
uses
path_graph_two_stacking_number_eq_tree_estimate_reflTransGen_eq_of_no_stephave hc' : c' = (fun _ => 1) := path_graph_two_stacking_number_eq_tree_estimate_reflTransGen_eq_of_no_step hno_step hreach subst hc'
The configuration (1, 1) is not stackable on P₂.
If (1, 1) were stacked on some vertex v ∈ Fin 2, then the other vertex w ≠ v would have 0 pebbles, but both vertices have 1 pebble in (1, 1), a contradiction.
fin_cases v · have := hzero 1 (by decide) contradiction · have := hzero 0 (by decide) contradiction
3 belongs to the set S of valid stacking bounds.
Unfolding the definition of graph_stacking_number, S consists of integers t ≥ 2 such that every configuration with sum t is stackable. Since 2 ≤ 3 and all configurations of sum 3 are stackable by path_graph_two_stacking_number_eq_tree_estimate_three_stackable, 3 ∈ S.
uses
path_graph_two_stacking_number_eq_tree_estimate_three_stackableunfold graph_stacking_number set S := {t : ℕ | 2 ≤ t ∧ ∀ c : Fin 2 → ℕ, ∑ v, c v = t → graph_config_stackable (SimpleGraph.pathGraph 2) c} have h3 : 3 ∈ S := by refine ⟨by decide, ?_⟩ intro c hc exact path_graph_two_stacking_number_eq_tree_estimate_three_stackable c hc
Every t ∈ S satisfies 3 ≤ t.
Suppose for contradiction that some t ∈ S has t < 3. Since t ≥ 2, we must have t = 2. Then every configuration of sum 2 would be stackable, including (1, 1). But (1, 1) is not stackable by path_graph_two_stacking_number_eq_tree_estimate_not_stackable_one_one, a contradiction.
uses
path_graph_two_stacking_number_eq_tree_estimate_not_stackable_one_onehave hmin : ∀ t ∈ S, 3 ≤ t := by intro t ⟨ht2, ht_all⟩ by_contra! hlt have ht : t = 2 := by omega have hsum : ∑ v : Fin 2, (fun _ : Fin 2 => 1 : Fin 2 → ℕ) v = 2 := by decide have hstack : graph_config_stackable (SimpleGraph.pathGraph 2) (fun _ => 1) := by subst ht exact ht_all (fun _ => 1) hsum exact path_graph_two_stacking_number_eq_tree_estimate_not_stackable_one_one hstack
The stacking number of P₂ is 3.
By antisymmetry, the infimum of S is at most 3 because 3 ∈ S, and at least 3 because 3 is a lower bound for S. Thus sInf S = 3.
uses
le_antisymm,Nat.sInf_le,le_csInfapply le_antisymm · exact Nat.sInf_le h3 · exact le_csInf ⟨3, h3⟩ hmin
The stacking number of P₂ equals the tree estimate of P₂.
Rewriting both sides using the established lemmas that the stacking number is 3 and the tree estimate is 3 completes the proof.
uses
path_graph_two_stacking_number_eq_tree_estimate_stacking_number,path_graph_two_stacking_number_eq_tree_estimate_tree_estimaterw [path_graph_two_stacking_number_eq_tree_estimate_stacking_number, path_graph_two_stacking_number_eq_tree_estimate_tree_estimate]
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
SimpleGraph.pathGraph_adj- Two vertices in the path graph Pₙ are adjacent if and only if their indices differ by 1.
Finset.mem_erase- An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
and_true- Conjunction of a proposition with True is equivalent to the proposition.
SimpleGraph.degree- The degree of a vertex is the cardinality of its neighbor finset.
path_graph_two_stacking_number_eq_tree_estimate_degree- Every vertex in the path graph P₂ has degree 1.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the set and satisfies the predicate.
true_and- Conjunction of True with a proposition is equivalent to the proposition.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
SimpleGraph.dist_self- The graph distance from any vertex to itself is 0.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
Finset.sup_le- The supremum of a function over a finite set is at most a if the function is at most a everywhere on that set.
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
Finset.le_sup- The value of a function at any element of a finite set is bounded above by the supremum over that set.
Fin.sum_univ_two- The sum of a function over Fin 2 equals f(0) + f(1).
Relation.ReflTransGen.refl- The reflexive-transitive closure of any relation is reflexive.
Relation.ReflTransGen.single- A single transition step implies reachability in the reflexive-transitive closure.
Function.update_of_ne- Updating a function at a' leaves its value at any distinct point a unchanged.
Function.update_self- Updating a function at a with value v evaluates to v at a.
Relation.ReflTransGen.head_induction_on- Induction principle for reflexive-transitive closures, decomposing into the reflexive base case and a single head step followed by reachability.
path_graph_two_stacking_number_eq_tree_estimate_reflTransGen_eq_of_no_step- If no transition step is possible from state a, any state reachable from a in the reflexive-transitive closure is a itself.
path_graph_two_stacking_number_eq_tree_estimate_three_stackable- Any pebble configuration on P₂ with 3 pebbles total is stackable.
path_graph_two_stacking_number_eq_tree_estimate_not_stackable_one_one- The pebble configuration (1, 1) on P₂ is not stackable.
Nat.sInf_le- The infimum of a set of natural numbers is at most any element of the set.
le_csInf- If a is a lower bound for a nonempty set, then a is at most the infimum of the set.
path_graph_two_stacking_number_eq_tree_estimate_stacking_number- The stacking number of P₂ is equal to 3.
path_graph_two_stacking_number_eq_tree_estimate_tree_estimate- The tree estimate of P₂ is equal to 3.
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.
lemma path_graph_two_stacking_number_eq_tree_estimate_degree [DecidableRel (SimpleGraph.pathGraph 2).Adj] (v : Fin 2) : (SimpleGraph.pathGraph 2).degree v = 1 := by have : (SimpleGraph.pathGraph 2).neighborFinset v = Finset.univ.erase v := by ext w simp only [SimpleGraph.mem_neighborFinset, SimpleGraph.pathGraph_adj, Finset.mem_erase, Finset.mem_univ, and_true] fin_cases v <;> fin_cases w <;> decide rw [SimpleGraph.degree, this] simplemma path_graph_two_stacking_number_eq_tree_estimate_tree_estimate [DecidableRel (SimpleGraph.pathGraph 2).Adj] : simple_graph_tree_estimate (SimpleGraph.pathGraph 2) = 3 := by unfold simple_graph_tree_estimate have h_deg : ∀ v : Fin 2, (SimpleGraph.pathGraph 2).degree v = 1 := path_graph_two_stacking_number_eq_tree_estimate_degree have h_r : ∀ r : Fin 2, (∑ v ∈ Finset.univ.filter (fun v => v = r ∨ 1 < (SimpleGraph.pathGraph 2).degree v), (SimpleGraph.pathGraph 2).degree v * 2 ^ (SimpleGraph.pathGraph 2).dist r v) + (Finset.univ.filter (fun v => v ≠ r ∧ (SimpleGraph.pathGraph 2).degree v = 1)).card = 2 := by intro r have hfilt1 : Finset.univ.filter (fun v => v = r ∨ 1 < (SimpleGraph.pathGraph 2).degree v) = {r} := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton, h_deg] omega have hfilt2 : Finset.univ.filter (fun v => v ≠ r ∧ (SimpleGraph.pathGraph 2).degree v = 1) = Finset.univ.erase r := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true, h_deg] rw [hfilt1, hfilt2] simp [h_deg, SimpleGraph.dist_self] have h_sup : Finset.univ.sup (fun r : Fin 2 => (∑ v ∈ Finset.univ.filter (fun v => v = r ∨ 1 < (SimpleGraph.pathGraph 2).degree v), (SimpleGraph.pathGraph 2).degree v * 2 ^ (SimpleGraph.pathGraph 2).dist r v) + (Finset.univ.filter (fun v => v ≠ r ∧ (SimpleGraph.pathGraph 2).degree v = 1)).card) = 2 := by apply le_antisymm · refine Finset.sup_le ?_ intro r _ rw [h_r r] · refine le_trans ?_ (Finset.le_sup (f := fun r => _) (Finset.mem_univ 0)) rw [h_r 0] rw [h_sup] rfllemma path_graph_two_stacking_number_eq_tree_estimate_three_stackable (c : Fin 2 → ℕ) (hc : ∑ v, c v = 3) : graph_config_stackable (SimpleGraph.pathGraph 2) c := by rw [Fin.sum_univ_two] at hc have hcases : (c 0 = 3 ∧ c 1 = 0) ∨ (c 0 = 2 ∧ c 1 = 1) ∨ (c 0 = 1 ∧ c 1 = 2) ∨ (c 0 = 0 ∧ c 1 = 3) := by omega rcases hcases with ⟨h0, h1⟩ | ⟨h0, h1⟩ | ⟨h0, h1⟩ | ⟨h0, h1⟩ · refine ⟨c, Relation.ReflTransGen.refl, 0, by omega, ?_⟩ intro w hw; fin_cases w; contradiction; exact h1 · let c' := Function.update (Function.update c 0 (c 0 - 2)) 1 (c 1 + 1) have hstep : graph_pebbling_step (SimpleGraph.pathGraph 2) c c' := by refine ⟨0, 1, ?_, ?_, rfl⟩ · rw [SimpleGraph.pathGraph_adj]; decide · omega refine ⟨c', Relation.ReflTransGen.single hstep, 1, by dsimp [c']; simp, ?_⟩ intro w hw; fin_cases w · dsimp [c']; simp [Function.update_of_ne, Function.update_self]; omega · contradiction · let c' := Function.update (Function.update c 1 (c 1 - 2)) 0 (c 0 + 1) have hstep : graph_pebbling_step (SimpleGraph.pathGraph 2) c c' := by refine ⟨1, 0, ?_, ?_, rfl⟩ · rw [SimpleGraph.pathGraph_adj]; decide · omega refine ⟨c', Relation.ReflTransGen.single hstep, 0, by dsimp [c']; simp, ?_⟩ intro w hw; fin_cases w · contradiction · dsimp [c']; simp [Function.update_of_ne, Function.update_self]; omega · refine ⟨c, Relation.ReflTransGen.refl, 1, by omega, ?_⟩ intro w hw; fin_cases w; exact h0; contradictionlemma path_graph_two_stacking_number_eq_tree_estimate_reflTransGen_eq_of_no_step {α : Type*} {R : α → α → Prop} {a b : α} (h : ∀ c, ¬ R a c) (hr : Relation.ReflTransGen R a b) : b = a := by induction hr using Relation.ReflTransGen.head_induction_on with | refl => rfl | head hstep _ _ => exact (h _ hstep).elimlemma path_graph_two_stacking_number_eq_tree_estimate_not_stackable_one_one : ¬ graph_config_stackable (SimpleGraph.pathGraph 2) (fun _ : Fin 2 => 1) := by intro ⟨c', hreach, v, _, hzero⟩ have hno_step : ∀ d, ¬ graph_pebbling_step (SimpleGraph.pathGraph 2) (fun _ => 1) d := by intro d ⟨u, _, _, h2, _⟩ dsimp at h2 omega have hc' : c' = (fun _ => 1) := path_graph_two_stacking_number_eq_tree_estimate_reflTransGen_eq_of_no_step hno_step hreach subst hc' fin_cases v · have := hzero 1 (by decide) contradiction · have := hzero 0 (by decide) contradictionlemma path_graph_two_stacking_number_eq_tree_estimate_stacking_number : graph_stacking_number (SimpleGraph.pathGraph 2) = 3 := by unfold graph_stacking_number set S := {t : ℕ | 2 ≤ t ∧ ∀ c : Fin 2 → ℕ, ∑ v, c v = t → graph_config_stackable (SimpleGraph.pathGraph 2) c} have h3 : 3 ∈ S := by refine ⟨by decide, ?_⟩ intro c hc exact path_graph_two_stacking_number_eq_tree_estimate_three_stackable c hc have hmin : ∀ t ∈ S, 3 ≤ t := by intro t ⟨ht2, ht_all⟩ by_contra! hlt have ht : t = 2 := by omega have hsum : ∑ v : Fin 2, (fun _ : Fin 2 => 1 : Fin 2 → ℕ) v = 2 := by decide have hstack : graph_config_stackable (SimpleGraph.pathGraph 2) (fun _ => 1) := by subst ht exact ht_all (fun _ => 1) hsum exact path_graph_two_stacking_number_eq_tree_estimate_not_stackable_one_one hstack apply le_antisymm · exact Nat.sInf_le h3 · exact le_csInf ⟨3, h3⟩ hmintheorem path_graph_two_stacking_number_eq_tree_estimate [DecidableRel (SimpleGraph.pathGraph 2).Adj] : graph_stacking_number (SimpleGraph.pathGraph 2) = simple_graph_tree_estimate (SimpleGraph.pathGraph 2) := by rw [path_graph_two_stacking_number_eq_tree_estimate_stacking_number, path_graph_two_stacking_number_eq_tree_estimate_tree_estimate]