AFTD Auto-Formalizing Theoretical Domains

nonsustainable_star_connectivity_of_ascent_step

theoremverified

If every non-sustainable tree on Fin n (n ≥ 2) that is not a star has a non-sustainable generalized-tree-shift successor with strictly larger adjacency spectral radius, then every non-sustainable tree on Fin n reaches some graph isomorphic to the star completeBipartiteGraph (Fin 1) (Fin (n-1)) by a sequence of non-sustainable generalized tree shifts. This is the second conjunct of op223_poset_connectivity with the one-step ascent claim isolated as a hypothesis.

Statement

theorem nonsustainable_star_connectivity_of_ascent_step
    (hstep : ∀ (n : ℕ) (_hn : 2 ≤ n) (X : SimpleGraph (Fin n)), is_nonsustainable_tree X →
      ¬ Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) →
      ∃ Y : SimpleGraph (Fin n), is_nonsustainable_tree Y ∧ is_generalized_tree_shift X Y ∧
        adjacency_spectral_radius X < adjacency_spectral_radius Y) :
    ∀ (n : ℕ) (_hn : 2 ≤ n) (X : SimpleGraph (Fin n)), is_nonsustainable_tree X →
      ∃ S : SimpleGraph (Fin n), Nonempty (S ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) ∧
        Relation.ReflTransGen nonsustainable_gts_step X S
Source
step towards op223_poset_connectivity
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • relation_reaches_terminal_of_nat_rank_ascentLet P and Term be predicates and R a relation on a type α, with r : α → ℕ. If every non-terminal P-state X has a P-successor Y (that is, R…
  • card_filter_gt_card_filter_of_ltFor f : α → β with β linearly ordered and α finite, if f a < f b then strictly fewer elements of α have f-value above f b than above f a.
  • is_nonsustainable_treeA tree T is non-sustainable if T is a tree and T is not sustainable.
  • nonsustainable_gts_stepA transition step between two non-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 establishes that any non-sustainable tree on n ≥ 2 vertices reaches a star graph through non-sustainable generalized tree shifts, using a ranking function on graphs. The ranking function counts how many graphs on Fin n have strictly larger adjacency spectral radius than a given graph. Because there are only finitely many graphs on Fin n, this rank takes values in ℕ and strictly decreases whenever the spectral radius strictly increases. Applying the general termination lemma relation_reaches_terminal_of_nat_rank_ascent with the one-step spectral ascent hypothesis ensures that the process must terminate at a star graph.

  1. It suffices to show that any non-sustainable tree on n vertices that is not a star has a non-sustainable generalized-tree-shift successor with strictly smaller spectral rank.

    We introduce the number of vertices n, the assumption n ≥ 2, the initial tree X, and the hypothesis that X is non-sustainable. We then invoke relation_reaches_terminal_of_nat_rank_ascent on the finite type of simple graphs on Fin n. The invariant P is being a non-sustainable tree, the terminal condition is being isomorphic to the star graph completeBipartiteGraph (Fin 1) (Fin (n - 1)), and the transition relation R is nonsustainable_gts_step. The ranking function r(Z) counts the graphs W on Fin n whose adjacency spectral radius is strictly greater than that of Z. Since r(Z) takes values in ℕ, proving that every non-terminal state has a rank-decreasing transition guarantees that X reaches a star graph in finitely many steps.

    lines 10–19

    uses relation_reaches_terminal_of_nat_rank_ascent

      intro n hn X hX
      classical
      refine relation_reaches_terminal_of_nat_rank_ascent
        (fun Z : SimpleGraph (Fin n) => is_nonsustainable_tree Z)
        (fun Z : SimpleGraph (Fin n) =>
          Nonempty (Z ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))))
        (nonsustainable_gts_step (V := Fin n))
        (fun Z : SimpleGraph (Fin n) =>
          (Finset.univ.filter (fun W : SimpleGraph (Fin n) =>
            adjacency_spectral_radius Z < adjacency_spectral_radius W)).card) ?_ X hX
  2. From any non-sustainable tree Z that is not a star, there is a generalized-tree-shift step to another non-sustainable tree Y with strictly larger spectral radius.

    Let Z be an arbitrary non-sustainable tree on Fin n not isomorphic to the star graph. Applying the ascent hypothesis hstep to Z yields a successor graph Y that is also a non-sustainable tree, is a generalized tree shift of Z, and satisfies adjacency_spectral_radius Z < adjacency_spectral_radius Y.

    lines 20–21

      intro Z hZns hZ
      obtain ⟨Y, hYns, hgts, hlt⟩ := hstep n hn Z hZns hZ
  3. The successor Y strictly decreases the spectral rank and witnesses a valid non-sustainable generalized-tree-shift step from Z.

    Because adjacency_spectral_radius Z < adjacency_spectral_radius Y, lemma card_filter_gt_card_filter_of_lt implies that the number of graphs with spectral radius strictly greater than Y is strictly less than the number of graphs with spectral radius strictly greater than Z, so r(Y) < r(Z). Combining this rank decrease with the fact that Z and Y are non-sustainable trees and Y is a generalized tree shift of Z establishes nonsustainable_gts_step Z Y and closes the goal.

    lines 22–23

    uses card_filter_gt_card_filter_of_lt

      exact ⟨Y, hYns, card_filter_gt_card_filter_of_lt (fun W : SimpleGraph (Fin n) =>
        adjacency_spectral_radius W) hlt, hZns, hYns, hgts⟩
relation_reaches_terminal_of_nat_rank_ascent
If every state satisfying an invariant P that is not terminal can transition via relation R to another state satisfying P while strictly decreasing a natural-number-valued ranking function r, then every state satisfying P eventually reaches a terminal state via the reflexive transitive closure of R.
card_filter_gt_card_filter_of_lt
For any function f from a finite type to a linearly ordered type, if f(a) < f(b), then the number of elements with value strictly greater than f(b) is strictly less than the number of elements with value strictly greater than f(a).

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 non-sustainable half of op223_poset_connectivity follows from the one-step ascent claim plus finite ascent on the spectral rank #{W | λ Z < λ W}. -/theorem nonsustainable_star_connectivity_of_ascent_step    (hstep : ∀ (n : ℕ) (_hn : 2 ≤ n) (X : SimpleGraph (Fin n)), is_nonsustainable_tree X →      ¬ Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) →      ∃ Y : SimpleGraph (Fin n), is_nonsustainable_tree Y ∧ is_generalized_tree_shift X Y ∧        adjacency_spectral_radius X < adjacency_spectral_radius Y) :    ∀ (n : ℕ) (_hn : 2 ≤ n) (X : SimpleGraph (Fin n)), is_nonsustainable_tree X →      ∃ S : SimpleGraph (Fin n), Nonempty (S ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) ∧        Relation.ReflTransGen nonsustainable_gts_step X S := by  intro n hn X hX  classical  refine relation_reaches_terminal_of_nat_rank_ascent    (fun Z : SimpleGraph (Fin n) => is_nonsustainable_tree Z)    (fun Z : SimpleGraph (Fin n) =>      Nonempty (Z ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))))    (nonsustainable_gts_step (V := Fin n))    (fun Z : SimpleGraph (Fin n) =>      (Finset.univ.filter (fun W : SimpleGraph (Fin n) =>        adjacency_spectral_radius Z < adjacency_spectral_radius W)).card) ?_ X hX  intro Z hZns hZ  obtain ⟨Y, hYns, hgts, hlt⟩ := hstep n hn Z hZns hZ  exact ⟨Y, hYns, card_filter_gt_card_filter_of_lt (fun W : SimpleGraph (Fin n) =>    adjacency_spectral_radius W) hlt, hZns, hYns, hgts⟩
See it in the graphDiscuss this resultChallenge it