nonsustainable_gts_step
A 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.
Statement
def nonsustainable_gts_step {V : Type*} [Fintype V] [DecidableEq V] (T T' : SimpleGraph V) : Prop
- Defined in
- arXiv:2610.17078 Open Problem 6.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 2
- is_nonsustainable_treeA tree T is non-sustainable if T is a tree and T is not sustainable.
- 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…
- Used by 5
- op223_nonsustainable_connectivity_fin_fourEvery non-sustainable tree X on Fin 4 can reach a star graph isomorphic to completeBipartiteGraph (Fin 1) (Fin 3) by a sequence of…
- op223_shift_bad_edge_yields_stepIf a nonsustainable tree undergoes an adjacent shift and a retained beneficiary edge remains nonsustainable, the shift is a step between…
- nonsustainable_star_connectivity_of_ascent_stepIf every non-sustainable tree on Fin n (n ≥ 2) that is not a star has a non-sustainable generalized-tree-shift successor with strictly…
- op223_star_connectivity_of_nonleaf_rank_stepIf every non-sustainable tree X on Fin n (n ≥ 2) that is not a star has a non-sustainable generalized-tree-shift successor Y with strictly…
- op223_star_connectivity_from_edge_preservationAssume shifting along a nonsustainable edge preserves it, shifting a branch toward the center of a nonsustainable pendant edge preserves…
Read back from the Lean
Let V be a finite type with decidable equality, and let T and T' be simple graphs on V. The definition nonsustainable_gts_step T T' asserts the conjunction of three conditions:
1. T is a nonsustainable tree: T is a tree (T.IsTree) and T is not a sustainable tree. Here, a tree is "sustainable" if for every edge e of T, e is sustainable, meaning there exists a non-edge f of T (an edge in Tᶜ) such that replacing e with f (deleting e and adding f) yields a tree whose adjacency spectral radius is at least that of T.
2. T' is a nonsustainable tree: T' is a tree and T' is not a sustainable tree (by the same definition).
3. T' is obtained from T by a generalized tree shift (is_generalized_tree_shift T T'): T is a tree, and there exist distinct vertices u, v : V and a walk p from u to v in T such that:
- p is a path (p.IsPath),
- every internal vertex x along the path p (i.e. x ∈ p.support with x ≠ u and x ≠ v) has degree 2 in T (Nat.card (T.neighborSet x) = 2), and
- T' is the graph obtained from T by shifting all edges incident to v, other than the edge between v and its penultimate vertex on p (p.penultimate), to become edges incident to u (i.e. deleting edges {v, z} for all neighbors z ≠ p.penultimate of v, and adding edges {u, z}).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A single step of generalized tree shift between two non-sustainable trees. -/ def nonsustainable_gts_step {V : Type*} [Fintype V] [DecidableEq V] (T T' : SimpleGraph V) : Prop := is_nonsustainable_tree T ∧ is_nonsustainable_tree T' ∧ is_generalized_tree_shift T T'