AFTD Auto-Formalizing Theoretical Domains

is_spectrally_sustainable_edge

def

An edge e in a simple graph G on a finite vertex set is spectrally sustainable if there exists a non-edge f of G such that deleting e and adding f yields a connected graph whose adjacency spectral radius is at least that of G.

Statement

def is_spectrally_sustainable_edge {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (e : Sym2 V) : Prop
Defined in
arXiv:2610.17078, Sustainable trees, Section 1
Verified
27 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 1
  • is_spectrally_sustainableA simple graph G on a finite vertex set is spectrally sustainable if G is connected and every edge of G is spectrally sustainable.

Read back from the Lean

Given a finite type V with decidable equality, a simple graph G on V, and an unordered pair of vertices e : Sym2 V, is_spectrally_sustainable_edge G e asserts that: 1. e is an edge of G (e ∈ G.edgeSet); and 2. There exists an edge f in the complement graph of G (f ∈ Gᶜ.edgeSet, i.e., an unordered pair of distinct vertices that are not adjacent in G) such that: a. The graph formed by deleting e from G and adding edge f, namely G.deleteEdges {e} ⊔ SimpleGraph.fromEdgeSet {f}, is connected; and b. The adjacency spectral radius of G is less than or equal to the adjacency spectral radius of G.deleteEdges {e} ⊔ SimpleGraph.fromEdgeSet {f}.

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 simple graph G is spectrally sustainable if there is a non-edge f such that G - e + f is connected and its spectral radius is at least that of G. -/
def is_spectrally_sustainable_edge {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (e : Sym2 V) : Prop := e ∈ G.edgeSet ∧ ∃ f ∈ Gᶜ.edgeSet,
    (G.deleteEdges {e} ⊔ SimpleGraph.fromEdgeSet {f}).Connected ∧
    adjacency_spectral_radius G ≤ adjacency_spectral_radius (G.deleteEdges {e} ⊔ SimpleGraph.fromEdgeSet {f})
See it in the graphDiscuss this resultChallenge it