AFTD Auto-Formalizing Theoretical Domains

is_sustainable_edge

def

An edge e in a tree T is sustainable if there exists a non-edge f such that T - e + f is a tree and the adjacency spectral radius of T - e + f is at least that of T.

Statement

def is_sustainable_edge {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (e : Sym2 V) : Prop
Defined in
arXiv:2610.17078 Section 1
Verified
18 Oct 2026
Axioms
none listed
Built on 1
  • 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.
Used by 10

Read back from the Lean

For a finite type V with decidable equality, a simple graph T on V, and an edge candidate e : Sym2 V, is_sustainable_edge T e asserts that: 1. e is an edge of T (e ∈ T.edgeSet), and 2. There exists an edge f in the complement graph of T (f ∈ Tᶜ.edgeSet) such that: (a) The graph obtained by deleting edge e from T and adding edge f (namely T.deleteEdges {e} ⊔ SimpleGraph.fromEdgeSet {f}) is a tree (SimpleGraph.IsTree), and (b) The adjacency spectral radius of T is less than or equal to the adjacency spectral radius of that modified graph.

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

/-- An edge e in a tree T is sustainable if replacing it by some non-edge f yields a tree with spectral radius at least that of T. -/
def is_sustainable_edge {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (e : Sym2 V) : Prop := e ∈ T.edgeSet ∧ ∃ f ∈ Tᶜ.edgeSet,
    (T.deleteEdges {e} ⊔ SimpleGraph.fromEdgeSet {f}).IsTree ∧
    adjacency_spectral_radius T ≤ adjacency_spectral_radius (T.deleteEdges {e} ⊔ SimpleGraph.fromEdgeSet {f})
See it in the graphDiscuss this resultChallenge it