nonsustainable_star_connectivity_of_ascent_step
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
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 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.
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.
uses
relation_reaches_terminal_of_nat_rank_ascentintro 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
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.
intro Z hZns hZ obtain ⟨Y, hYns, hgts, hlt⟩ := hstep n hn Z hZns hZ
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.
uses
card_filter_gt_card_filter_of_ltexact ⟨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
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 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⟩