AFTD Auto-Formalizing Theoretical Domains

sustainable_path_connectivity_of_descent_step

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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.

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

    lines 10–11

      intro n hn X hX
      classical
  2. It 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.

    lines 12–18

    uses relation_reaches_terminal_of_nat_rank_descent

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

    lines 19–20

      intro Z hZsus hZ
      obtain ⟨Y, hYsus, hgts, hlt⟩ := hstep n hn Z hZsus hZ
  4. 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.

    lines 21–23

    uses card_filter_lt_card_filter_of_lt

      exact ⟨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).

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

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