AFTD Auto-Formalizing Theoretical Domains

nonsustainable_gts_step

def

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

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