AFTD Auto-Formalizing Theoretical Domains

path_graph_three_stacking_number_eq_tree_estimate

theoremverifiedoriginal

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.

  1. 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.

    lines 26–27

    uses SimpleGraph.pathGraph_adj

      rw [SimpleGraph.pathGraph_adj]
      fin_cases u <;> fin_cases v <;> decide
  2. 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.

    lines 31–41

    uses path_graph_three_stacked, Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_eq

      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⟩
  3. 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.

    lines 47–67

    uses path_graph_three_adj_iff

      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 <;> simp
  4. 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.

    lines 72–92

    uses path_graph_three_stacked_iff, Relation.ReflTransGen.refl, Relation.ReflTransGen.head, path_graph_three_stk, path_graph_three_step_iff

      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)
  5. 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.

    lines 97–118

    uses Relation.ReflTransGen.head_induction_on, path_graph_three_dead, path_graph_three_stacked_iff, path_graph_three_step_iff

      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))
  6. 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.

    line 122

      decide
  7. Specific 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.

    line 128

      decide
  8. Every 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.

    lines 131–139

    uses Fin.sum_univ_three, path_graph_three_stk_sound, path_graph_three_stk_seven

      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
  9. 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.

    lines 140–149

    uses path_graph_three_dead_examples, path_graph_three_dead_sound

      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⟩
  10. 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.

    lines 150–155

    uses le_antisymm, Nat.sInf_le, le_csInf

      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)
  11. 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.

    lines 159–167

    uses SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.mem_neighborFinset, Finset.mem_filter, Finset.mem_univ, true_and, path_graph_three_adj_iff

      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 <;> decide
  12. 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.

    lines 171–197

    uses path_graph_three_degree, SimpleGraph.dist_self, Finset.sum_pair, Finset.sum_singleton

      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]
      decide
  13. 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.

    line 203

    uses path_graph_three_stacking_number, path_graph_three_tree_estimate

      rw [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.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it