sustainable_path_connectivity_of_descent_step
If every sustainable tree on Fin n (n ≥ 1) that is not a path has a sustainable generalized-tree-shift predecessor with strictly smaller adjacency spectral radius, then every sustainable tree on Fin n is reachable from some graph isomorphic to pathGraph n by a sequence of sustainable generalized tree shifts. This is the first conjunct of op223_poset_connectivity with the one-step descent claim isolated as a hypothesis.
Statement
theorem sustainable_path_connectivity_of_descent_step
(hstep : ∀ (n : ℕ) (_hn : 1 ≤ n) (X : SimpleGraph (Fin n)), is_sustainable_tree X →
¬ Nonempty (X ≃g SimpleGraph.pathGraph n) →
∃ Y : SimpleGraph (Fin n), is_sustainable_tree Y ∧ is_generalized_tree_shift Y X ∧
adjacency_spectral_radius Y < adjacency_spectral_radius X) :
∀ (n : ℕ) (_hn : 1 ≤ n) (X : SimpleGraph (Fin n)), is_sustainable_tree X →
∃ P : SimpleGraph (Fin n), Nonempty (P ≃g SimpleGraph.pathGraph n) ∧
Relation.ReflTransGen sustainable_gts_step P X- Source
- step towards op223_poset_connectivity
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- relation_reaches_terminal_of_nat_rank_descentLet P and Term be predicates and R a relation on a type α, with r : α → ℕ. If every non-terminal P-state X has a P-predecessor Y (that is,…
- card_filter_lt_card_filter_of_ltFor f : α → β with β linearly ordered and α finite, if f a < f b then strictly fewer elements of α have f-value below f a than below f b.
- is_sustainable_treeA tree T is sustainable if every edge of T is sustainable.
- sustainable_gts_stepA transition step between two sustainable trees T and T' on a finite type V where T' is obtained from T by a generalized tree shift.
- adjacency_spectral_radiusThe adjacency spectral radius of a simple graph G on a finite vertex set is the spectral radius of its real adjacency matrix.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - is_generalized_tree_shiftA simple graph T' on an arbitrary type V is obtained from a tree T by a generalized tree shift if T is a tree, and there exist distinct…
The proof, explained
The theorem is proved by finite descent on a natural-number rank. For each graph on n vertices, its rank is the number of graphs on n vertices with strictly smaller adjacency spectral radius. By the one-step descent hypothesis, every sustainable tree that is not a path has a sustainable predecessor with strictly smaller spectral radius, which strictly decreases this rank because the graph space is finite. An abstract well-founded descent principle on natural numbers then guarantees that every sustainable tree is reachable from some path graph by a sequence of sustainable generalized tree shifts.
Fix an arbitrary graph size n ≥ 1 and a sustainable tree X on n vertices, assuming classical logic.
We introduce the vertex count n, the condition 1 ≤ n, the tree X, and the hypothesis that X is a sustainable tree. We enable classical reasoning so that decidability for filtering finite sets is available.
intro n hn X hX classicalIt suffices to show that any sustainable tree not isomorphic to the path graph admits a sustainable generalized-tree-shift predecessor with strictly lower spectral rank.
We invoke relation_reaches_terminal_of_nat_rank_descent, choosing the state invariant to be being a sustainable tree, the terminal condition to be isomorphism with the path graph pathGraph n, the transition relation to be sustainable_gts_step, and the ranking function r(Z) to be the number of graphs on Fin n whose adjacency spectral radius is strictly less than that of Z. Since the universe of graphs on Fin n is finite, r takes values in ℕ. This reduces reachability from a path graph to establishing the one-step descent property for this rank.
uses
relation_reaches_terminal_of_nat_rank_descentrefine relation_reaches_terminal_of_nat_rank_descent (fun Z : SimpleGraph (Fin n) => is_sustainable_tree Z) (fun Z : SimpleGraph (Fin n) => Nonempty (Z ≃g SimpleGraph.pathGraph n)) (sustainable_gts_step (V := Fin n)) (fun Z : SimpleGraph (Fin n) => (Finset.univ.filter (fun W : SimpleGraph (Fin n) => adjacency_spectral_radius W < adjacency_spectral_radius Z)).card) ?_ X hX
Given a non-path sustainable tree Z, there exists a sustainable generalized-tree-shift predecessor Y with strictly smaller spectral radius.
We let Z be any sustainable tree that is not isomorphic to the path graph. Applying the one-step descent hypothesis hstep to Z produces a sustainable tree Y such that Y forms a generalized tree shift to Z and the adjacency spectral radius of Y is strictly less than that of Z.
intro Z hZsus hZ obtain ⟨Y, hYsus, hgts, hlt⟩ := hstep n hn Z hZsus hZ
The predecessor Y strictly decreases the spectral rank and yields a valid sustainable generalized-tree-shift step to Z.
Because the spectral radius of Y is strictly less than that of Z and the vertex set is finite, card_filter_lt_card_filter_of_lt implies that strictly fewer graphs have spectral radius less than that of Y than less than that of Z, so r(Y) < r(Z). Combining this with the fact that Y and Z are both sustainable trees and Y shifts to Z, Y witnesses the required descent step.
uses
card_filter_lt_card_filter_of_ltexact ⟨Y, hYsus, card_filter_lt_card_filter_of_lt (fun W : SimpleGraph (Fin n) => adjacency_spectral_radius W) hlt, hYsus, hZsus, hgts⟩
relation_reaches_terminal_of_nat_rank_descent- If an invariant property P admits a predecessor under a relation R that strictly decreases a natural-number rank r whenever a terminal condition is not met, then every element satisfying P is reachable from some terminal element by a sequence of R-steps.
card_filter_lt_card_filter_of_lt- For any function f from a finite type to a linearly ordered type, if f(a) < f(b), then strictly fewer elements have function value less than f(a) than have value less than f(b).
- The ranking function maps each graph Z to the natural number |{W | λ(W) < λ(Z)}| rather than using the spectral radius directly; this discretizes the descent into ℕ so that the finite descent lemma relation_reaches_terminal_of_nat_rank_descent applies.
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.
/-- The sustainable half of op223_poset_connectivity follows from the one-step descent claim plus finite descent on the spectral rank #{W | λ W < λ Z}. -/theorem sustainable_path_connectivity_of_descent_step (hstep : ∀ (n : ℕ) (_hn : 1 ≤ n) (X : SimpleGraph (Fin n)), is_sustainable_tree X → ¬ Nonempty (X ≃g SimpleGraph.pathGraph n) → ∃ Y : SimpleGraph (Fin n), is_sustainable_tree Y ∧ is_generalized_tree_shift Y X ∧ adjacency_spectral_radius Y < adjacency_spectral_radius X) : ∀ (n : ℕ) (_hn : 1 ≤ n) (X : SimpleGraph (Fin n)), is_sustainable_tree X → ∃ P : SimpleGraph (Fin n), Nonempty (P ≃g SimpleGraph.pathGraph n) ∧ Relation.ReflTransGen sustainable_gts_step P X := by intro n hn X hX classical refine relation_reaches_terminal_of_nat_rank_descent (fun Z : SimpleGraph (Fin n) => is_sustainable_tree Z) (fun Z : SimpleGraph (Fin n) => Nonempty (Z ≃g SimpleGraph.pathGraph n)) (sustainable_gts_step (V := Fin n)) (fun Z : SimpleGraph (Fin n) => (Finset.univ.filter (fun W : SimpleGraph (Fin n) => adjacency_spectral_radius W < adjacency_spectral_radius Z)).card) ?_ X hX intro Z hZsus hZ obtain ⟨Y, hYsus, hgts, hlt⟩ := hstep n hn Z hZsus hZ exact ⟨Y, hYsus, card_filter_lt_card_filter_of_lt (fun W : SimpleGraph (Fin n) => adjacency_spectral_radius W) hlt, hYsus, hZsus, hgts⟩