path_graph_three_stacking_number_eq_tree_estimate
Conjecture 5.6 (OP-144) holds for the path on three vertices: stack(P₃) = estim(P₃) (both equal 7).
Statement
theorem path_graph_three_stacking_number_eq_tree_estimate
[DecidableRel (SimpleGraph.pathGraph 3).Adj] :
graph_stacking_number (SimpleGraph.pathGraph 3) =
simple_graph_tree_estimate (SimpleGraph.pathGraph 3)- Related work
- arXiv:2610.09650 (The Almost Stacked Hypothesis: A Conjectural Analogue of Sjöstrand's Cover Pebbling Theorem), Conjecture 5.6 for the path P₃; consistent with stack(P_n) = 2^n − 1 (Theorem 4.4, from earlier work).
- 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
Conjecture 5.6 holds for the path graph on three vertices P₃ by showing that both its stacking number stack(P₃) and its tree estimate estim(P₃) equal 7. The stacking number is verified by computational enumeration: an exhaustive search confirms that every 7-pebble configuration can be stacked in at most 7 moves, while explicit unstackable counterexamples are verified for all pebble counts from 2 to 6. Separately, the tree estimate is calculated directly from its definition by evaluating the vertex degrees and graph distances across all possible rootings.
The adjacency relation on P₃ consists of the edges {0, 1} and {1, 2}.
We rewrite with SimpleGraph.pathGraph_adj, which states that vertices are adjacent when their indices differ by 1, and exhaustively check all pairs of vertices in Fin 3 using fin_cases and decide.
uses
SimpleGraph.pathGraph_adjrw [SimpleGraph.pathGraph_adj] fin_cases u <;> fin_cases v <;> decide
A pebble configuration on P₃ is stacked according to path_graph_three_stacked if and only if all pebbles reside on a single vertex.
We expand the definition of path_graph_three_stacked and simplify Boolean connectives to logical ones. In each direction, exactly one vertex has strictly positive pebbles while all other vertices have zero pebbles.
uses
path_graph_three_stacked,Bool.or_eq_true,Bool.and_eq_true,decide_eq_true_eqsimp only [path_graph_three_stacked, Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_eq] constructor · rintro ((⟨⟨h0, h1⟩, h2⟩ | ⟨⟨h0, h1⟩, h2⟩) | ⟨⟨h0, h1⟩, h2⟩) · exact ⟨0, h0, fun w hw => by fin_cases w <;> simp_all⟩ · exact ⟨1, h1, fun w hw => by fin_cases w <;> simp_all⟩ · exact ⟨2, h2, fun w hw => by fin_cases w <;> simp_all⟩ · rintro ⟨v, hv, hw⟩ fin_cases v · exact Or.inl (Or.inl ⟨⟨hv, hw 1 (by decide)⟩, hw 2 (by decide)⟩) · exact Or.inl (Or.inr ⟨⟨hw 0 (by decide), hv⟩, hw 2 (by decide)⟩) · exact Or.inr ⟨⟨hw 0 (by decide), hw 1 (by decide)⟩, hv⟩
A single pebbling step on P₃ is valid if and only if it is one of the four moves 0→1, 1→0, 1→2, or 2→1, each consuming 2 pebbles from the source and adding 1 to the destination.
A pebbling step requires two adjacent vertices with at least 2 pebbles at the source. Using path_graph_three_adj_iff, the only possible edges are {0, 1} and {1, 2}. Case analysis on the edge and direction characterizes all possible single-step transitions.
uses
path_graph_three_adj_iffconstructor · rintro ⟨u, v, huv, hu, rfl⟩ rw [path_graph_three_adj_iff] at huv rcases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · refine Or.inl ⟨hu, ?_⟩ funext i; fin_cases i <;> simp · refine Or.inr (Or.inl ⟨hu, ?_⟩) funext i; fin_cases i <;> simp · refine Or.inr (Or.inr (Or.inl ⟨hu, ?_⟩)) funext i; fin_cases i <;> simp · refine Or.inr (Or.inr (Or.inr ⟨hu, ?_⟩)) funext i; fin_cases i <;> simp · rintro (⟨hu, rfl⟩ | ⟨hu, rfl⟩ | ⟨hu, rfl⟩ | ⟨hu, rfl⟩) · refine ⟨0, 1, (path_graph_three_adj_iff _ _).2 (by decide), hu, ?_⟩ funext i; fin_cases i <;> simp · refine ⟨1, 0, (path_graph_three_adj_iff _ _).2 (by decide), hu, ?_⟩ funext i; fin_cases i <;> simp · refine ⟨1, 2, (path_graph_three_adj_iff _ _).2 (by decide), hu, ?_⟩ funext i; fin_cases i <;> simp · refine ⟨2, 1, (path_graph_three_adj_iff _ _).2 (by decide), hu, ?_⟩ funext i; fin_cases i <;> simp
The search procedure path_graph_three_stk is sound: returning true within fuel k implies the configuration is stackable.
By induction on the fuel k: for k = 0, the configuration is already stacked; for k + 1, if it is not already stacked, the search branches over all four possible pebbling moves. If any move yields a configuration that succeeds with fuel k, the induction hypothesis provides reachability to a stacked state, which is prepended using Relation.ReflTransGen.head.
uses
path_graph_three_stacked_iff,Relation.ReflTransGen.refl,Relation.ReflTransGen.head,path_graph_three_stk,path_graph_three_step_iffinduction k generalizing c with | zero => obtain ⟨v, hv, hw⟩ := (path_graph_three_stacked_iff c).1 h exact ⟨c, Relation.ReflTransGen.refl, v, hv, hw⟩ | succ k ih => have back : ∀ d, graph_pebbling_step (SimpleGraph.pathGraph 3) c d → path_graph_three_stk k (d 0) (d 1) (d 2) = true → graph_config_stackable (SimpleGraph.pathGraph 3) c := by intro d hd hk obtain ⟨e, he, hst⟩ := ih d hk exact ⟨e, Relation.ReflTransGen.head hd he, hst⟩ simp only [path_graph_three_stk, Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_eq] at h rcases h with (((h | ⟨ha, h⟩) | ⟨hb, h⟩) | ⟨hb, h⟩) | ⟨hc, h⟩ · obtain ⟨v, hv, hw⟩ := (path_graph_three_stacked_iff c).1 h exact ⟨c, Relation.ReflTransGen.refl, v, hv, hw⟩ · exact back _ ((path_graph_three_step_iff _ _).2 (Or.inl ⟨ha, rfl⟩)) (by simpa using h) · exact back _ ((path_graph_three_step_iff _ _).2 (Or.inr (Or.inl ⟨hb, rfl⟩))) (by simpa using h) · exact back _ ((path_graph_three_step_iff _ _).2 (Or.inr (Or.inr (Or.inl ⟨hb, rfl⟩)))) (by simpa using h) · exact back _ ((path_graph_three_step_iff _ _).2 (Or.inr (Or.inr (Or.inr ⟨hc, rfl⟩)))) (by simpa using h)
The procedure path_graph_three_dead is sound: returning true for fuel k certifies that no stacked configuration can ever be reached.
Assuming reachability to a stacked state, we induct on the step sequence via Relation.ReflTransGen.head_induction_on. In the base case of zero steps, the configuration is stacked, contradicting path_graph_three_dead. In the inductive step, each valid move reduces the available fuel by 1 and preserves deadness, deriving a contradiction via the induction hypothesis.
uses
Relation.ReflTransGen.head_induction_on,path_graph_three_dead,path_graph_three_stacked_iff,path_graph_three_step_iffrintro ⟨e, he, hst⟩ induction he using Relation.ReflTransGen.head_induction_on generalizing k with | refl => cases k <;> · simp only [path_graph_three_dead, Bool.and_eq_true, Bool.not_eq_true'] at h have := (path_graph_three_stacked_iff _).2 hst simp_all | head hd _ ih => rename_i c c' cases k with | zero => simp only [path_graph_three_dead, Bool.and_eq_true, decide_eq_true_eq] at h rcases (path_graph_three_step_iff _ _).1 hd with ⟨h', -⟩ | ⟨h', -⟩ | ⟨h', -⟩ | ⟨h', -⟩ <;> omega | succ k => simp only [path_graph_three_dead, Bool.and_eq_true, Bool.or_eq_true, decide_eq_true_eq] at h obtain ⟨⟨⟨⟨-, h0⟩, h1⟩, h2⟩, h3⟩ := h rcases (path_graph_three_step_iff _ _).1 hd with ⟨h', rfl⟩ | ⟨h', rfl⟩ | ⟨h', rfl⟩ | ⟨h', rfl⟩ · exact ih k (by simpa using h0.resolve_left (by omega)) · exact ih k (by simpa using h1.resolve_left (by omega)) · exact ih k (by simpa using h2.resolve_left (by omega)) · exact ih k (by simpa using h3.resolve_left (by omega))
Every configuration of 7 pebbles on P₃ can reach a stacked configuration in at most 7 moves. automation
The decide tactic evaluates the search procedure path_graph_three_stk with fuel 7 for all partitions of 7 pebbles among the three vertices, verifying it returns true in every case.
decideSpecific configurations of sizes 2, 3, 4, 5, and 6 pebbles are verified to be dead. automation
The decide tactic verifies that path_graph_three_dead returns true on (1,0,1), (1,1,1), (3,0,1), (3,1,1), and (5,0,1) with fuels 2, 3, 4, 5, and 6 respectively.
decideEvery configuration of 7 pebbles on P₃ is stackable, so 7 is an upper bound in the definition of the stacking number.
Any configuration c with sum equal to 7 is parameterized as (c 0, c 1, 7 - c 0 - c 1). By path_graph_three_stk_seven and path_graph_three_stk_sound, every such configuration is stackable.
uses
Fin.sum_univ_three,path_graph_three_stk_sound,path_graph_three_stk_sevenhave hvec : ∀ c : Fin 3 → ℕ, c = ![c 0, c 1, c 2] := fun c => by funext i; fin_cases i <;> rfl have h7 : 7 ∈ {t : ℕ | 2 ≤ t ∧ ∀ c : Fin 3 → ℕ, ∑ v, c v = t → graph_config_stackable (SimpleGraph.pathGraph 3) c} := by refine ⟨by norm_num, fun c hc => ?_⟩ rw [Fin.sum_univ_three] at hc apply path_graph_three_stk_sound 7 have := path_graph_three_stk_seven (c 0) (by omega) (c 1) (by omega) rwa [show 7 - c 0 - c 1 = c 2 by omega] at this
For each pebble count t from 2 to 6, there exists a configuration that cannot be stacked.
Using interval_cases on t ∈ {2, 3, 4, 5, 6}, we exhibit the explicit witness verified in path_graph_three_dead_examples and apply path_graph_three_dead_sound to prove it is unstackable.
uses
path_graph_three_dead_examples,path_graph_three_dead_soundhave hdead : ∀ t, 2 ≤ t → t < 7 → ∃ c : Fin 3 → ℕ, ∑ v, c v = t ∧ ¬ graph_config_stackable (SimpleGraph.pathGraph 3) c := by obtain ⟨d2, d3, d4, d5, d6⟩ := path_graph_three_dead_examples intro t ht2 ht7 interval_cases t · exact ⟨![1, 0, 1], by decide, path_graph_three_dead_sound 2 _ d2⟩ · exact ⟨![1, 1, 1], by decide, path_graph_three_dead_sound 3 _ d3⟩ · exact ⟨![3, 0, 1], by decide, path_graph_three_dead_sound 4 _ d4⟩ · exact ⟨![3, 1, 1], by decide, path_graph_three_dead_sound 5 _ d5⟩ · exact ⟨![5, 0, 1], by decide, path_graph_three_dead_sound 6 _ d6⟩
The stacking number of P₃ is 7.
The stacking number is defined as the infimum of all t ≥ 2 such that every t-pebble configuration is stackable. Since 7 satisfies this property and no smaller t ≥ 2 does, the infimum is 7 by le_antisymm, Nat.sInf_le, and le_csInf.
uses
le_antisymm,Nat.sInf_le,le_csInfunfold graph_stacking_number apply le_antisymm (Nat.sInf_le h7) refine le_csInf ⟨7, h7⟩ fun t ⟨ht2, hall⟩ => ?_ by_contra hlt obtain ⟨c, hc, hns⟩ := hdead t ht2 (by omega) exact hns (hall c hc)
The vertex degrees of P₃ are deg(1) = 2 and deg(0) = deg(2) = 1.
We express degree as the cardinality of the neighbor finset using SimpleGraph.card_neighborFinset_eq_degree, filter by adjacency via path_graph_three_adj_iff, and compute the cardinality by case analysis on v.
uses
SimpleGraph.card_neighborFinset_eq_degree,SimpleGraph.mem_neighborFinset,Finset.mem_filter,Finset.mem_univ,true_and,path_graph_three_adj_iffrw [← SimpleGraph.card_neighborFinset_eq_degree] have : (SimpleGraph.pathGraph 3).neighborFinset v = Finset.univ.filter (fun w => (v = 0 ∧ w = 1) ∨ (v = 1 ∧ w = 0) ∨ (v = 1 ∧ w = 2) ∨ (v = 2 ∧ w = 1)) := by ext w simp only [SimpleGraph.mem_neighborFinset, Finset.mem_filter, Finset.mem_univ, true_and, path_graph_three_adj_iff] rw [this] fin_cases v <;> decide
The tree estimate of P₃ equals 7.
We unfold simple_graph_tree_estimate and plug in the degrees. Evaluating the formula for root r = 1 gives 4, and for roots r = 0 and r = 2 gives 6. Taking the supremum over roots yields 1 + max(6, 4, 6) = 7, and max(2, 7) = 7.
uses
path_graph_three_degree,SimpleGraph.dist_self,Finset.sum_pair,Finset.sum_singletonunfold simple_graph_tree_estimate simp only [path_graph_three_degree] have hd01 : (SimpleGraph.pathGraph 3).dist 0 1 = 1 := SimpleGraph.dist_eq_one_iff_adj.2 ((path_graph_three_adj_iff _ _).2 (by decide)) have hd21 : (SimpleGraph.pathGraph 3).dist 2 1 = 1 := SimpleGraph.dist_eq_one_iff_adj.2 ((path_graph_three_adj_iff _ _).2 (by decide)) have h : ∀ r : Fin 3, (∑ v ∈ Finset.univ.filter (fun v : Fin 3 => v = r ∨ 1 < if v = 1 then 2 else 1), (if v = 1 then 2 else 1) * 2 ^ (SimpleGraph.pathGraph 3).dist r v) + (Finset.univ.filter (fun v : Fin 3 => v ≠ r ∧ (if v = 1 then 2 else 1) = 1)).card = if r = 1 then 4 else 6 := by intro r fin_cases r <;> dsimp only <;> simp only [Fin.zero_eta, Fin.mk_one, Fin.reduceFinMk] · rw [show Finset.univ.filter (fun v : Fin 3 => v = 0 ∨ 1 < if v = 1 then 2 else 1) = {0, 1} by decide] rw [Finset.sum_pair (by decide), SimpleGraph.dist_self, hd01] decide · rw [show Finset.univ.filter (fun v : Fin 3 => v = 1 ∨ 1 < if v = 1 then 2 else 1) = {1} by decide] rw [Finset.sum_singleton, SimpleGraph.dist_self] decide · rw [show Finset.univ.filter (fun v : Fin 3 => v = 2 ∨ 1 < if v = 1 then 2 else 1) = {2, 1} by decide] rw [Finset.sum_pair (by decide), SimpleGraph.dist_self, hd21] decide simp only [h] decide
The stacking number of P₃ equals its tree estimate.
Both quantities were shown to equal 7; rewriting by path_graph_three_stacking_number and path_graph_three_tree_estimate completes the proof.
uses
path_graph_three_stacking_number,path_graph_three_tree_estimaterw [path_graph_three_stacking_number, path_graph_three_tree_estimate]
SimpleGraph.pathGraph_adj- Two vertices in a path graph P_n are adjacent if and only if their indices differ by 1.
path_graph_three_stacked- A Boolean function indicating whether pebbles are concentrated entirely on one of the three vertices of P₃.
Bool.or_eq_true- A Boolean disjunction evaluates to true if and only if at least one operand is true.
Bool.and_eq_true- A Boolean conjunction evaluates to true if and only if both operands are true.
decide_eq_true_eq- The decision function decide(p) equals true if and only if the proposition p is true.
path_graph_three_adj_iff- The edges of the 3-vertex path graph P₃ are precisely {0, 1} and {1, 2}.
path_graph_three_stacked_iff- A configuration on P₃ satisfies path_graph_three_stacked if and only if all pebbles reside on a single vertex.
Relation.ReflTransGen.refl- Every element is reachable from itself in zero steps in the reflexive-transitive closure.
Relation.ReflTransGen.head- A single step prepended to a multi-step reachability path yields a valid reachability path.
path_graph_three_stk- A bounded recursive search function testing whether a configuration on P₃ can reach a stacked state in at most k pebbling steps.
path_graph_three_step_iff- A single pebbling step on P₃ is valid if and only if it is one of the four moves 0→1, 1→0, 1→2, or 2→1, each consuming 2 pebbles at the source and adding 1 at the destination.
Relation.ReflTransGen.head_induction_on- Induction principle for reflexive-transitive reachability decomposing a sequence of steps from the head.
path_graph_three_dead- A bounded search function certifying that no sequence of pebbling steps of length at most k can reach a stacked configuration.
Fin.sum_univ_three- The sum of a function over Fin 3 equals f(0) + f(1) + f(2).
path_graph_three_stk_sound- If path_graph_three_stk returns true for fuel k and configuration c, then c is stackable on P₃.
path_graph_three_stk_seven- Every 7-pebble configuration on P₃ can be stacked in at most 7 moves.
path_graph_three_dead_examples- The specific configurations (1,0,1), (1,1,1), (3,0,1), (3,1,1), and (5,0,1) are verified to be dead configurations.
path_graph_three_dead_sound- If path_graph_three_dead returns true for fuel k and configuration c, then c cannot be stacked on P₃.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in that set.
le_csInf- If a is a lower bound for a nonempty set bounded below, then a ≤ sInf(s).
SimpleGraph.card_neighborFinset_eq_degree- The degree of a vertex in a simple graph equals the size of its neighbor finset.
SimpleGraph.mem_neighborFinset- A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- True ∧ p is equivalent to p.
path_graph_three_degree- In P₃, the middle vertex 1 has degree 2, while the endpoints 0 and 2 have degree 1.
SimpleGraph.dist_self- The graph distance from any vertex to itself is 0.
Finset.sum_pair- The sum of a function over a pair of distinct elements {a, b} equals f(a) + f(b).
Finset.sum_singleton- The sum of a function over a singleton set {a} equals f(a).
path_graph_three_stacking_number- The stacking number of the path graph P₃ is 7.
path_graph_three_tree_estimate- The tree estimate of the path graph P₃ equals 7.
- Exhaustive verification that every 7-pebble configuration is stackable and that the specified 2- to 6-pebble configurations are unstackable is performed computationally by Lean's kernel using `decide`.
- The tree estimate formula is evaluated by explicit case analysis on the root vertex and finite set operations.
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.
/-- Stacked triple on the three vertices of `P₃`. -/def path_graph_three_stacked (a b c : ℕ) : Bool := (0 < a && b = 0 && c = 0) || (a = 0 && 0 < b && c = 0) || (a = 0 && b = 0 && 0 < c)/-- Bounded search for a stacking sequence on `P₃` (moves 0→1, 1→0, 1→2, 2→1). -/def path_graph_three_stk : ℕ → ℕ → ℕ → ℕ → Bool | 0, a, b, c => path_graph_three_stacked a b c | k + 1, a, b, c => path_graph_three_stacked a b c || (2 ≤ a && path_graph_three_stk k (a - 2) (b + 1) c) || (2 ≤ b && path_graph_three_stk k (a + 1) (b - 2) c) || (2 ≤ b && path_graph_three_stk k a (b - 2) (c + 1)) || (2 ≤ c && path_graph_three_stk k a (b + 1) (c - 2))/-- No configuration reachable on `P₃` is stacked (fuel bounds the number of steps). -/def path_graph_three_dead : ℕ → ℕ → ℕ → ℕ → Bool | 0, a, b, c => !path_graph_three_stacked a b c && a < 2 && b < 2 && c < 2 | k + 1, a, b, c => !path_graph_three_stacked a b c && (a < 2 || path_graph_three_dead k (a - 2) (b + 1) c) && (b < 2 || path_graph_three_dead k (a + 1) (b - 2) c) && (b < 2 || path_graph_three_dead k a (b - 2) (c + 1)) && (c < 2 || path_graph_three_dead k a (b + 1) (c - 2))theorem path_graph_three_adj_iff (u v : Fin 3) : (SimpleGraph.pathGraph 3).Adj u v ↔ (u = 0 ∧ v = 1) ∨ (u = 1 ∧ v = 0) ∨ (u = 1 ∧ v = 2) ∨ (u = 2 ∧ v = 1) := by rw [SimpleGraph.pathGraph_adj] fin_cases u <;> fin_cases v <;> decidetheorem path_graph_three_stacked_iff (c : Fin 3 → ℕ) : path_graph_three_stacked (c 0) (c 1) (c 2) = true ↔ ∃ v, 0 < c v ∧ ∀ w, w ≠ v → c w = 0 := by simp only [path_graph_three_stacked, Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_eq] constructor · rintro ((⟨⟨h0, h1⟩, h2⟩ | ⟨⟨h0, h1⟩, h2⟩) | ⟨⟨h0, h1⟩, h2⟩) · exact ⟨0, h0, fun w hw => by fin_cases w <;> simp_all⟩ · exact ⟨1, h1, fun w hw => by fin_cases w <;> simp_all⟩ · exact ⟨2, h2, fun w hw => by fin_cases w <;> simp_all⟩ · rintro ⟨v, hv, hw⟩ fin_cases v · exact Or.inl (Or.inl ⟨⟨hv, hw 1 (by decide)⟩, hw 2 (by decide)⟩) · exact Or.inl (Or.inr ⟨⟨hw 0 (by decide), hv⟩, hw 2 (by decide)⟩) · exact Or.inr ⟨⟨hw 0 (by decide), hw 1 (by decide)⟩, hv⟩theorem path_graph_three_step_iff (c d : Fin 3 → ℕ) : graph_pebbling_step (SimpleGraph.pathGraph 3) c d ↔ (2 ≤ c 0 ∧ d = ![c 0 - 2, c 1 + 1, c 2]) ∨ (2 ≤ c 1 ∧ d = ![c 0 + 1, c 1 - 2, c 2]) ∨ (2 ≤ c 1 ∧ d = ![c 0, c 1 - 2, c 2 + 1]) ∨ (2 ≤ c 2 ∧ d = ![c 0, c 1 + 1, c 2 - 2]) := by constructor · rintro ⟨u, v, huv, hu, rfl⟩ rw [path_graph_three_adj_iff] at huv rcases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · refine Or.inl ⟨hu, ?_⟩ funext i; fin_cases i <;> simp · refine Or.inr (Or.inl ⟨hu, ?_⟩) funext i; fin_cases i <;> simp · refine Or.inr (Or.inr (Or.inl ⟨hu, ?_⟩)) funext i; fin_cases i <;> simp · refine Or.inr (Or.inr (Or.inr ⟨hu, ?_⟩)) funext i; fin_cases i <;> simp · rintro (⟨hu, rfl⟩ | ⟨hu, rfl⟩ | ⟨hu, rfl⟩ | ⟨hu, rfl⟩) · refine ⟨0, 1, (path_graph_three_adj_iff _ _).2 (by decide), hu, ?_⟩ funext i; fin_cases i <;> simp · refine ⟨1, 0, (path_graph_three_adj_iff _ _).2 (by decide), hu, ?_⟩ funext i; fin_cases i <;> simp · refine ⟨1, 2, (path_graph_three_adj_iff _ _).2 (by decide), hu, ?_⟩ funext i; fin_cases i <;> simp · refine ⟨2, 1, (path_graph_three_adj_iff _ _).2 (by decide), hu, ?_⟩ funext i; fin_cases i <;> simptheorem path_graph_three_stk_sound (k : ℕ) (c : Fin 3 → ℕ) (h : path_graph_three_stk k (c 0) (c 1) (c 2) = true) : graph_config_stackable (SimpleGraph.pathGraph 3) c := by induction k generalizing c with | zero => obtain ⟨v, hv, hw⟩ := (path_graph_three_stacked_iff c).1 h exact ⟨c, Relation.ReflTransGen.refl, v, hv, hw⟩ | succ k ih => have back : ∀ d, graph_pebbling_step (SimpleGraph.pathGraph 3) c d → path_graph_three_stk k (d 0) (d 1) (d 2) = true → graph_config_stackable (SimpleGraph.pathGraph 3) c := by intro d hd hk obtain ⟨e, he, hst⟩ := ih d hk exact ⟨e, Relation.ReflTransGen.head hd he, hst⟩ simp only [path_graph_three_stk, Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_eq] at h rcases h with (((h | ⟨ha, h⟩) | ⟨hb, h⟩) | ⟨hb, h⟩) | ⟨hc, h⟩ · obtain ⟨v, hv, hw⟩ := (path_graph_three_stacked_iff c).1 h exact ⟨c, Relation.ReflTransGen.refl, v, hv, hw⟩ · exact back _ ((path_graph_three_step_iff _ _).2 (Or.inl ⟨ha, rfl⟩)) (by simpa using h) · exact back _ ((path_graph_three_step_iff _ _).2 (Or.inr (Or.inl ⟨hb, rfl⟩))) (by simpa using h) · exact back _ ((path_graph_three_step_iff _ _).2 (Or.inr (Or.inr (Or.inl ⟨hb, rfl⟩)))) (by simpa using h) · exact back _ ((path_graph_three_step_iff _ _).2 (Or.inr (Or.inr (Or.inr ⟨hc, rfl⟩)))) (by simpa using h)theorem path_graph_three_dead_sound (k : ℕ) (c : Fin 3 → ℕ) (h : path_graph_three_dead k (c 0) (c 1) (c 2) = true) : ¬ graph_config_stackable (SimpleGraph.pathGraph 3) c := by rintro ⟨e, he, hst⟩ induction he using Relation.ReflTransGen.head_induction_on generalizing k with | refl => cases k <;> · simp only [path_graph_three_dead, Bool.and_eq_true, Bool.not_eq_true'] at h have := (path_graph_three_stacked_iff _).2 hst simp_all | head hd _ ih => rename_i c c' cases k with | zero => simp only [path_graph_three_dead, Bool.and_eq_true, decide_eq_true_eq] at h rcases (path_graph_three_step_iff _ _).1 hd with ⟨h', -⟩ | ⟨h', -⟩ | ⟨h', -⟩ | ⟨h', -⟩ <;> omega | succ k => simp only [path_graph_three_dead, Bool.and_eq_true, Bool.or_eq_true, decide_eq_true_eq] at h obtain ⟨⟨⟨⟨-, h0⟩, h1⟩, h2⟩, h3⟩ := h rcases (path_graph_three_step_iff _ _).1 hd with ⟨h', rfl⟩ | ⟨h', rfl⟩ | ⟨h', rfl⟩ | ⟨h', rfl⟩ · exact ih k (by simpa using h0.resolve_left (by omega)) · exact ih k (by simpa using h1.resolve_left (by omega)) · exact ih k (by simpa using h2.resolve_left (by omega)) · exact ih k (by simpa using h3.resolve_left (by omega))theorem path_graph_three_stk_seven : ∀ a ≤ 7, ∀ b ≤ 7 - a, path_graph_three_stk 7 a b (7 - a - b) = true := by decidetheorem path_graph_three_dead_examples : path_graph_three_dead 2 1 0 1 = true ∧ path_graph_three_dead 3 1 1 1 = true ∧ path_graph_three_dead 4 3 0 1 = true ∧ path_graph_three_dead 5 3 1 1 = true ∧ path_graph_three_dead 6 5 0 1 = true := by decidetheorem path_graph_three_stacking_number : graph_stacking_number (SimpleGraph.pathGraph 3) = 7 := by have hvec : ∀ c : Fin 3 → ℕ, c = ![c 0, c 1, c 2] := fun c => by funext i; fin_cases i <;> rfl have h7 : 7 ∈ {t : ℕ | 2 ≤ t ∧ ∀ c : Fin 3 → ℕ, ∑ v, c v = t → graph_config_stackable (SimpleGraph.pathGraph 3) c} := by refine ⟨by norm_num, fun c hc => ?_⟩ rw [Fin.sum_univ_three] at hc apply path_graph_three_stk_sound 7 have := path_graph_three_stk_seven (c 0) (by omega) (c 1) (by omega) rwa [show 7 - c 0 - c 1 = c 2 by omega] at this have hdead : ∀ t, 2 ≤ t → t < 7 → ∃ c : Fin 3 → ℕ, ∑ v, c v = t ∧ ¬ graph_config_stackable (SimpleGraph.pathGraph 3) c := by obtain ⟨d2, d3, d4, d5, d6⟩ := path_graph_three_dead_examples intro t ht2 ht7 interval_cases t · exact ⟨![1, 0, 1], by decide, path_graph_three_dead_sound 2 _ d2⟩ · exact ⟨![1, 1, 1], by decide, path_graph_three_dead_sound 3 _ d3⟩ · exact ⟨![3, 0, 1], by decide, path_graph_three_dead_sound 4 _ d4⟩ · exact ⟨![3, 1, 1], by decide, path_graph_three_dead_sound 5 _ d5⟩ · exact ⟨![5, 0, 1], by decide, path_graph_three_dead_sound 6 _ d6⟩ unfold graph_stacking_number apply le_antisymm (Nat.sInf_le h7) refine le_csInf ⟨7, h7⟩ fun t ⟨ht2, hall⟩ => ?_ by_contra hlt obtain ⟨c, hc, hns⟩ := hdead t ht2 (by omega) exact hns (hall c hc)theorem path_graph_three_degree [DecidableRel (SimpleGraph.pathGraph 3).Adj] (v : Fin 3) : (SimpleGraph.pathGraph 3).degree v = if v = 1 then 2 else 1 := by rw [← SimpleGraph.card_neighborFinset_eq_degree] have : (SimpleGraph.pathGraph 3).neighborFinset v = Finset.univ.filter (fun w => (v = 0 ∧ w = 1) ∨ (v = 1 ∧ w = 0) ∨ (v = 1 ∧ w = 2) ∨ (v = 2 ∧ w = 1)) := by ext w simp only [SimpleGraph.mem_neighborFinset, Finset.mem_filter, Finset.mem_univ, true_and, path_graph_three_adj_iff] rw [this] fin_cases v <;> decidetheorem path_graph_three_tree_estimate [DecidableRel (SimpleGraph.pathGraph 3).Adj] : simple_graph_tree_estimate (SimpleGraph.pathGraph 3) = 7 := by unfold simple_graph_tree_estimate simp only [path_graph_three_degree] have hd01 : (SimpleGraph.pathGraph 3).dist 0 1 = 1 := SimpleGraph.dist_eq_one_iff_adj.2 ((path_graph_three_adj_iff _ _).2 (by decide)) have hd21 : (SimpleGraph.pathGraph 3).dist 2 1 = 1 := SimpleGraph.dist_eq_one_iff_adj.2 ((path_graph_three_adj_iff _ _).2 (by decide)) have h : ∀ r : Fin 3, (∑ v ∈ Finset.univ.filter (fun v : Fin 3 => v = r ∨ 1 < if v = 1 then 2 else 1), (if v = 1 then 2 else 1) * 2 ^ (SimpleGraph.pathGraph 3).dist r v) + (Finset.univ.filter (fun v : Fin 3 => v ≠ r ∧ (if v = 1 then 2 else 1) = 1)).card = if r = 1 then 4 else 6 := by intro r fin_cases r <;> dsimp only <;> simp only [Fin.zero_eta, Fin.mk_one, Fin.reduceFinMk] · rw [show Finset.univ.filter (fun v : Fin 3 => v = 0 ∨ 1 < if v = 1 then 2 else 1) = {0, 1} by decide] rw [Finset.sum_pair (by decide), SimpleGraph.dist_self, hd01] decide · rw [show Finset.univ.filter (fun v : Fin 3 => v = 1 ∨ 1 < if v = 1 then 2 else 1) = {1} by decide] rw [Finset.sum_singleton, SimpleGraph.dist_self] decide · rw [show Finset.univ.filter (fun v : Fin 3 => v = 2 ∨ 1 < if v = 1 then 2 else 1) = {2, 1} by decide] rw [Finset.sum_pair (by decide), SimpleGraph.dist_self, hd21] decide simp only [h] decidetheorem path_graph_three_stacking_number_eq_tree_estimate [DecidableRel (SimpleGraph.pathGraph 3).Adj] : graph_stacking_number (SimpleGraph.pathGraph 3) = simple_graph_tree_estimate (SimpleGraph.pathGraph 3) := by rw [path_graph_three_stacking_number, path_graph_three_tree_estimate]